數(shù)據(jù)結構英文教學課件：chapter6 Tree

1、Chapter 6Tree Data StructureSoftware College Northeastern UniversityOverview What is Tree Tree Terminology Tree ADT Binary Trees Binary Tree ADT Storing Binary Trees Binary Tree Traversals Applications of Binary Tree Storing Trees Tree Traversals Huffman Code TreeData StructureSoftware College North

2、eastern UniversityNature View of a TreebranchesleavesrootData StructureSoftware College Northeastern UniversityComputer Scientists ViewbranchesleavesrootnodesData StructureSoftware College Northeastern UniversityWhat is a TreeA tree is a finite nonempty set of elements.It is an abstract model of a h

3、ierarchical structure.consists of nodes with a parent-child relation.Applications:Organization chartsFile systemsProgramming environmentsData StructureSoftware College Northeastern UniversityWhat is a Tree:ExamplesLenovoSalesR&DManufacturingLaptopsDesktopsCHINAInternationalEuropeAsiaCanadaData Struc

4、tureSoftware College Northeastern UniversityWhat is a Tree:ExamplesData StructureSoftware College Northeastern UniversitysubtreeTree TerminologyRoot: node without parent (A)Siblings: nodes share the same parentInternal node: node with at least one child (A, B, C, F)External node (leaf ): node withou

5、t children (E, I, J, K, G, H, D)Ancestors of a node: parent, grandparent, grand-grandparent, etc.Descendant of a node: child, grandchild, grand-grandchild, etc.ABDCGHEFIJKData StructureSoftware College Northeastern UniversitysubtreeTree TerminologyDepth of a node: number of ancestorsHeight of a tree

6、: maximum depth of any nodeDegree of a node: the number of its childrenDegree of a tree: the maximum number of its node.Subtree: tree consisting of a node and its descendantsABDCGHEFIJKData StructureSoftware College Northeastern UniversityTree TerminologyData StructureSoftware College Northeastern U

7、niversityTree PropertiesABCDGEFIHProperty ValueNumber of nodes ?HeightRoot NodeLeavesInterior nodesAncestors of HDescendants of BSiblings of ERight subtree of ADegree of this treeData StructureSoftware College Northeastern UniversityTree ADTWe use positions to abstract nodesGeneric methods:integer s

8、ize()boolean isEmpty()objectIterator elements()positionIterator positions()Accessor methods:position root()position parent(p)positionIterator children(p)Query methods:boolean isInternal(p)boolean isExternal(p)boolean isRoot(p)Update methods:swapElements(p, q)object replaceElement(p, o)Additional upd

9、ate methods may be defined by data structures implementing the Tree ADTData StructureSoftware College Northeastern Universitytemplate class Tree public: Tree ( ); Tree ( ); position Root ( ); BuildRoot ( const Type& value ); position FirstChild ( position p ); position NextSibling ( position p, posi

10、tion v ); position Parent ( position p ); Type Retrieve ( position p ); ADT of TreeData StructureSoftware College Northeastern University int InsertChild ( const position p, const Type &value ); int DeleteChild ( position p, int i ); void DeleteSubTree ( position t ); int IsEmpty ( );ADT of TreeData

11、 StructureSoftware College Northeastern UniversityBinary TreeA binary tree is a tree with the following properties:Each internal node has at most two children (degree of two)The children of a node are an ordered pairACGFBEDHIData StructureSoftware College Northeastern UniversityBinary TreeWe call th

12、e children of an internal node left child and right childAlternative recursive definition: a binary tree is eithera tree consisting of a single node, ORa tree whose root has an ordered pair of children, each of which is a binary treeApplications:arithmetic expressionsdecision processessearchingData

13、StructureSoftware College Northeastern UniversityA collection of binary treesData StructureSoftware College Northeastern UniversityArithmetic Expression TreeBinary tree associated with an arithmetic expressioninternal nodes: operatorsexternal nodes: operandsExample: arithmetic expression tree for th

