数据结构英文教学课件：chapter6 Tree

1、Software College Northeastern UniversityData StructureSoftware College Northeastern Universityz What is Treez Tree Terminology z Tree ADT z Binary Treesz Binary Tree ADTz Storing Binary Treesz Binary Tree Traversals z Applications of Binary Treez Storing Treesz Tree Traversalsz Huffman Code TreeData

2、 StructureSoftware College Northeastern UniversityNature View of a TreebranchesleavesrootData StructureSoftware College Northeastern UniversityComputer Scientists ViewbranchesleavesrootnodesData StructureSoftware College Northeastern UniversityWhat is a TreezA tree is a finite nonempty set of elemen

3、ts.zIt is an abstract model of a hierarchical structure.zconsists of nodes with a parent-child relation.zApplications:yOrganization chartsyFile systemsyProgramming environmentsData StructureSoftware College Northeastern UniversityWhat is a Tree:ExamplesLenovoSalesR&DManufacturingLaptopsDesktopsC

4、HINAInternationalEuropeAsiaCanadaData StructureSoftware College Northeastern UniversityWhat is a Tree:ExamplesData StructureSoftware College Northeastern UniversitysubtreeTree Terminologyz Root: node without parent (A)z Siblings: nodes share the same parentz Internal node: node with at least one chi

5、ld (A, B, C, F)z External node (leaf ): node without children (E, I, J, K, G, H, D)z Ancestors of a node: parent, grandparent, grand-grandparent, etc.z Descendant of a node: child, grandchild, grand-grandchild, etc.ABDCGHEFIJKData StructureSoftware College Northeastern UniversitysubtreeTree Terminol

6、ogyz Depth of a node: number of ancestorsz Height of a tree: maximum depth of any nodez Degree of a node: the number of its childrenz Degree of a tree: the maximum number of its node.z Subtree: tree consisting of a node and its descendantsABDCGHEFIJKData StructureSoftware College Northeastern Univer

7、sityTree TerminologyData StructureSoftware College Northeastern UniversityTree PropertiesABCDGEFIHProperty ValueNumber of nodes ?HeightRoot NodeLeavesInterior nodesAncestors of HDescendants of BSiblings of ERight subtree of ADegree of this treeData StructureSoftware College Northeastern UniversityTr

8、ee ADTz We use positions to abstract nodesz Generic methods:yinteger size()yboolean isEmpty()yobjectIterator elements()ypositionIterator positions()z Accessor methods:yposition root()yposition parent(p)ypositionIterator children(p)z Query methods:yboolean isInternal(p)yboolean isExternal(p)yboolean

9、isRoot(p)z Update methods:yswapElements(p, q)yobject replaceElement(p, o)z Additional update methods may be defined by data structures implementing the Tree ADTData StructureSoftware College Northeastern Universitytemplate class Tree public: Tree ( ); Tree ( ); position Root ( ); BuildRoot ( const T

10、ype& value ); position FirstChild ( position p ); position NextSibling ( position p, position v ); position Parent ( position p ); Type Retrieve ( position p ); Data StructureSoftware College Northeastern University int InsertChild ( const position p, const Type &value ); int DeleteChild ( p

11、osition p, int i ); void DeleteSubTree ( position t ); int IsEmpty ( );Data StructureSoftware College Northeastern UniversityBinary Treez A binary tree is a tree with the following properties:yEach internal node has at most two children (degree of two)yThe children of a node are an ordered pairACGFB

12、EDHIData StructureSoftware College Northeastern UniversityBinary TreezWe call the children of an internal node left child and right childzAlternative recursive definition: a binary tree is eitherya tree consisting of a single node, ORya tree whose root has an ordered pair of children, each of which

13、is a binary treezApplications:yarithmetic expressionsydecision processesysearchingData StructureSoftware College Northeastern UniversityA collection of binary treesData StructureSoftware College Northeastern UniversityArithmetic Expression TreezBinary tree associated with an arithmetic expressionyin

