其他數(shù)據(jù)結(jié)構(gòu)

1、 樹(shù)和森林的概念 二叉樹(shù) 二叉樹(shù)遍歷 二叉樹(shù)的計(jì)數(shù) 線(xiàn)索化二叉樹(shù) 堆 樹(shù)與森林 霍夫曼樹(shù) 第六章 樹(shù)與森林樹(shù)和森林的概念樹(shù)的定義 樹(shù)是由 n (n 0) 個(gè)結(jié)點(diǎn)組成的有限集合。如果 n = 0，稱(chēng)為空樹(shù)；如果 n 0，則 有一個(gè)特定的稱(chēng)之為根(root)的結(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)； 除根以外的其它結(jié)點(diǎn)劃分為 m (m 0) 個(gè) 互不相交的有限集合T0, T1, , Tm-1，每個(gè)集合又是一棵樹(shù)，并且稱(chēng)之為根的子樹(shù)。樹(shù)的特點(diǎn)每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。0層1層3層2層height= 3ACGBDEFKLHMIJ0層1層3層2層height= 3A

2、CGBDEFKLHMIJ結(jié)點(diǎn)結(jié)點(diǎn)的度分支結(jié)點(diǎn)葉結(jié)點(diǎn)子女雙親兄弟祖先子孫結(jié)點(diǎn)層次樹(shù)的度樹(shù)高度森林template class Tree /對(duì)象: 樹(shù)是由n(0)個(gè)結(jié)點(diǎn)組成的有限集/合。在類(lèi)界面中的position是樹(shù)中結(jié)點(diǎn)的/地址。在順序存儲(chǔ)方式下是下標(biāo)型, 在鏈/表存儲(chǔ)方式下是指針型。Type是樹(shù)結(jié)點(diǎn)中存放數(shù)據(jù)的類(lèi)型。public: Tree ( ); Tree ( ); 樹(shù)的抽象數(shù)據(jù)類(lèi)型 position Root ( ); BuildRoot ( const Type& value ); position FirstChild ( position p ); position NextSi

3、bling ( position p, position v ); position Parent ( position p ); Type GetData ( position p ); int InsertChild ( const position p, const Type &value ); int DeleteChild ( position p, int i );二叉樹(shù) (Binary Tree)二叉樹(shù)的定義二叉樹(shù)的五種不同形態(tài) 一棵二叉樹(shù)是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的、互不相交的二叉樹(shù)組成。LLRR性質(zhì)1 若二叉樹(shù)的層次

4、從0開(kāi)始, 則在二叉樹(shù)的第 i 層最多有 2i 個(gè)結(jié)點(diǎn)。(i 0) 證明用數(shù)學(xué)歸納法性質(zhì)2 高度為 h 的二叉樹(shù)最多有 2h+1-1個(gè)結(jié)點(diǎn)。(h -1) 證明用求等比級(jí)數(shù)前k項(xiàng)和的公式 20 + 21 + 22 + + 2h = 2h+1-1二叉樹(shù)的性質(zhì)性質(zhì)3 對(duì)任何一棵二叉樹(shù), 如果其葉結(jié)點(diǎn)有 n0 個(gè), 度為2的非葉結(jié)點(diǎn)有 n2 個(gè), 則有 n0n21證明：若設(shè)度為1的結(jié)點(diǎn)有 n1 個(gè)，總結(jié)點(diǎn)個(gè)數(shù)為 n，總邊數(shù)為 e，則根據(jù)二叉樹(shù)的定義， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n

5、0 - 1 n0 = n2 + 1 定義1 滿(mǎn)二叉樹(shù) (Full Binary Tree) 定義2 完全二叉樹(shù) (Complete Binary Tree) 若設(shè)二叉樹(shù)的高度為h，則共有h+1層。除第 h 層外，其它各層 (0 h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)。性質(zhì)4 具有 n (n 0) 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為 log2(n+1) -1 證明：設(shè)完全二叉樹(shù)的高度為 h，則有 2h - 1 n 2h+1 - 1變形 2h n+1 2h+1 取對(duì)數(shù) h 0, 則 i 的雙親為(i -1)/2 若2*i+1 n, 則 i 的左子女為 2*i+

