算法和数据结构09课件.ppt

1、2004-3L.Chen12004-3L.Chen2qTrees.qTerminology.qTraversal of Binary Trees.qExpression Trees.qBinary Search Trees.2004-3L.Chen3Definition A trees:t is a finite nonempty set of elements.One of these elements is called the root,and the remaining elements(if any)are partitioned into trees which are calle

2、d the subtrees of t.2004-3L.Chen62004-3L.Chen7nodes2004-3L.Chen8parent node2004-3L.Chen9child nodesparent node2004-3L.Chen10child nodesparent node2004-3L.Chen11root node2004-3L.Chen12leaf nodes2004-3L.Chen13sub-tree2004-3L.Chen14sub-tree2004-3L.Chen15sub-tree2004-3L.Chen16sub-treeLevel 4Level 3Level

3、 2ObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeExceptionLevel 1ObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeException321100100ObjectNumberThrowableOutputStreamIntegerDoubleExceptionFileOutputStreamRuntimeException321100100Degree of tr

4、ee=3.2004-3L.Chen20nFinite(possibly empty)collection of elements.nA nonempty binary tree has a root element.nThe remaining elements(if any)are partitioned into two binary trees.nThese are called the left and right subtrees of the binary tree.2004-3L.Chen21nNo node in a binary tree may have a degree

5、more than 2,whereas there is no limit on the degree of a node in a tree.nA binary tree may be empty;a tree cannot be empty.2004-3L.Chen22nThe subtrees of a binary tree are ordered;those of a tree are not ordered.abab Are different when viewed as binary trees.Are the same when viewed as trees.2004-3L

6、.Chen23ABABemptyemptyABCDEFGHI#nodes=9height of root=42004-3L.Chen24nUse binary trees to represent arithmetic expressionsne.g.,/a*e-cd)(*dcea2004-3L.Chen25n(a+b)*(c+d)+e f/g*h+3.25nExpressions comprise three kinds of entities.Operators(+,-,/,*).Operands(a,b,c,d,e,f,g,h,3.25,(a+b),(c+d),etc.).Delimit

7、ers(,).2004-3L.Chen26nNumber of operands that the operator requires.nBinary operator requires two operands.a+bc/de-fnUnary operator requires one operand.+g-h2004-3L.Chen27nNormal way to write an expression.nBinary operators come in between their left and right operands.a*ba+b*ca*b/c(a+b)*(c+d)+e f/g

8、*h+3.252004-3L.Chen28nHow do you figure out the operands of an operator?a+b*ca*b+c/dnThis is done by assigning operator priorities.priority(*)=priority(/)priority(+)=priority(-)nWhen an operand lies between two operators,the operand associates with the operator that has higher priority.2004-3L.Chen2

9、9nWhen an operand lies between two operators that have the same priority,the operand associates with the operator on the left.a+b-ca*b/c/d2004-3L.Chen30nSubexpression within delimiters is treated as a single operand,independent from the remainder of the expression.(a+b)*(c d)/(e f)2004-3L.Chen31nNee

10、d operator priorities,tie breaker,and delimiters.nThis makes computer evaluation more difficult than is necessary.nPostfix and prefix expression forms do not rely on operator priorities,a tie breaker,or delimiters.nSo it is easier for a computer to evaluate expressions that are in these forms.2004-3

11、L.Chen32nThe postfix form of a variable or constant is the same as its infix form.a,b,3.25nThe relative order of operands is the same in infix and postfix forms.nOperators come immediately after the postfix form of their operands.Infix=a+bPostfix=ab+2004-3L.Chen33nInfix=a+b*cPostfix=a b c*+Infix=a*b

12、+c Postfix=a b*c+Infix=(a+b)*(c d)/(e+f)Postfix=a b+c d-*e f+/2004-3L.Chen34nReplace with new symbols.+a=a+a+b=a b+-a=a?-a-b=a?b-2004-3L.Chen35nScan postfix expression from left to right pushing operands on to a stack.nWhen an operator is encountered,pop as many operands as this operator needs;evalu