14、e expression (2 (a - 1) + (3 b)+-2a13bData StructureSoftware College Northeastern UniversityDecision TreeBinary tree associated with a decision processinternal nodes: questions with yes/no answerexternal nodes: decisionsExample: dining decisionWant a fast meal?How about coffee?On expense account?Sta

15、rbucksMcDonalds Marriott HotelPizza HutYesNoYesNoYesNoData StructureSoftware College Northeastern UniversityMaximum Number of Nodes in a Binary TreeThe maximum number of nodes on depth i of a binary tree is 2i, i=0.The maximum number of nodes in a binary tree of height k is 2k+1-1, k=0.Prove by indu

16、ction.Data 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 n2 the number of nodes of degree 2, then n0=n2+1 PROOF: Let n and B denote the total number of nodes and bran

17、ches 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 Northeastern UniversityFull Binary TreeA full binary tree of a given height k has 2k+11 nodes.Height 3 full binary

18、tree.Data StructureSoftware College Northeastern UniversityLabeling Nodes In A Full Binary TreeLabel the nodes 1 through 2k+1 1. Label by levels from top to bottom.Within a level, label from left to right.123456789101112131415Data StructureSoftware College Northeastern UniversityNode Number Properti

19、es Parent of node i is node i / 2, unless i = 1.Node 1 is the root and has no parent.123456789101112131415Data StructureSoftware College Northeastern UniversityNode Number Properties Left child of node i is node 2i, unless 2i n, where n is the number of nodes.If 2i n, node i has no left child.123456

20、789101112131415Data StructureSoftware College Northeastern UniversityNode Number Properties Right child of node i is node 2i+1, unless 2i+1 n, where n is the number of nodes.If 2i+1 n, node i has no right child.123456789101112131415Data StructureSoftware College Northeastern UniversityComplete Binar

21、y TreesA 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 so on.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

22、 full binary tree of level k.Full binary tree of depth 2Complete binary tree151536273244Data StructureSoftware College Northeastern UniversityADT of Binary treetemplate class BinaryTree public: BinaryTree ( ); BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); int IsEmpty ( ); BinTreeNo

23、de *Parent ( ); BinTreeNode *LeftChild ( ); BinTreeNode *RightChild ( ); int Insert ( const Type &item ); int Find ( const Type &item ) const; Type GetData ( ) const; const BinTreeNode *GetRoot ( ) const;Data StructureSoftware College Northeastern UniversityStoring Binary TreesLinked structureEach n

24、ode = data cells + two child pointersAccessed via a pointer to root nodeContiguous array structureA1 = root nodeA2,A3 = children of A1A4,A5,A6,A7 = children of A2 and A3Data StructureSoftware College Northeastern UniversityBinary Tree in linked structuretemplate class BiTNode TElemType data; BiTNode

25、 *leftchild,*rightchild; /pointers to left and right child ;Typedef BiTNode * BiTree; DataParentLeftchildrightchildData StructureSoftware College Northeastern University D A B C E F AFEABCD D A B F In one linked Binary tree there are n+1 NULL pointers.BCDData StructureSoftware College Northeastern U

26、niversityAnother linked structuretemplate class BiTNode TElemType data; BiTNode *leftchild,*rightchild,*parent; /pointers to left and right child ;ABDFECADEBCFData StructureSoftware College Northeastern University A B C D E F #define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE+1 SqBiTr

27、ee bt; 1 2 3 4 5 6 7 m+1A123456BCDEFA tree stored without pointersData StructureSoftware College Northeastern UniversityA tree stored without pointers1 2 3 4 5 6 7 8 9 10 m+1A B C D E F GAEGADEG11068CBDFFCBData StructureSoftware College Northeastern Universitytemplate class BinaryTree;template Class

28、 BinTreeNode friend class BinaryTree;public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) BinTreeNode ( Type item, BinTreeNode *left = NULL, BinTreeNode *right = NULL ) : data (item), leftChild (left), rightChild (right) Implementation of Binary TreeData StructureSoftware College Northeaste

29、rn UniversityType GetData ( ) const return data; BinTreeNode *GetLeft ( ) const return leftChild; BinTreeNode *GetRight ( ) const return rightChild; void SetData ( const Type & item ) data = item; void SetLeft ( BinTreeNode *L ) leftChild = L; void SetRight ( BinTreeNode *R ) rightChild = R; Impleme

30、ntation of Binary TreeData StructureSoftware College Northeastern Universityprivate: BinTreeNode *leftChild, *rightChild; Type data;template class BinaryTree public: BinaryTree ( ) : root (NULL) BinaryTree ( Type value ) : RefValue (value), root (NULL) virtual BinaryTree ( ) destroy ( root ); virtua