6、1，若2*i+2 n, 則 i 的右子女為2*i+2 若 i 為偶數(shù), 且i != 0, 則其左兄弟為i-1, 若 i 為奇數(shù), 且i != n-1, 則其右兄弟為i+1 0123745689二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型template class BinaryTree public: BinaryTree ( ); /構(gòu)造函數(shù) BinaryTree ( BinTreeNode * lch, BinTreeNode * rch, Type item ); /構(gòu)造以item為根，lch和rch為左、右 /子樹(shù)的二叉樹(shù) int IsEmpty ( ); /判二叉樹(shù)空否？ BinTreeNode * Par

7、ent ( ); /雙親 BinTreeNode * LeftChild ( ); /取左子女結(jié)點(diǎn)地址 BinTreeNode * RightChild ( ); /取右子女結(jié)點(diǎn)地址 int Insert ( const Type& item ); /插入 int Find ( const Type &item ) const; /搜索 Type GetData ( ) const; /取得結(jié)點(diǎn)數(shù)據(jù) BinTreeNode *GetRoot ( ) const; /取根結(jié)點(diǎn)地址完全二叉樹(shù) 一般二叉樹(shù)的順序表示 的順序表示二叉樹(shù)的順序表示00 1 2 3 4 5 6 7 8 990 1 2 3

8、4 5 6 7 8 9137894562012543678二叉樹(shù)的鏈表表示leftChild data rightChilddataleftChildrightChild二叉鏈表二叉樹(shù)的鏈表表示leftChild data parent rightChildparentdataleftChildrightChild三叉鏈表二叉樹(shù)鏈表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉樹(shù) 二叉鏈表 三叉鏈表二叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdata parent leftChild rightChild012345A -1 1 -1B 0 2 3C 1 -1 -1D 1

9、 4 5E 3 -1 -1F 3 -1 -1template class BinaryTree;template Class BinTreeNode friend class BinaryTree;private: Type data; BinTreeNode * leftChild; BinTreeNode * rightChild; public: BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) 二叉樹(shù)的類(lèi)定義 BinTreeNode ( Type item, BinTreeNode *left = NULL, BinTreeNo

10、de *right = NULL ) : data (item), leftChild (left), rightChild (right) 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 ) leftChild =

11、 L; void SetRight ( BinTreeNode * R ) rightChild = R; ;template class BinaryTree private: BinTreeNode *root; Type RefValue; void CreateBinTree ( ifstream& in, BinTreeNode * & current ); BinTreeNode * Parent ( BinTreeNode * start, BinTreeNode * current ); int Insert ( BinTreeNode * & current, const T

12、ype &item ); /插入 void Traverse ( BinTreeNode *current, ostream &out ) const /遍歷 int Find ( BinTreeNode *current, const Type &item ) const/搜索 void destroy ( BinTreeNode * current ); /刪除public: virtual BinaryTree ( ) : root (NULL) virtual BinaryTree ( Type value ) : RefValue (value), root (NULL) virtu

13、al BinaryTree ( ) destroy ( root ); virtual int IsEmpty ( ) /判樹(shù)空否 return root = NULL ? 1 : 0; virtual BinTreeNode * Parent ( BinTreeNode *current ) return root = NULL | root = current？ NULL : Parent ( root, current ); /找current結(jié)點(diǎn)的雙親 virtual BinTreeNode * LeftChild ( BinTreeNode *current ) /取current結(jié)

14、點(diǎn)的左子女 return root != NULL ? current-leftChild : NULL; virtual BinTreeNode * RightChild ( BinTreeNode *current ) /取current結(jié)點(diǎn)的右子女 return root != NULL ? current-rightChild : NULL; virtual int Insert ( const Type& item); virtual BinTreeNode * Find ( const Type& item ) const; /搜索 BinTreeNode *GetRoot ( )

15、 const return root; /取根 friend istream& operator (filename, BinaryTree& Tree) /重載操作：輸入 friend ostream& operator (ostream&out, BinaryTree& Tree) /重載操作：輸出 二叉樹(shù)部分成員函數(shù)的實(shí)現(xiàn) template void BinaryTree : destroy ( BinTreeNode *current ) if ( current != NULL ) destroy ( current - leftChild ); destroy ( current

16、- rightChild ); delete current; template void BinaryTree : CreateBinTree ( ifstream& in, BinTreeNode * & current ) /私有函數(shù): 以遞歸方式建立二叉樹(shù)。/輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(jié)點(diǎn)前/序遍歷的順序。并約定以輸入序列中不可/能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,/此值在RefValue中。例如用“”或用“-1”/表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。 Type item; if ( !in.eof ( ) ) 如圖所示的二叉樹(shù)的前序遍歷順序?yàn)锳 B C D E G F ABCDEGF