13、ate the operator;push the result on to the stack.nThis works because,in postfix,operators come immediately after their operands.2004-3L.Chen36n(a+b)*(c d)/(e+f)na b+c d-*e f+/na b+c d-*e f+/stacka a b+c d-*e f+/b a b+c d-*e f+/2004-3L.Chen37n(a+b)*(c d)/(e+f)na b+c d-*e f+/na b+c d-*e f+/stack(a+b)a

14、 b+c d-*e f+/a b+c d-*e f+/a b+c d-*e f+/c a b+c d-*e f+/d a b+c d-*e f+/2004-3L.Chen38n(a+b)*(c d)/(e+f)na b+c d-*e f+/stack(a+b)a b+c d-*e f+/(c d)2004-3L.Chen39n(a+b)*(c d)/(e+f)na b+c d-*e f+/stack(a+b)*(c d)a b+c d-*e f+/e a b+c d-*e f+/a b+c d-*e f+/f a b+c d-*e f+/2004-3L.Chen40n(a+b)*(c d)/(

15、e+f)na b+c d-*e f+/stack(a+b)*(c d)a b+c d-*e f+/(e+f)a b+c d-*e f+/a b+c d-*e f+/a b+c d-*e f+/a b+c d-*e f+/2004-3L.Chen41nThe prefix form of a variable or constant is the same as its infix form.a,b,3.25nThe relative order of operands is the same in infix and prefix forms.nOperators come immediate

16、ly before the prefix form of their operands.Infix=a+bPostfix=ab+Prefix=+ab2004-3L.Chen42na+b+ab-a-a2004-3L.Chen43n(a+b)*(c d)/(e+f)/+ab-cd+ef*/2004-3L.Chen44nLeft and right operands are easy to visualize.nCode optimization algorithms work with the binary tree form of an expression.nSimple recursive

17、evaluation of expression.+ab-cd+ef*/2004-3L.Chen451.A binary tree with n nodes has n-1 edges2.A binary tree of height h,h0,has at least h and at most 2h-1 elements in it3.The height of a binary tree that contains n elements is at most n and at least log2(n+1)2004-3L.Chen48nMinimum number of nodes in

18、 a binary tree whose height is h.nAt least one node at each of first h levels.minimum number of nodes is hnAll possible nodes at first h levels are present.Maximum number of nodes=1+2+4+8+2h-1=2h-12004-3L.Chen50nLet n be the number of nodes in a binary tree whose height is h.nh=n=2h 1nlog2(n+1)=h n,

19、where n is the number of nodes.nIf 2i n,node i has no left child.123456789101112131415 nRight child of node i is node 2i+1,unless 2i+1 n,where n is the number of nodes.nIf 2i+1 n,node i has no right child.123456789101112131415123467121415513810119Definition:Full binary tree of height h has exactly 2

20、h-1 elementsExample:height h=4 24-1 =15 elements2004-3L.Chen57123465 Definition:binary tree of height h all levels except possibly level h-1 are full full binary tree is a special case of a complete binary tree2004-3L.Chen58nStart with a full binary tree that has at least n nodes.nNumber the nodes a

21、s described earlier.nThe binary tree defined by the nodes numbered 1 through n is the unique n node complete binary tree.2004-3L.Chen59nComplete binary tree with 10 nodes.123456789101112131415nLet i,1 i n,be the number assigned to an element of a complete binary tree of height h as follows:nBegin at

22、 level 1 and go down to level h,numbering left to right(see next slide).If i=1,then element is root of binary tree.If i1,then its parent has number i/2nIf 2in,then element has no left child.O.w.,its left child has been assigned the number 2inIf 2i+1n,then this element has no right child.O.w.,its rig

23、ht child has been assigned the number 2i+12004-3L.Chen61123467121415513810119Rigorous proof by induction on i2004-3L.Chen62nWhich nodes are leaves?nWhich node is the root?nWhat is the parent of C?nWhich nodes are ancestors of E?ABCDFGIJEKHLnWhat is the depth of node C?nWhat is the height of node C/t

