树和森林的概念ppt课件

1、template class Tree public: Tree ( ); Tree ( ); position Root ( ); BuildRoot ( const Type& value ); position FirstChild ( position p ); position NextSibling ( position p, position v ); position Parent ( position p ); Type Retrieve ( position p ); position InsertChild ( const position p, const Type &

2、value ); position DeleteChild ( position p, int i ); void DeleteSubTree ( position t ); int IsEmpty ( ); n0n21假设设二叉树的高度为假设设二叉树的高度为h，那么共有，那么共有h+1层。除第层。除第h层外，其它各层层外，其它各层(0 h-1)的的结点数都到达最大个数，第结点数都到达最大个数，第h层从右向左延层从右向左延续缺假设干结点，这就是完全二叉树。续缺假设干结点，这就是完全二叉树。n+1 2h+1 取对数取对数 h log2(n+1) h+1 template class Binary

3、Tree public: BinaryTree ( ); 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 BinTreeN

4、ode *GetRoot ( ) const;完全二叉树的数组表示完全二叉树的数组表示 普通二叉树的数组表示普通二叉树的数组表示 单支树二叉树链表表示的例如二叉树链表表示的例如二叉链表的静态构造二叉链表的静态构造template class BinaryTree;template Class BinTreeNode friend class BinaryTree;public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) BinTreeNode ( Type item, BinTreeNode *left = NULL, BinT

5、reeNode *right = NULL ) : data (item), leftChild (left), rightChild (right) const Type & 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 )

6、leftChild = L; void SetRight ( BinTreeNode *R ) rightChild = R; private: BinTreeNode *leftChild, *rightChild; Type data;template class BinaryTree public: BinaryTree ( ) : root (NULL) BinaryTree ( Type value ) : RefValue (value), root (NULL) virtual BinaryTree ( ) destroy ( root ); virtual int IsEmpt

7、y ( ) return root = NULL ? 1 : 0; virtual BinTreeNode *Parent ( BinTreeNode *current ) return root = NULL | root = current？ NULL : Parent ( root, current ); virtual BinTreeNode *LeftChild ( BinTreeNode *current ) return root != NULL ? currentleftChild : NULL; virtual BinTreeNode *RightChild ( BinTre

8、eNode *current ) return root != NULL ? currentrightChild : NULL; virtual int Insert ( const Type & item); virtual int Find ( const Type &item ) const; const BinTreeNode *GetRoot ( ) const return root; friend istream &operator ( istream &in, BinaryTree &Tree ) friend ostream &operator ( ostream &out,

9、 BinaryTree &Tree )private: BinTreeNode *root; Type RefValue; 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

10、void destroy(BinTreeNode *current); template void BinaryTree: destroy ( BinTreeNode *current ) if ( current != NULL ) destroy ( currentleftChild ); destroy ( currentrightChild ); delete current; Template BinTreeNode *BinaryTree :Parent ( BinTreeNode *start, BinTreeNode *cuurent ) if ( start = NULL )

11、 return NULL; if ( startleftChild = current | startrightChild = current ) return start; BinTreeNode *p; if ( ( p = Parent ( startleftChild, current ) ) != NULL ) return p; else return Parent ( startrightChild, current );Template void BinaryTree:Traverse ( BinTreeNode *current, ostream &out ) const i