17、 in item; /讀入根結(jié)點(diǎn)的值 if ( item != RefValue ) current = new BinTreeNode ( item );/建立根結(jié)點(diǎn) if ( current = NULL ) cerr “存儲(chǔ)分配錯(cuò)!” leftChild ); CreateBinTree ( in, current-rightChild ); else current = NULL; /封閉葉結(jié)點(diǎn) template BinTreeNode * BinaryTree : Parent ( BinTreeNode * start, BinTreeNode * cuurent ) if ( s

18、tart = NULL ) return NULL; if ( start-leftChild = current | start-rightChild = current ) return start; BinTreeNode *p; if ( p = Parent ( start-leftChild, current ) != NULL ) return p; else return Parent(start-rightChild, current);template void BinaryTree : Traverse ( BinTreeNode *current, ostream &o

19、ut ) const /私有函數(shù): 搜索并輸出根為current的二叉樹(shù) if ( current != NULL ) out data leftChild, out ); Traverse ( current-rightChild, out ); template istream& operator ( filename, BinaryTree & Tree ) /建立一棵二叉樹(shù)Tree。in是輸入流對(duì)象 Type item; ifstream fin (filename, /打開(kāi)文件 ios : in | ios : nocreate ); if ( !fin ) cerr “文件未發(fā)現(xiàn)!

20、” endl; exit (1); CreateBinTree ( ifstream& fin, root ); fin.close ( ); /關(guān)閉文件template ostream& operator ( ostream& out, BinaryTree &Tree ) out “二叉樹(shù)的前序遍歷.n; Tree.Traverse ( Tree.root, out ); out endl; return out;二叉樹(shù)遍歷 樹(shù)的遍歷就是按某種次序訪(fǎng)問(wèn)樹(shù)中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪(fǎng)問(wèn)一次且僅訪(fǎng)問(wèn)一次。 設(shè)訪(fǎng)問(wèn)根結(jié)點(diǎn)記作 V 遍歷根的左子樹(shù)記作 L 遍歷根的右子樹(shù)記作 R 則可能的遍歷次序有 前

21、序 VLR 鏡像 VRL 中序 LVR 鏡像 RVL 后序 LRV 鏡像 RLV 中序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則中序遍歷左子樹(shù) (L)；訪(fǎng)問(wèn)根結(jié)點(diǎn) (V)；中序遍歷右子樹(shù) (R)。遍歷結(jié)果 a + b * c - d - e / f中序遍歷 (Inorder Traversal)-/+*abcdef二叉樹(shù)遞歸的中序遍歷算法template void BinaryTree : InOrder ( BinTreeNode *current ) if ( current != NULL ) InOrder ( current-leftChild ); cout data;

22、InOrder ( current-rightChild ); 前序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則訪(fǎng)問(wèn)根結(jié)點(diǎn) (V)；前序遍歷左子樹(shù) (L)；前序遍歷右子樹(shù) (R)。遍歷結(jié)果 - + a * b - c d / e f前序遍歷 (Preorder Traversal)-/+*abcdef二叉樹(shù)遞歸的前序遍歷算法template void BinaryTree :PreOrder ( BinTreeNode * current ) if ( current != NULL ) cout data; PreOrder ( current-leftChild ); PreOrd

23、er ( current-rightChild ); 后序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則后序遍歷左子樹(shù) (L)；后序遍歷右子樹(shù) (R)；訪(fǎng)問(wèn)根結(jié)點(diǎn) (V)。遍歷結(jié)果 a b c d - * + e f / -后序遍歷 (Postorder Traversal)-/+*abcdef二叉樹(shù)遞歸的后序遍歷算法template void BinaryTree :PostOrder ( BinTreeNode * current ) if ( current != NULL ) PostOrder ( current-leftChild ); PostOrder ( current

24、-rightChild ); cout data; 利用二叉樹(shù)后序遍歷計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)及二叉樹(shù)的高度template int BinaryTree : Count ( const BinTreeNode * t ) const if ( t = NULL ) return 0; else return 1 + Count ( t-leftChild ) + Count ( t-rightChild );應(yīng)用二叉樹(shù)遍歷的事例template int BinaryTree : Height ( const BinTreeNode * t ) const if ( t = NULL ) retur