31、l int IsEmpty ( ) return root = NULL ? 1 : 0; Implementation of Binary TreeData StructureSoftware College Northeastern University virtual BinTreeNode *Parent ( BinTreeNode *current ) return root = NULL | root = current？ NULL : Parent ( root, current ); virtual BinTreeNode *LeftChild ( BinTreeNode *c

32、urrent ) return current != NULL ? currentleftChild : NULL; virtual BinTreeNode *RightChild ( BinTreeNode *current ) return current != NULL ? currentrightChild : NULL; Implementation of Binary TreeData StructureSoftware College Northeastern University virtual int Insert ( const Type & item); virtual

33、int Find ( const Type &item ) const; const BinTreeNode *GetRoot ( ) const return root; friend istream &operator ( istream &in, BinaryTree &Tree ) friend ostream &operator ( ostream &out, BinaryTree &Tree )private: BinTreeNode *root; Type RefValue; Data StructureSoftware College Northeastern Universi

34、ty BinTreeNode *Parent ( BinTreeNode *start, BinTreeNode *current ); int Insert ( BinTreeNode * ¤t, const Type &item ); void Traverse ( BinTreeNode *current, ostream &out ) const int Find ( BinTreeNode *current, const Type &item ) const void destroy(BinTreeNode *current); Data StructureSoftwar

35、e College Northeastern University Implementation of functions template void BinaryTree: destroy ( BinTreeNode *current ) if ( current != NULL ) destroy ( currentleftChild ); destroy ( currentrightChild ); delete current; Data StructureSoftware College Northeastern Universitytemplate BinTreeNode * Bi

36、naryTree : Parent ( BinTreeNode * start, BinTreeNode *current ) if ( start = NULL ) return NULL; if ( startleftChild = current | startrightChild = current ) return start; BinTreeNode *p; if ( ( p = Parent ( startleftChild, current ) ) != NULL ) return p; else return Parent ( startrightChild, current

37、 );Implementation of functionsData StructureSoftware College Northeastern Universitytemplate void BinaryTree : Traverse ( BinTreeNode *current, ostream &out ) const if ( current != NULL ) out currentdata ; Traverse ( currentleftChild, out ); Traverse ( currentrightChild, out ); Implementation of fun