12、f ( current != NULL ) out currentdata ; Traverse ( currentleftChild, out ); Traverse ( currentrightChild, out ); Template istream & operator ( istream & in, BinaryTree &Tree ) Type item; cout 构造二叉树构造二叉树:n ; cout 输入数据输入数据 (用用 Tree.RefValue item; while ( item != Tree.RefValue ) Tree.Insert ( item ); c

13、out 输入数据输入数据 (用用 Tree.RefValue item; return in;Template ostream & operator ( ostream & out, BinaryTree &Tree ) out “二叉树的前序遍历二叉树的前序遍历.n; Tree.Traverse ( Tree.root, out ); out endl; return out; 二叉树递归的后序遍历算法二叉树递归的后序遍历算法template void BinaryTree :PostOrder ( ) PostOrder ( root );template void BinaryTree:

14、PostOrder ( BinTreeNode *current ) if ( current != NULL ) PostOrder ( currentleftChild ); PostOrder ( currentrightChild ); cout currentdata; 1、利用二叉树后序遍历计算二叉树结点个、利用二叉树后序遍历计算二叉树结点个数及二叉树的高度数及二叉树的高度 template int BinaryTree:Size ( const BinTreeNode *t ) const if ( t = NULL ) return 0; else return 1 + Siz

15、e ( tleftChild ) + Size ( trightChild );template int BinaryTree:Height ( const BinTreeNode *t ) const if ( t = NULL ) return -1; else return 1 + Max ( Height ( tleftChild ), Height ( trightChild ) );Template void BinaryTree:PreOrdere () StackTreenode * st; BinTreeNode * p=root; do while ( p ！=NULL)

16、cout( pdata ); S.Push( p); p=pleftchild; if ( st.IsEmpty()=0 ) p = S.getTop( ); st.Pop( ); p=p-rightchild /进右子树进右子树 while (p!=NULL|!st.Isempty() void InOrderTraverse ( Bitree T ) StackType S; BitreeNode * p; S.makeEmpty( ); p = T; /初始化初始化 do while ( p ) S.Push(p); p = pleftChild; if ( !S.IsEmpty( )

17、) /栈非空栈非空 p = S.getTop( ); S.Pop( ); /退栈退栈 printf ( pdata); /访问根结点访问根结点 p = prightChild; /向右链走向右链走 while ( p | !S.IsEmpty( ) ); , , 当当tag/R时时, 表示刚刚是在右子树中表示刚刚是在右子树中,在从右子树中在从右子树中退退/出时出时, 去访问位于栈顶的结点。去访问位于栈顶的结点。 ptr tag (LR) StackType S; BitreeNode * p; StackNode w; S.makeEmpty( ); p = T; /初始化初始化 do whi

18、le ( p ) w.ptr = p; w.tag = L; S.Push(w); p = pleftChild; /遍历左子树并把经过结点加左标志遍历左子树并把经过结点加左标志进栈进栈 int continue = 1; /继续循环继续循环标志标志 while ( continue & !S.IsEmpty( ) ) w = S.getTop( ); S.Pop( ); p = w.ptr; switch (w.tag) /判别栈顶的判别栈顶的tag标志标志 case L : w.tag = R; S.Push(w); continue = 0; /修正栈顶修正栈顶tag p = prigh

19、tChild; break; case R : printf (pdata); break; while ( p | !S.IsEmpty( ) ); 假设前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。bnnnnnnnnC111122()!6.4 6.4 线索化二叉树线索化二叉树6.4.1 线索 用于指示前驱与后继的指针，加了线索的二叉树叫线用于指示前驱与后继的指针，加了线索的二叉树叫线索化二叉树索化二叉树6.4 6.4 线索化二叉树线索化二叉树最小堆最小堆: :任一节点的关键码均小于或等于它的任一节点的关键码均小于或等于它的左、右子女的关键码，位于堆顶即完全二叉左、右子女的关键码

20、，位于堆顶即完全二叉树根结点位置的结点的关键码是整个集合中树根结点位置的结点的关键码是整个集合中最小的。最小的。最大堆最大堆: :任一节点的关键码均大于或等于它的任一节点的关键码均大于或等于它的左、右子女的关键码，位于堆顶即完全二叉左、右子女的关键码，位于堆顶即完全二叉树根结点位置的结点的关键码是整个集合中树根结点位置的结点的关键码是整个集合中最大的。最大的。6.5.1 6.5.1 堆的定义堆的定义定义定义图例CurrentSize = 0; int IsFull ( ) const return CurrentSize = MaxHeapSize; void MakeEmpty ( ) Cu

21、rrentSize = 0; private: enum DefaultSize = 10 ; Type *heap; int CurrentSize; int MaxHeapSize; void FilterDown ( int i, int m ); void FilterUp ( int i ); template MinHeap :MinHeap ( int maxSize ) /根据给定大小根据给定大小maxSize,建立堆对象建立堆对象 MaxHeapSize = DefaultSize maxSize ? maxSize : DefaultSize; /确定堆大小确定堆大小 he

22、ap = new Type MaxHeapSize; /创创建堆空间建堆空间 CurrentSize = 0; /初始化初始化template MinHeap : MinHeap ( Type arr , int n ) /根据给定数组中的数据和大小根据给定数组中的数据和大小,建立堆对象建立堆对象 算法：算法：template MinHeap : MinHeap ( Type arr , int n ) /根据给定数组中的数据和大小根据给定数组中的数据和大小,建立堆对象建立堆对象 MaxHeapSize = DefaultSize = 0 ) /从下到上逐渐扩展,构成堆 FilterDown

23、( currentPos, CurrentSize-1 ); /从currentPos开场,到CurrentSize为止, 调整 currentPos-; template void MinHeap: FilterDown ( const int start, const int EndOfHeap ) int i = start, j = 2*i+1; / j 是是 i 的左子女的左子女 Type temp = heapi; while ( j = EndOfHeap ) if ( j heapj+1.key ) j+;/两子女中选小者两子女中选小者 if ( temp.key = heap

24、j.key ) break; else heapi = heapj; i = j; j = 2*j+1; heapi = temp;自下向上逐渐伐整为最小堆自下向上逐渐伐整为最小堆算法：算法：template int MinHeap:Insert ( const Type &x ) /在堆中插入新元素在堆中插入新元素 x if ( CurrentSize = MaxHeapSize ) /堆满堆满 cout 堆已满堆已满 endl; return 0; heapCurrentSize = x; /插在表插在表尾尾 FilterUp (CurrentSize); /向上调向上调整为堆整为堆 Cu

25、rrentSize+; /堆元堆元素增一素增一 return 1;template void MinHeap:FilterUp ( int start ) /从从 start 开场开场,向上直到向上直到0,调整堆调整堆 int j = start, i = (j-1)/2; / i 是是 j 的的双亲双亲 Type temp = heapj; while ( j 0 ) if ( heapi.key = temp.key ) break; else heapj = heapi; j = i; i = (i -1)/2; heapj = temp;图例删除删除template int MinHe

26、ap :RemoveMin ( Type &x ) if ( !CurrentSize ) cout “ 堆已空堆已空 endl; return 0; x = heap0; /最小元素出最小元素出队列队列 heap0 = heapCurrentSize-1; CurrentSize-; /用最小元素用最小元素填补填补 FilterDown ( 0, CurrentSize-1 ); /从从0号位置开场自顶向下调整为堆号位置开场自顶向下调整为堆 return 1;树的广义表表示树的广义表表示 (结点的结点的utype域没有画出域没有画出) data child1child2 child3chil

27、dd datafirstChild nextSibling firstChild (fc), nextSibling firstChild (fc), nextSibling (ns) (ns) ;template class Tree public: Tree ( ) root = current = NULL; int Root(); int leftchild(); int RightSibling(); void RemovesubTree(TreeNode *p); void FindParent(TreeNode *t,TreeNode *p); private: TreeNode

28、 *root, *current; void PreOrder ( ostream & out, TreeNode *p ); int Find ( TypeNode *p, Type target ); void RemovesubTree ( TreeNode *p ); int FindParent ( TreeNode *t, *p );其右子树为其右子树为B (T2, T3, , Tn)，其中，其中，T2, T3, , Tn是除是除T1外其它树构成的森林。外其它树构成的森林。 current = p; /递归完递归完恢复当前结点恢复当前结点 visit ( ); /访问根结点访问根结

29、点 2、广度优先遍历、广度优先遍历按层次次序遍历树的算法按层次次序遍历树的算法template void Tree:LevelOrder ( ) QueueTreeNode* Qu ( DefaultSize ); if ( ! IsEmpty ( ) ) TreeNode *p = current; Qu.EnQueue ( current ); /根进队列 while ( !Qu.IsEmpty ( ) ) /队列不空 current = Qu.DeQueue ( ); visit ( ); /退出队列,访问 FirstChild ( ); /转向长子 while ( !IsEmpty ( ) ) /结点指针不空