25、n -1; else return 1 + Max ( Height ( t-leftChild ), Height ( t-rightChild ) ); 利用棧的前序遍歷非遞歸算法abcdecdcc訪(fǎng)問(wèn)a進(jìn)棧c左進(jìn)b訪(fǎng)問(wèn)b進(jìn)棧d左進(jìn)空退棧d訪(fǎng)問(wèn)d左進(jìn)空退棧c訪(fǎng)問(wèn)c左進(jìn)e訪(fǎng)問(wèn)e左進(jìn)空棧空結(jié)束template void BinaryTree : PreOrder( ) stack TreeNode* S; BinTreeNode * p = root; /初始化 S.Push ( NULL ); while ( p != NULL ) cout data rightChild != NULL

26、) S.Push ( p-rightChild ); /預(yù)留右子樹(shù)指針在棧中利用棧的前序遍歷非遞歸算法if ( p-leftChild != NULL ) p = p-leftChild; /進(jìn)左子樹(shù) else p = S.getTop( ); S.Pop( ); /左子樹(shù)為空, 進(jìn)右子樹(shù) 利用棧的中序遍歷非遞歸算法template void BinaryTree : InOrder ( ) stack TreeNode* S; 利用棧的中序遍歷非遞歸算法abcdebaadaa左空退棧訪(fǎng)問(wèn)左空退棧訪(fǎng)問(wèn)退棧訪(fǎng)問(wèn)左空ec退棧訪(fǎng)問(wèn)cc右空退棧訪(fǎng)問(wèn) ?？战Y(jié)束 BinTreeNode * p = roo

27、t; /初始化 do while ( p != NULL ) S.Push(p); p = p-leftChild; if ( !S.IsEmpty( ) ) /棧非空 p = S.getTop( ); S.Pop( ); /退棧 cout data rightChild; /向右鏈走 while ( p != NULL | !S.IsEmpty( ) );利用棧的后序遍歷非遞歸算法后序遍歷時(shí)使用的棧的結(jié)點(diǎn)定義template struct stkNode BinTreeNode *ptr; enum tag L, R ; /該結(jié)點(diǎn)退棧標(biāo)記 stkNode( BinTreeNode* N =

28、NULL ) : ptr (N), tag ( L ) /構(gòu)造函數(shù); 根結(jié)點(diǎn)的tag = L，表示從左子樹(shù)退出, 訪(fǎng)問(wèn)右子樹(shù)。tag = R, 表示從右子樹(shù)退出, 訪(fǎng)問(wèn)根。ptr tagL,R abcdeaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaRtemplate void BinaryTree : PostOrder ( ) stack stkNode S; stkNode w; BinTreeNode * p = root; do while ( p != NULL ) /向左子樹(shù)走 w.ptr = p; w.tag = L; s

29、t.Push ( w ); p = p-leftChild; int continue = 1; /繼續(xù)循環(huán)標(biāo)記 while ( continue & !S.IsEmpty( ) ) w = st.getTop ( ); st.Pop ( ); p = w.ptr; switch ( w.tag ) /判斷棧頂tag標(biāo)記 case L : w.tag = R; st.Push ( w ); continue = 0; p = p-rightChild; break; case R : cout data endl; while ( p != NULL | !S.IsEmpty( ) ); co

30、ut endl; 二叉樹(shù)的計(jì)數(shù) 由二叉樹(shù)的前序序列和中序序列可唯一地確定一棵二叉樹(shù)。 例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 構(gòu)造二叉樹(shù)過(guò)程如下：HBDFEKCGAEKCGABHDFKCG前序序列 ABHFDECKG EKCGABHDFEKCGABHFDEABHFDEABHFDCKG 如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹(shù)。612345789612375849 固定前序排列,選擇所有可能的中序排列,可以可能構(gòu)造多少種不同的二叉樹(shù)？ 例如, 有 3 個(gè)數(shù)據(jù) 1, 2, 3 ，可得 5 種不同的二叉樹(shù)。它們的前序排列均為 123，中序序列可能是