14、ternal nodes: operatorsyexternal nodes: operandszExample: arithmetic expression tree for the expression (2 (a - 1) + (3 b)+ -2a13bData StructureSoftware College Northeastern UniversityDecision Treez Binary tree associated with a decision processyinternal nodes: questions with yes/no answeryexternal

15、nodes: decisionsz Example: dining decisionWant a fast meal?How about coffee?On expense account?StarbucksMcDonalds Marriott HotelPizza HutYesNoYesNoYesNoData StructureSoftware College Northeastern UniversityMaximum Number of Nodes in a Binary TreezThe maximum number of nodes on depth i of a binary tr

16、ee is 2i, i=0.zThe maximum number of nodes in a binary tree of height k is 2k+1-1, k=0.Prove by induction.12210kkiiData StructureSoftware College Northeastern UniversityRelations between Number ofLeaf Nodes and Nodes of Degree 2 For any nonempty binary tree, T, if n0 is the number of leaf nodes and

17、n2 the number of nodes of degree 2, then n0=n2+1 PROOF: Let n and B denote the total number of nodes and branches in T. Let n0, n1, n2 represent the nodes with no children, single child, and two children respectively. B+1=n B=n1+2n2 n=n0+n1+n2 n1+2n2+1= n n0=n2+1Data StructureSoftware College Northe

18、astern UniversityFull Binary TreezA full binary tree of a given height k has 2k+11 nodes.Height 3 full binary tree.Data StructureSoftware College Northeastern UniversityLabeling Nodes In A Full Binary TreezLabel the nodes 1 through 2k+1 1. zLabel by levels from top to bottom.zWithin a level, label f

19、rom left to right.123456789101112131415Data StructureSoftware College Northeastern UniversityNode Number Properties zParent of node i is node i / 2, unless i = 1.zNode 1 is the root and has no parent.123456789101112131415Data StructureSoftware College Northeastern UniversityNode Number Properties zL

20、eft child of node i is node 2i, unless 2i n, where n is the number of nodes.zIf 2i n, node i has no left child.123456789101112131415Data StructureSoftware College Northeastern UniversityNode Number Properties zRight child of node i is node 2i+1, unless 2i+1 n, where n is the number of nodes.zIf 2i+1

21、 n, node i has no right child.123456789101112131415Data StructureSoftware College Northeastern UniversityComplete Binary Treesz A labeled binary tree containing the labels 1 to n with root 1, branches leading to nodes labeled 2 and 3, branches from these leading to 4, 5 and 6, 7, respectively, and s

22、o on.z A binary tree with n nodes and level k is complete iff its nodes correspond to the nodes numbered from 1 to n in the full binary tree of level k.Full binary tree of depth 2Complete binary treeData StructureSoftware College Northeastern Universitytemplate class BinaryTree public: BinaryTree (

23、); BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); int IsEmpty ( ); BinTreeNode *Parent ( ); BinTreeNode *LeftChild ( ); BinTreeNode *RightChild ( ); int Insert ( const Type &item ); int Find ( const Type &item ) const; Type GetData ( ) const; const BinTreeNode *GetRoot ( ) c

24、onst;Data StructureSoftware College Northeastern UniversityStoring Binary TreeszLinked structureyEach node = data cells + two child pointersyAccessed via a pointer to root nodezContiguous array structureyA1 = root nodeyA2,A3 = children of A1yA4,A5,A6,A7 = children of A2 and A3Data StructureSoftware

25、College Northeastern Universitytemplate class BiTNode TElemType data; BiTNode *leftchild,*rightchild; /pointers to left and right child ;Typedef BiTNode * BiTree; Data StructureSoftware College Northeastern University D A B C E F D A B F In one linked Binary tree there are n+1 NULL pointers.Data Str

26、uctureSoftware College Northeastern Universitytemplate class BiTNode TElemType data; BiTNode *leftchild,*rightchild,*parent; /pointers to left and right child ;ABDFECData StructureSoftware College Northeastern University A B C D E F 1 2 3 4 5 6 7 m+1A123456BCDEFA tree stored without pointersData Str

27、uctureSoftware College Northeastern UniversityA tree stored without pointersData StructureSoftware College Northeastern Universitytemplate class BinaryTree;template Class BinTreeNode friend class BinaryTree;public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) BinTreeNode ( Type item, BinTre

28、eNode *left = NULL, BinTreeNode *right = NULL ) : data (item), leftChild (left), rightChild (right) Implementation of Binary TreeData StructureSoftware College Northeastern UniversityType GetData ( ) const return data; BinTreeNode *GetLeft ( ) const return leftChild; BinTreeNode *GetRight ( ) const

29、return rightChild; void SetData ( const Type & item ) data = item; void SetLeft ( BinTreeNode *L ) leftChild = L; void SetRight ( BinTreeNode *R ) rightChild = R; Implementation of Binary TreeData StructureSoftware College Northeastern Universityprivate: BinTreeNode *leftChild, *rightChild; Type

30、 data;template class BinaryTree public: BinaryTree ( ) : root (NULL) BinaryTree ( Type value ) : RefValue (value), root (NULL) virtual BinaryTree ( ) destroy ( root ); virtual int IsEmpty ( ) return root = NULL ? 1 : 0; Implementation of Binary TreeData StructureSoftware College Northeastern Univers