24、he tree?nHow many different paths of length 3 are there?2004-3L.Chen63nFormula-Based RepresentationnLinked RepresentationnNumber the nodes using the numbering scheme for a full binary tree.The node that is numbered i is stored in treei.tree0510abc d e fg h ijbacdefghi j12345678910nAn n node binary t

25、ree needs an array whose length is between n+1 and 2n.ab13c7d15tree0510a-b-c-15d2004-3L.Chen68nEach binary tree node is represented as an object whose data type is BinaryTreeNode.nThe space required by an n node binary tree is n*(space required by one node).acbdfeghleftChildelementrightChildrootnUse

26、 array to store elementsnElement numbers are used as array indicesnAssume complete binary tree(with missing elements)nLeave empty cells in the arraynUse properties of complete b.t.to calculate array indices(see previous slide)ABC1234567ABC01234567nLet r be index of element,thennParent(r)=(r-1)/2,0rn

27、nLeft child(r)=2r+1,if 2r+1 nnRight child(r)=2r+2 if 2r+2nnLeft sibling(r)=r-1 if even and 0rnnRight sibling(r)=r+1 if r odd and r+1nnCompact representationnHowever,only useful when number of missing elements is small 2004-3L.Chen72nRight-skewed binary treeWith n elements,requires array of size up t

28、o 2n-1 ABC37ABCDD7nEach element is represented by by a node(chain node)that has two link fields(leftChild and rightChild)neach node has element field to hold datanedge in tree is represented by a pointer from parent node to child nodetABCDEA binary tree with n nodes has2n-(n-1)=n+1 NULL pointers2004

29、-3L.Chen74nPopular way to represent treesnlarge fraction of space is devoted to tree structure overhead(not to storing data)nTree traversal through pointer“chasing”nneed methods such as getLeftChild(),getRightChild(),etc.template class BinaryTreeNode public:BinaryTreeNode()LeftChild=RightChild=0;Bin

30、aryTreeNode(const T&e)data=e;LeftChild=RightChild=0;BinaryTreeNode(const T&e,BinaryTreeNode*l,BinaryTreeNode*r)data=e;LeftChild=l;RightChild=r;private:T data;BinaryTreeNode*LeftChild,/left subtree *RightChild;/right subtree ;Program 8.1 Node class for linked binary trees2004-3L.Chen762004-3L.Chen77T

31、he Operations:Determine its height.Determine the number of elements in it.Make a Copy.Display the binary tree on a screen or on paper.Determine whether two binary trees are identical.Delete the tree.If it is an expression tree,evaluate the expression.If it is an expression tree,obtain the parenthesi

32、zed form of the expression.2004-3L.Chen78qSystematic way of visiting all the nodes.qMethods:Preorder,Inorder,and PostorderqThey all traverse the left subtree before the right subtree.qThe name of the traversal method depends on when the node is visited.2004-3L.Chen79nMany binary tree operations are

33、done by performing a traversal of the binary tree.nIn a traversal,each element of the binary tree is visited exactly once.nDuring the visit of an element,all action(make a clone,display,evaluate the operator,etc.)with respect to this element is taken.2004-3L.Chen80nPreordernInordernPostordernLevel o

34、rder2004-3L.Chen81qVisit the node.qTraverse the left subtree.qTraverse the right subtree.2004-3L.Chen82314364204056283347598943312028403364564759892004-3L.Chen83qTraverse the left subtree.qVisit the node.qTraverse the right subtree.2004-3L.Chen84314364204056283347598920312840334356475964892004-3L.Ch

35、en85qTraverse the left subtree.qTraverse the right subtree.qVisit the node.2004-3L.Chen86314364204056283347598920284031335647596489432004-3L.Chen87qA Binary Tree built with operands and operators.qAlso known as a parse tree.qUsed in compilers.2004-3L.Chen88/+/13*6741/3 +6*7/42004-3L.Chen89qPreorderP