31、 123，132，213，231，321。123123123123123 有0個(gè), 1個(gè), 2個(gè), 3個(gè)結(jié)點(diǎn)的不同二叉樹(shù)如下b0 =1b1 =1b2 =2b3 =5 b4 =14計(jì)算具有 n 個(gè)結(jié)點(diǎn)的不同二叉樹(shù)的棵數(shù)Catalan函數(shù)bibn-i-11線(xiàn)索化二叉樹(shù) (Threaded Binary Tree)線(xiàn)索 (Thread)增加 Pred 指針和 Succ 指針的二叉樹(shù)線(xiàn)索化二叉樹(shù)及其二叉鏈表表示LeftThread=0, LeftChild為左子女指針LeftThread=1, LeftChild為前驅(qū)線(xiàn)索RightThread=0, RightChild為右子女指針RightThre

32、ad=1, RightChild為后繼指針LeftChildRightChilddataLeftThreadRightThread中序線(xiàn)索化二叉樹(shù)的類(lèi)定義template class ThreadTree; template class ThreadNode friend class ThreadTree;private: int leftThread, rightThread; ThreadNode *leftChild, *rightChild; Type data;public: ThreadNode ( const Type item ) : data (item), leftChil

33、d (NULL), rightChild (NULL), leftThread (0), rightThread (0) ;template class ThreadTree private: ThreadNode * root; /根 InThread ( ThreadNode * current, ThreadNode * pre ); /建樹(shù)public: ThreadTree ( ) : root (NULL) ; /構(gòu)造函數(shù) ThreadNode * First ( ThreadNode * current ); ThreadNode * Last ( ThreadNode * cu

34、rrent ); ThreadNode * Next ( ThreadNode * current ); ThreadNode * Prior ( ThreadNode * current ); 通過(guò)中序遍歷建立中序線(xiàn)索化二叉樹(shù)template void ThreadTree :InThread ( ThreadNode * current, ThreadNode *& pre ) if ( current != NULL ) InThread ( current-leftChild, pre ); /遞歸, 左子樹(shù)線(xiàn)索化 if ( current-leftChild = NULL ) cur

35、rent-leftChild = pre; current-leftThread = 1; /建立當(dāng)前結(jié)點(diǎn)的前驅(qū)線(xiàn)索 if ( pre != NULL & pre-rightChild = NULL ) pre-rightChild = current; pre-rightThread = 1; /建立前驅(qū)結(jié)點(diǎn)的后繼線(xiàn)索pre = current;/前驅(qū)跟上當(dāng)前指針I(yè)nThread ( current-rightChild, pre ); /遞歸, 右子樹(shù)線(xiàn)索化 template voidThreadTree : CreateInThread ( ) ThreadNode *pre = NUL

36、L; /前驅(qū)指針 if ( root != NULL ) /非空二叉樹(shù), 線(xiàn)索化 InThread ( root, pre ); /中序遍歷線(xiàn)索化二叉樹(shù) pre-rightChild = NULL; pre-rightThread = 1; /后處理, 中序最后一個(gè)結(jié)點(diǎn) 0 A 0 0 B 0 0 C 0 0 D 0 0 E 0 rootpre = NULLcurrent0 A 0 1 B 0 0 C 0 0 D 0 0 E 0 rootpre = NULLcurrent0 A 0 1 B 0 0 C 0 1 D 0 0 E 0 rootprecurrent0 A 0 1 B 0 0 C 0

37、1 D 1 0 E 0 rootprecurrent0 A 0 1 B 0 0 C 0 1 D 1 1 E 0 rootprecurrent0 A 0 1 B 0 0 C 0 1 D 1 1 E 1 rootprecurrent0 A 0 1 B 0 0 C 1 1 D 1 1 E 1 rootpre后處理 if (p-rightThread =1) if (p-rightChild != NULL) 后繼為 p-rightChild else 無(wú)后繼 else /p-rightThread != 1 if (p-rightChild != NULL) 后繼為當(dāng)前結(jié)點(diǎn)右子樹(shù) 的中序下的第一個(gè)結(jié)