31、ity virtual BinTreeNode *Parent ( BinTreeNode *current ) return root = NULL | root = current？ NULL : Parent ( root, current ); virtual BinTreeNode *LeftChild ( BinTreeNode *current ) return current != NULL ? currentleftChild : NULL; virtual BinTreeNode *RightChild ( BinTreeNode *current ) return cur

32、rent != NULL ? currentrightChild : NULL; Implementation of Binary TreeData StructureSoftware College Northeastern University virtual int Insert ( const Type & item); virtual int Find ( const Type &item ) const; const BinTreeNode *GetRoot ( ) const return root; friend istream &operator (

33、istream &in, BinaryTree &Tree ) friend ostream &operator ( ostream &out, BinaryTree &Tree )private: BinTreeNode *root; Type RefValue; Data StructureSoftware College Northeastern University BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current ); int Insert ( BinTreeNode

34、* &current, const Type &item ); void Traverse ( BinTreeNode *current, ostream &out ) const int Find ( BinTreeNode *current, const Type &item ) const void destroy(BinTreeNode *current); Data StructureSoftware College Northeastern University template void BinaryTree: destroy ( BinTreeN

35、ode *current ) if ( current != NULL ) destroy ( currentleftChild ); destroy ( currentrightChild ); delete current; Data StructureSoftware College Northeastern Universitytemplate BinTreeNode * BinaryTree : Parent ( BinTreeNode * start, BinTreeNode *current ) if ( start = NULL ) return NULL; if ( star

36、tleftChild = current | startrightChild = current ) return start; BinTreeNode *p; if ( ( p = Parent ( startleftChild, current ) ) != NULL ) return p; else return Parent ( startrightChild, current );Data StructureSoftware College Northeastern Universitytemplate void BinaryTree : Traverse ( BinTreeNode

37、 *current, ostream &out ) const if ( current != NULL ) out currentdata ; Traverse ( currentleftChild, out ); Traverse ( currentrightChild, out ); Data StructureSoftware College Northeastern Universitytemplate istream & operator ( istream & in, BinaryTree &Tree ) Type item; cout “构造二叉