36、refix NotationqInorderInfix NotationqPostorderPostfix Notation2004-3L.Chen90/+/13*6741/3+*67/42004-3L.Chen917/1+/3*64Recall:Reverse Polish Notation11336677*44/+772004-3L.Chen92/+/13*674+/13/*6742004-3L.Chen93Program 8.2 Preorder traversaltemplate void PreOrder(BinaryTreeNode*t)if(t)Visit(t);/visit t

37、ree root PreOrder(t-LeftChild);/do left subtree PreOrder(t-RightChild);/do right subtree 2004-3L.Chen94Program 8.3 Inorder traversaltemplate void InOrder(BinaryTreeNode*t)if(t)InOrder(t-LeftChild);/do left subtree Visit(t);/visit tree root InOrder(t-RightChild);/do right subtree 2004-3L.Chen95Progra

38、m 8.4 Postorder traversaltemplate void PostOrder(BinaryTreeNode*t)if(t)PostOrder(t-LeftChild);/do left subtree PostOrder(t-RightChild);/do right subtree Visit(t);/visit tree root 2004-3L.Chen96AbstractDataType BinaryTree instances:collection elements;if not empty,thecollection is partitioned into a

39、root,left subtree,andright subtree;each subtree is also a binary tree;operations:Create():Create an empty binary tree;IsEmpty:Return true if empty,return false otherwise;Root(x):x is set to root element;return false if the operation fails,return true otherwiseMakeTree(root,left,right):create a binar

40、y treeelement,left(right)as theleft(right)subtree.BreakTree(root,left,right):inverse of createPreOrder:preorder traversal of binary treeInOrder:inorder traversal of binary treePostOrder:postorder traversal of binary treeLevelOrder:level-order traversal of binary treeADT 5.1 The abstract data type bi

41、nary tree2004-3L.Chen99template class BinaryTree public:BinaryTree()root=0;BinaryTree();bool IsEmpty()constreturn(root)?false:true);bool Root(T&x)const;void MakeTree(const T&element,BinaryTree&left,BinaryTree&right);void BreakTree(T&element,BinaryTree&left,BinaryTree&right);void PreOrder(void(*Visit

42、)(BinaryTreeNode*u)PreOrder(Visit,root);void InOrder(void(*Visit)(BinaryTreeNode*u)InOrder(Visit,root);void PostOrder(void(*Visit)(BinaryTreeNode*u);PostOrder(Visit,root);void LevelOrder(void(*Visit)(BinaryTreeNode*u);private:BinaryTreeNode*root;/pointer to root void PreOrder(void(*Visit)(BinaryTree

43、Node*u),BinaryTreeNode*t);void InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);void PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);template bool BinaryTree:Root(T&x)const/Set x to root data./Return false if no root.if(root)x=root-data;return true;else return false;/no root templ

44、ate void BinaryTree:MakeTree(const T&element,BinaryTree&left,BinaryTree&right)root=new BinaryTreeNode (element,left.root,right.root);left.root=right.root=0;template void BinaryTree:BreakTree(T&element,BinaryTree&left,BinaryTree&right)if(!root)throw BadInput();/tree empty element=root-data;left.root=

45、root-LeftChild;right.root=root-RightChild;delete root;root=0;template void BinaryTree:PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)/Preorder traversal.if(t)Visit(t);PreOrder(Visit,t-LeftChild);PreOrder(Visit,t-RightChild);template void BinaryTree:InOrder(void(*Visit)(BinaryTreeNode*u),Bi

46、naryTreeNode*t)/Inorder traversal.if(t)InOrder(Visit,t-LeftChild);Visit(t);InOrder(Visit,t-RightChild);template void BinaryTree:PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)/Postorder traversal.if(t)PostOrder(Visit,t-LeftChild);PostOrder(Visit,t-RightChild);Visit(t);2004-3L.Chen1092004-3L.Chen110ChapterEx8;Ex16;Ex22;