38、點(diǎn) else 出錯(cuò)情況 尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼ABDECFHIKGJ if (current-leftThread=1) if (current-leftChild != NULL) 前驅(qū)為current-leftChild else 無(wú)前驅(qū) else /current-leftThread=0 if (current-leftChild != NULL) 前驅(qū)為當(dāng)前結(jié)點(diǎn)左子樹(shù) 中序下的最后一個(gè)結(jié)點(diǎn) else 出錯(cuò)情況 尋找當(dāng)前結(jié)點(diǎn)在中序下的前驅(qū)ABDECFHIKGJL在中序線(xiàn)索化二叉樹(shù)中部分成員函數(shù)的實(shí)現(xiàn)template ThreadNode * ThreadTree : First (

39、 ThreadNode * current ) /函數(shù)返回以*current為根在線(xiàn)索化二叉樹(shù)中/的中序序列下的第一個(gè)結(jié)點(diǎn) ThreadNode * p = current; while ( p-leftThread = 0 ) p = p-leftChild;/最左下的結(jié)點(diǎn) return p;template ThreadNode * ThreadTree : Next ( ThreadNode * current ) /函數(shù)返回在線(xiàn)索化二叉樹(shù)中結(jié)點(diǎn)*current在/中序下的后繼結(jié)點(diǎn) ThreadNode *p = current-rightChild; if ( current-righ

40、tThread = 0 ) return First ( p ); /rightThread = 0, 表示有右子女 else return p;/rightThread = 1, 直接返回后繼線(xiàn)索 template void ThreadTree : Inorder ( ) /線(xiàn)索化二叉樹(shù)的中序遍歷 ThreadNode * p; for ( p = First ( ); p != NULL; p = Next ( ) ) cout data leftThread=1?前驅(qū)線(xiàn)索 = 左子女p-rightChild = NULL后繼為p-leftChild=無(wú)后繼 后繼為p-rightChil

41、dABCED后序線(xiàn)索化二叉樹(shù)后序序列 D B E C A在前序線(xiàn)索化二叉樹(shù)中尋找當(dāng)前結(jié)點(diǎn)的后繼p-rightThread=1?后繼線(xiàn)索 = 右子女后繼為q的右子樹(shù)中后序下第一個(gè)結(jié)點(diǎn) 后繼為p-leftChild=無(wú)后繼 后繼為qABCEDq=p-parentq=NULL?Q-rightThread=1 |q-rightChild=p?=堆 ( Heap )template class MinPQ public: Virtual void Insert ( const Type & ) = 0; Virtual Type *RemoveMin ( Type & ) = 0; 最小優(yōu)先級(jí)隊(duì)列類(lèi)的定

42、義優(yōu)先級(jí)隊(duì)列 每次出隊(duì)列的是優(yōu)先權(quán)最高的元素完全二叉樹(shù) 數(shù)組表示Ki K2i+1 & Ki K2i+2完全二叉樹(shù) 數(shù)組表示Ki K2i+1 & Ki K2i+2堆的定義090987877878454565653131532323531717最小堆的類(lèi)定義#define DefaultSize 10;template class MinHeap : public MinPQ private: Type * heap; /存放最小堆元素的數(shù)組 int CurrentSize; /最小堆當(dāng)前元素個(gè)數(shù) int MaxHeapSize; /最多允許元素個(gè)數(shù) void FilterDown ( int i

43、, int m ); /從 i 到m自頂向下進(jìn)行調(diào)整成為最小堆 void FilterUp ( int i ); /從 i 到0自底向上進(jìn)行調(diào)整成為最小堆public: MinHeap ( int sz ); /構(gòu)造函數(shù) : 建立空堆 MinHeap ( Type arr , int n ); /構(gòu)造函數(shù) MinHeap ( ) delete heap; const MinHeap& operator = ( const MinHeap& R ); int Insert ( const Type& x ); /插入 int RemoveMin ( Type& x ); /刪除 int IsEm

44、pty ( ) const /判堆空否 return CurrentSize = 0; int IsFull ( ) const /判堆滿(mǎn)否 return CurrentSize = MaxHeapSize; void MakeEmpty ( ) CurrentSize = 0; 堆的建立template MinHeap :MinHeap ( int maxSize ) /根據(jù)給定大小maxSize,建立堆對(duì)象 MaxHeapSize = DefaultSize maxSize ? maxSize : DefaultSize; /確定堆的大小 heap = new Type MaxHeapSi