38、ctionsData StructureSoftware College Northeastern Universitytemplate istream & operator ( istream & in, BinaryTree &Tree ) Type item; cout “構造二叉樹 : n ; cout “輸入數(shù)據(jù) ( 用 Tree.RefValue item; while ( item != Tree.RefValue ) Tree.Insert ( item ); cout “輸入數(shù)據(jù) ( 用 Tree.RefValue item; return in;Implementation

39、 of functionsData StructureSoftware College Northeastern Universitytemplate ostream & operator ( ostream & out, BinaryTree &Tree ) out “二叉樹的前序遍歷.n; Tree.Traverse ( Tree.root, out ); out endl; return out;Implementation of functionsData StructureSoftware College Northeastern UniversityBinary Tree Trav

40、ersalsLet L, r, and R stand for moving left, visiting the node, and moving right.There are six possible combinations of traversalLRr, LrR, rLR , RLr, RrL, rRLAdopt convention that we traverse left before right, only 3 traversals remainLRr, LrR, rLRpostorder, inorder, preorder Data StructureSoftware

41、College Northeastern UniversityDepth-First TraversalsData StructureSoftware College Northeastern UniversityPreorder TraversalIn an preorder traversal a node is visited before its left subtree and right subtreeAlgorithm PreOrder(v)if(v非空) visit(v)if LeftChild (v)PreOrder (leftChild (v)if rightChild(v

42、)PreOrder (rightChild (v)532618974Data StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern Universitytemplate void BinaryTree :PreOrder ( ) PreOrder ( root );template void BinaryTree: PreOrder ( BinTreeNod

43、e *current ) if ( current != NULL ) cout currentdata; PreOrder ( currentleftChild ); PreOrder ( currentrightChild ); Code for Preorder TraversalData StructureSoftware College Northeastern UniversityInorder TraversalIn an inorder traversal a node is visited after its left subtree and before its right

44、 subtreeAlgorithm inOrder(v) if(v非空) if letChild(v)inOrder (leftChild (v)visit(v)if rightChild (v)inOrder (rightChild (v)312567984Data StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern Universitytemplate void BinaryTree :InOrder ( ) InOrder ( root );templat

45、e void BinaryTree : InOrder ( BinTreeNode *current ) if ( current != NULL ) InOrder ( currentleftChild ); cout currentdata; InOrder ( currentrightChild ); Code for InOrder TraversalData StructureSoftware College Northeastern UniversityPostorder TraversalIn an postorder traversal a node is visited af

46、ter its left subtree and right subtreeAlgorithm PostOrder(v)if(v非空) if leftChild (v)PostOrder (leftChild (v)if rightChild (v)PostOrder (rightChild (v)visit(v)215396784Data StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern Universitytemplate void BinaryTree

47、:PostOrder ( ) PostOrder ( root );template void BinaryTree:PostOrder ( BinTreeNode *current ) if ( current != NULL ) PostOrder ( currentleftChild ); PostOrder ( currentrightChild ); cout currentdata; C Code for Postorder TraversalData StructureSoftware College Northeastern UniversityTraversal exam12

48、3456preorder : ?inorder : ?postorder : ?71012345698Data StructureSoftware College Northeastern Universitytemplate int BinaryTree : Size ( const BinTreeNode *t ) const if ( t = NULL ) return 0; else return 1 + Size ( tleftChild ) + Size ( trightChild );Application of Binary TreeTraversalData Structur

49、eSoftware College Northeastern Universitytemplate int BinaryTree : Depth ( const BinTreeNode *t ) const if ( t = NULL ) return -1; else return 1 + Max ( Depth ( tleftChild ), Depth ( trightChild ) ); Application of Binary TreeTraversalData StructureSoftware College Northeastern UniversityExam：if we

50、know the preorder sequence of a binary tree ABECDFGHIJAlso inorder sequence of a binary tree EBCDAFHIGJ specify this binary tree.ABECDFGHIJ ABECDFGHIJ ABECDFGHIJEBCDAFHIGJ EBCD FHIGJ E CD HIGJAEBCDFHIGJABECDHIGJFABEHIGJFCDA problem often in exam of data structure Data StructureSoftware College North

51、eastern UniversityPrint Arithmetic Expressionstemplate void BinaryTree :Outputexpress () Outputexpress(root);template void BinaryTree : Outputexpress ( const BinTreeNode *T );Data StructureSoftware College Northeastern UniversityPrint Arithmetic ExpressionsSpecialization of an inorder traversalprint

52、 operand or operator when visiting nodeprint “(“ before traversing left subtreeprint “)“ after traversing right subtreeAlgorithm 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 StructureSoftwa

53、re College Northeastern UniversityPrint Arithmetic Expressionstemplate void BinaryTree : Outputexpress ( const BinTreeNode *T ) if (T) if(T-leftChild != NULL) printf(); Outputexpress(T-leftChild); cout data; if(T-rightChild != NULL) Outputexpress(T-rightChild); printf(); Data StructureSoftware Colle

54、ge Northeastern UniversityEvaluate Arithmetic Expressionsrecursive method returning the value of a subtreewhen visiting an internal node, combine the values of the subtreesAlgorithm evalExpr(v)if isExternal (v)return v.element ()elsex evalExpr(leftChild (v)y evalExpr(rightChild (v) operator stored a

55、t vreturn x y+-25132Data 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 B*Express null using *A B D * F * * * C E * * *Preorder sequence：A B D F C E Create a binary tree through preorder sequenceDa

56、ta StructureSoftware College Northeastern Universitytemplate void BinaryTree : CreateBinaryTree () CreateBinaryTree(root); Create a binary tree through preorder sequenceData StructureSoftware College Northeastern Universitytemplate void BinaryTree : CreateBinaryTree (BiTreeNode * T) scanf(&ch); /get

57、 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; Create a binary tree through preorder sequenceData Stru

58、ctureSoftware 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 isExternal (v)return nlLength = rLength = 0if (leftchild(v)

59、 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 v and an initial value nOutput: the number of nodes wi

60、th 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 UniversityTree Traversal:Recursive Implementation Recall t