38、树构造二叉树 : n ; cout “输入数据输入数据 ( 用用 Tree.RefValue item; while ( item != Tree.RefValue ) Tree.Insert ( item ); cout “输入数据输入数据 ( 用用 Tree.RefValue item; return in;Data StructureSoftware College Northeastern Universitytemplate ostream & operator ( ostream & out, BinaryTree &Tree ) out “二叉树的前序遍历

39、二叉树的前序遍历.n; Tree.Traverse ( Tree.root, out ); out endl; return out;Data StructureSoftware College Northeastern UniversityBinary Tree TraversalszLet L, r, and R stand for moving left, visiting the node, and moving right.zThere are six possible combinations of traversalyLRr, LrR, rLR , RLr, RrL, rRLzA

40、dopt convention that we traverse left before right, only 3 traversals remainyLRr, LrR, rLRypostorder, inorder, preorder Data StructureSoftware College Northeastern UniversityDepth-First TraversalsData StructureSoftware College Northeastern UniversityPreorder TraversalzIn an preorder traversal a node

41、 is visited before its left subtree and right subtreeAlgorithm PreOrder(v)if(v非空非空) visit(v)if LeftChild (v)PreOrder (leftChild (v)if rightChild(v)PreOrder (rightChild (v)532618974Data StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern UniversityData Structu

42、reSoftware College Northeastern Universitytemplate void BinaryTree :PreOrder ( ) PreOrder ( root );template void BinaryTree: PreOrder ( BinTreeNode *current ) if ( current != NULL ) cout currentdata; PreOrder ( currentleftChild ); PreOrder ( currentrightChild ); Code for Preorder TraversalData Struc

43、tureSoftware College Northeastern UniversityInorder TraversalzIn an inorder traversal a node is visited after its left subtree and before its right subtreeAlgorithm inOrder(v) if(v非空) if letChild(v)inOrder (leftChild (v)visit(v)if rightChild (v)inOrder (rightChild (v)312567984Data StructureSoftware

44、College Northeastern UniversityData StructureSoftware College Northeastern Universitytemplate void BinaryTree :InOrder ( ) InOrder ( root );template void BinaryTree : InOrder ( BinTreeNode *current ) if ( current != NULL ) InOrder ( currentleftChild ); cout currentdata; InOrder ( currentrightChild )

45、; Code for InOrder TraversalData StructureSoftware College Northeastern UniversityPostorder TraversalzIn an postorder traversal a node is visited after its left subtree and right subtreeAlgorithm PostOrder(v)if(v非空非空) if leftChild (v)PostOrder (leftChild (v)if rightChild (v)PostOrder (rightChild (v)

46、visit(v)215396784Data StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern Universitytemplate void BinaryTree :PostOrder ( ) PostOrder ( root );template void BinaryTree:PostOrder ( BinTreeNode *current ) if ( current != NULL ) PostOrder ( currentleftChild ); P

47、ostOrder ( currentrightChild ); cout currentdata; C Code for Postorder TraversalData StructureSoftware College Northeastern UniversityTraversal exam123456preorder : ?inorder : ?postorder : ?71012345698Data StructureSoftware College Northeastern Universitytemplate int BinaryTree : Size ( const BinTre

48、eNode *t ) const if ( t = NULL ) return 0; else return 1 + Size ( tleftChild ) + Size ( trightChild );Data StructureSoftware College Northeastern Universitytemplate int BinaryTree : Depth ( const BinTreeNode *t ) const if ( t = NULL ) return -1; else return 1 + Max ( Depth ( tleftChild ), Depth ( tr

49、ightChild ) ); Data StructureSoftware College Northeastern UniversityAEBCDFHIGJABECDHIGJFABEHIGJFCDA problem often in exam of data structure Data StructureSoftware College Northeastern UniversityPrint Arithmetic Expressionstemplate void BinaryTree :Outputexpress () Outputexpress(root);template void

50、BinaryTree : Outputexpress ( const BinTreeNode *T );Data StructureSoftware College Northeastern UniversityPrint Arithmetic Expressionsz Specialization of an inorder traversalyprint operand or operator when visiting nodeyprint “(“ before traversing left subtreeyprint “)“ after traversing right subtre

51、eAlgorithm inOrder (v)if isInternal (v)print(“()inOrder (leftChild (v)print(v.element ()if isInternal (v)inOrder (rightChild (v)print (“)2a13b(2 (a - 1) + (3 b)Data StructureSoftware College Northeastern UniversityPrint Arithmetic Expressionstemplate void BinaryTree : Outputexpress ( const BinTreeNo

52、de *T ) if (T) if(T-leftChild != NULL) printf(); cout data; if(T-rightChild != NULL) printf(); Data StructureSoftware College Northeastern UniversityEvaluate Arithmetic Expressionsz recursive method returning the value of a subtreez when visiting an internal node, combine the values of the subtreesA

53、lgorithm evalExpr(v)if isExternal (v)return v.element ()elsex evalExpr(leftChild (v)y evalExpr(rightChild (v) operator stored at vreturn x y25132Data StructureSoftware College Northeastern University Input a preorder sequence of a binary tree ,create a Linked structure of the binary tree. A F E D C

54、B*Create a binary tree through preorder sequenceData StructureSoftware College Northeastern Universitytemplate void BinaryTree : CreateBinaryTree () CreateBinaryTree(root); Create a binary tree through preorder sequenceData StructureSoftware College Northeastern Universitytemplate void BinaryTree :

55、CreateBinaryTree (BiTreeNode * T) scanf(&ch); /get a char if (ch=*) T=NULL; /if it denotes an empty tree else if (!(T= new BiTreeNode() exit(1); /allocated failed T-data = ch; CreateBiTree(T-leftChild); /creates its left subtree CreateBiTree(T-rightChild); /creates its right subtree return OK; C

56、reate a binary tree through preorder sequenceData StructureSoftware College Northeastern UniversityCreativity: pathLength(tree) = depth(v) v treeAlgorithm pathLength(v, n)Input: a tree node v and an initial value nOutput: the pathLength of the tree with root vUsage: pl = pathLength(root, 0);if isExt

57、ernal (v)return nlLength = rLength = 0if (leftchild(v) lLength= pathLength(leftChild (v), n + 1) if (rightchild(v) rLength= pathLength(rightChild (v), n + 1) return lLength + rlength + n;Data StructureSoftware College Northeastern UniversityCreativity: Algorithm NumberofTree(v, n)Input: a tree node

58、v and an initial value nOutput: the number of nodes with root vUsage: leafn = NumberofTree(root, 0);Algorithm NumberofLeaf(v, n)Input: a tree node v and an initial value nOutput: the number of leaf nodes with root vUsage: leafn = Numberofleaf(root, 0);Data StructureSoftware College Northeastern Univ

59、ersityTree Traversal:Recursive Implementationz Recall that a stack is used during function calls.z The caller function places the arguments on the stack and passes control to the callee.z Local variables are allocated storage on the call stack.z Calling a function itself makes no difference as far a

60、s the call stack is concerned. Data StructureSoftware College Northeastern University a + * /d -T e b c TLData StructureSoftware College Northeastern UniversityNon Recursive TraversalzWe can implement non-recursive versions of the preorder, inorder and postorder traversal by using an explicit stack.zThe stack will be used to store the tree nodes in the appropriate order.zHere, for example, is the