45、ze; if ( heap = NULL ) cerr “存儲(chǔ)分配錯(cuò)!” endl; exit(1); CurrentSize = 0; template MinHeap : MinHeap ( Type arr , int n ) /根據(jù)給定數(shù)組中的數(shù)據(jù)和大小,建立堆對(duì)象 MaxHeapSize = DefaultSize n ? n : DefaultSize; heap = new Type MaxHeapSize; if ( heap = NULL ) cerr “存儲(chǔ)分配錯(cuò)!” = 0 ) /從下到上逐步擴(kuò)大,形成堆 FilterDown ( currentPos, CurrentS

46、ize-1 ); /從currentPos開(kāi)始,到CurrentSize止, /調(diào)整 currentPos-; 自下向上逐步調(diào)整為最小堆將一組用數(shù)組存放的任意數(shù)據(jù)調(diào)整成堆5353171778780923456587i0923456587currentPos = i = 3currentPos = i = 2i5353171778780923456587i0923456587currentPos = i = 1i5353171778780923456587i0923456587currentPos = i = 0i095353171778780923456587i0923456587i17最小堆

47、的向下調(diào)整算法template void MinHeap : FilterDown ( int start, 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 = heapj.key ) break; else heapi = heapj; /下面的上浮 i = j; j = 2*j+1; /向下滑動(dòng) heapi = temp; 堆的插入template

48、int MinHeap : Insert ( const Type &x ) /在堆中插入新元素 x if ( CurrentSize = MaxHeapSize ) /堆滿(mǎn) cerr 堆已滿(mǎn) endl; return 0; heapCurrentSize = x; /插在表尾 FilterUp (CurrentSize); /向上調(diào)整為堆 CurrentSize+; /堆元素增一 return 1;最小堆的向上調(diào)整算法template void MinHeap : FilterUp ( int start ) /從 start 開(kāi)始,向上直到0,調(diào)整堆 int j = start, i =

49、(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;53171778780923456587i0923456587j11在堆中插入新元素1153j1123i最小堆的向上調(diào)整5317117878094565870923456587j115323i2317ji最小堆的刪除算法template int MinHeap :RemoveMin ( Type &x ) if

50、( !CurrentSize ) cout “ 堆已空 endl; return 0; x = heap0; /最小元素出隊(duì)列 heap0 = heapCurrentSize-1; CurrentSize-; /用最小元素填補(bǔ) FilterDown ( 0, CurrentSize-1 ); /調(diào)整 return 1;樹(shù)的存儲(chǔ)表示 廣義表表示樹(shù)的廣義表表示 (結(jié)點(diǎn)的utype域沒(méi)有畫(huà)出)樹(shù)與森林ABCDEFGABEFCDG 雙親表示ABCDEFGdataparentA B C D E F G-1 0 0 0 1 1 30 1 2 3 4 5 6 左子女-右兄弟表示法第一種解決方案 data c

51、hild1child2child3childd第二種解決方案樹(shù)的左子女 - 右兄弟表示 datafirstChildnextSiblingABCDEFGABCDGFE用左子女-右兄弟表示實(shí)現(xiàn)的樹(shù)的類(lèi)定義template class Tree;template class TreeNode friend class Tree;private: Type data; TreeNode *firstChild, *nextSibling;public: TreeNode ( Type value=0, TreeNode *fc=NULL, TreeNode *ns=NULL ) : data (va

52、lue), firstChild (fc), nextSibling (ns) ; template class Tree private: TreeNode *root, *current; /根指針及當(dāng)前指針 void PreOrder ( ostream& out, TreeNode *p ); /先根次序遍歷并輸出以 p 為根的樹(shù) int Find ( TreeNode *p, Type target ); void RemovesubTree (TreeNode * p); /刪除以 p 為根的子樹(shù) int FindParent ( TreeNode * t, TreeNode *

53、p ); /在樹(shù) t 中搜索結(jié)點(diǎn) p 的雙親public: Tree ( ) root = current = NULL; int Root ( ); int FirstChild ( ); int NextSibling ( ); int Parent ( ); int Find ( Type target ); /樹(shù)的其它公共操作template int Tree : Root ( ) /讓樹(shù)的根結(jié)點(diǎn)成為樹(shù)的當(dāng)前結(jié)點(diǎn) if ( root = NULL ) current = NULL; return 0; else current = root; return 1; template in

54、t Tree : Parent ( ) /在樹(shù)中找當(dāng)前結(jié)點(diǎn)的雙親, 成為當(dāng)前結(jié)點(diǎn) TreeNode * p = current, *t; if ( current = NULL | current = root ) current = NULL; return 0; /空樹(shù)或根為當(dāng)前結(jié)點(diǎn), 返回0 t = root; int k = FindParent ( t, p ); /從t找p雙親 return k;template int Tree : FindParent ( TreeNode *t, TreeNode *p ) /在根為 t 的樹(shù)中找 p 的雙親, 成為當(dāng)前結(jié)點(diǎn) TreeNode

55、 *q = t-firstChild; while ( q != NULL & q != p ) /循根的長(zhǎng)子的兄弟鏈,遞歸在子樹(shù)中搜索 if ( int i = FindParent (* q,* p) ) != 0 ) return i; q = q-nextSibling; if ( q != NULL & q =p ) current = t; return 1; else return 0; /未找到雙親,當(dāng)前結(jié)點(diǎn)不變template int Tree : FirstChild ( ) /在樹(shù)中找當(dāng)前結(jié)點(diǎn)的長(zhǎng)子,成為當(dāng)前結(jié)點(diǎn) if (current != NULL & current

56、-firstChild != NULL ) current = currentfirstChild; return 1; current = NULL; return 0;template int Tree : NextSibling ( ) /在樹(shù)中找當(dāng)前結(jié)點(diǎn)的兄弟,成為當(dāng)前結(jié)點(diǎn) if ( current != NULL & current-nextSibling != NULL ) current = current-nextSibling; return 1; current = NULL; return 0;template int Tree : Find ( Type target

57、) if ( IsEmpty ( ) ) return 0; return Find ( root, target );template int Tree :Find ( TreeNode * p, Type target ) /在根為 p 的樹(shù)中找值為 target 的結(jié)點(diǎn), 找到/后該結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn),否則當(dāng)前結(jié)點(diǎn)不變。/函數(shù)返回成功標(biāo)志：=1, 成功; =0, 失敗 int result = 0; if ( p-data = target ) result = 1; current = p; /搜索成功 else /搜索失敗 TreeNode *q = p-firstChild; whi

58、le ( q != NULL & ! ( result = Find ( q, target ) ) ) q = q-nextSibling; return result;森林與二叉樹(shù)的轉(zhuǎn)換森林與二叉樹(shù)的對(duì)應(yīng)關(guān)系T1 T2 T3AFHT1 T2 T3ABCDGIJEKFBCDEGHIKJABCEDHIKJFG3 棵樹(shù)的森林各棵樹(shù)的二叉樹(shù)表示森林的二叉樹(shù)表示(1) 森林轉(zhuǎn)化成二叉樹(shù)的規(guī)則 若 F 為空，即 n = 0，則 對(duì)應(yīng)的二叉樹(shù) B 為空二叉樹(shù)。 若 F 不空，則 對(duì)應(yīng)二叉樹(shù) B 的根 root (B) 是 F 中第一棵樹(shù) T1 的根 root (T1)； 其左子樹(shù)為 B (T11, T1

59、2, , T1m)，其中，T11, T12, , T1m 是 root (T1) 的子樹(shù)； 其右子樹(shù)為 B (T2, T3, , Tn)，其中，T2, T3, , Tn 是除 T1 外其它樹(shù)構(gòu)成的森林。(2) 二叉樹(shù)轉(zhuǎn)換為森林的規(guī)則 如果 B 為空，則對(duì)應(yīng)的森林 F 也為空。 如果 B 非空，則 F 中第一棵樹(shù) T1 的根為 root； T1 的根的子樹(shù)森林 T11, T12, , T1m 是由 root 的左子樹(shù) LB 轉(zhuǎn)換而來(lái)，F(xiàn) 中除了 T1 之外其余的樹(shù)組成的森林 T2, T3, , Tn 是由 root 的右子樹(shù) RB 轉(zhuǎn)換而成的森林。樹(shù)的二叉樹(shù)表示樹(shù)的遍歷深度優(yōu)先遍歷 先根次序遍歷

60、 后根次序遍歷廣度優(yōu)先遍歷ABCEDABCDEFGGF(1) 樹(shù)的先根次序遍歷的遞歸算法template void Tree : PreOrder ( ) /以當(dāng)前指針current為根, 先根次序遍歷 if ( IsEmpty ( ) = 0 ) visit ( ); /訪(fǎng)問(wèn)根結(jié)點(diǎn) TreeNode *p = current; current = current -firstChild; /第一棵子樹(shù) while ( current != NULL ) PreOrder ( ); /遞歸先根遍歷子樹(shù) current = current -nextSibling; current = p;/恢