【導(dǎo)讀】有一個(gè)特定的稱之為根的結(jié)點(diǎn)，它。除根以外的其它結(jié)點(diǎn)劃分為m(m?個(gè)互不相交的有限集合T0,T1,…集合又是一棵樹，并且稱之為根的子樹。驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。在類界面中的position是樹中結(jié)點(diǎn)的。在順序存儲(chǔ)方式下是下標(biāo)型,在鏈。中存放數(shù)據(jù)的類型。樹的第i層最多有2i個(gè)結(jié)點(diǎn)。若設(shè)二叉樹的高度為h，則共有h+1層。除第h層外，其它各層(0?若干結(jié)點(diǎn)，這就是完全二叉樹。頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)0,,n-1，則有以下關(guān)系：。若2*i+1<n,則i的左子女為2*i+1，若i為偶數(shù),且i!intIsEmpty();//判二叉樹空否？

　　

【正文】 heap[j].key ) break。 else { heap[i] = heap[j]。 //下面的上浮 i = j。 j = 2*j+1。 //向下滑動(dòng) } } heap[i] = temp。 } 堆的插入 template class Type int MinHeapType :: Insert ( const Type amp。x ) { //在堆中插入新元素 x if ( CurrentSize == MaxHeapSize ) //堆滿 { cerr 堆已滿 endl。 return 0。 } heap[CurrentSize] = x。 //插在表尾 FilterUp (CurrentSize)。 //向上調(diào)整為堆 CurrentSize++。 //堆元素增一 return 1。 } 最小堆的向上調(diào)整算法 template class Type void MinHeapType :: FilterUp ( int start ) { //從 start 開始 ,向上直到 0,調(diào)整堆 int j = start, i = (j1)/2。 // i 是 j 的雙親 Type temp = heap[j]。 while ( j 0 ) { if ( heap[i].key = ) break。 else { heap[j] = heap[i]。 j = i。 i = (i 1)/2。} } heap[j] = temp。 } 53 17 17 78 78 09 23 45 65 87 i 09 23 45 65 87 j 11 在堆中插入新元素 11 53 j 11 23 i 最小堆的向上調(diào)整 53 17 11 78 78 09 45 65 87 09 23 45 65 87 j 11 53 23 i 23 17 j i 最小堆的刪除算法 template class Type int MinHeap Type :: RemoveMin ( Type amp。x ) { if ( !CurrentSize ) { cout “ 堆已空 endl。 return 0。 } x = heap[0]。 //最小元素出隊(duì)列 heap[0] = heap[CurrentSize1]。 CurrentSize。 //用最小元素填補(bǔ) FilterDown ( 0, CurrentSize1 )。 //調(diào)整 return 1。 } 樹的存儲(chǔ)表示 ? 廣義表表示 樹的廣義表表示 (結(jié)點(diǎn)的 utype域沒有畫出 ) 樹與森林 A B C D E F G A B E F C D G ? 雙親表示 A B C D E F G data parent A B C D E F G 1 0 0 0 1 1 3 0 1 2 3 4 5 6 ? 左子女 右兄弟表示法 第一種解決方案 data child1 child2 child3 childd 第二種解決方案 樹的左子女 右兄弟表示 data firstChild nextSibling A B C D E F G A B C D G F E 用左子女 右兄弟表示實(shí)現(xiàn)樹的類定義 template class Type class Tree。 template class Type class TreeNode { friend classType Tree。 private: Type data。 TreeNodeType *firstChild, *nextSibling。 public: TreeNode ( Type value=0, TreeNodeType *fc=NULL, TreeNodeType *ns=NULL ) : data (value), firstChild (fc), nextSibling (ns) { } }。 template class Type class Tree { private: TreeNodeType *root, *current。 //根指針及當(dāng)前指針 void PreOrder ( ostreamamp。 out, TreeNodeType *p )。 //先根次序遍歷并輸出以 p 為根的樹 int Find ( TreeNodeType *p, Type target )。 void RemovesubTree (TreeNodeType * p)。 //刪除以 p 為根的子樹 int FindParent ( TreeNodeType * t, TreeNodeType * p )。 //在樹 t 中搜索結(jié)點(diǎn) p 的雙親 public: Tree ( ) { root = current = NULL。 } int Root ( )。 int FirstChild ( )。 int NextSibling ( )。 int Parent ( )。 int Find ( Type target )。 //樹的其它公共操作 …… } template class Type int Tree Type :: Root ( ) { //讓樹的根結(jié)點(diǎn)成為樹的當(dāng)前結(jié)點(diǎn) if ( root == NULL ) { current = NULL。 return 0。 } else { current = root。 return 1。 } } template class Type int TreeType :: Parent ( ) { //在樹中找當(dāng)前結(jié)點(diǎn)的雙親 , 成為當(dāng)前結(jié)點(diǎn) TreeNodeType * p = current, *t。 if ( current == NULL || current == root ) { current = NULL。 return 0。 } //空樹或根為當(dāng)前結(jié)點(diǎn) , 返回 0 t = root。 int k = FindParent ( t, p )。 //從 t找 p雙親 return k。 } template class Type int TreeType :: FindParent ( TreeNodeType *t, TreeNodeType *p ) { //在根為 t 的樹中找 p 的雙親 , 成為當(dāng)前結(jié)點(diǎn) TreeNodeType *q = tfirstChild。 while ( q != NULL amp。amp。 q != p ) { //循環(huán)根的長(zhǎng)子的兄弟鏈 ,遞歸在子樹中搜索 if (( int i = FindParent (* q,* p) ) != 0 ) return i。 q = qnextSibling。 } if ( q != NULL amp。amp。 q ==p ) { current = t。 return 1。 } else return 0。 //未找到雙親 ,當(dāng)前結(jié)點(diǎn)不變 } template class Type int Tree Type :: FirstChild ( ) { //在樹中找當(dāng)前結(jié)點(diǎn)的長(zhǎng)子 ,成為當(dāng)前結(jié)點(diǎn) if (current != NULL amp。amp。 currentfirstChild != NULL ) { current = current→firstChild 。 return 1。 } current = NULL。 return 0。 } template class Type int Tree Type :: NextSibling ( ) { //在樹中找當(dāng)前結(jié)點(diǎn)的兄弟 ,成為當(dāng)前結(jié)點(diǎn) if ( current != NULL amp。amp。 currentnextSibling != NULL ) { current = currentnextSibling。 return 1。 } current = NULL。 return 0。 } template class Type int TreeType :: Find ( Type target ) { if ( IsEmpty ( ) ) return 0。 return Find ( root, target )。 } template class Type int Tree Type:: Find ( TreeNode Type * p, Type target ) { //在根為 p 的樹中找值為 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 ( pdata == target ) { result = 1。 current = p。 } //搜索成功 else //搜索失敗 { TreeNodeType *q = pfirstChild。 while ( q != NULL amp。amp。 ! ( result = Find ( q, target ) ) ) q = qnextSibling。 } return result。 } 森林與二叉樹的轉(zhuǎn)換 森林與二叉樹的對(duì)應(yīng)關(guān)系 T1 T2 T3 A F H T1 T2 T3 A B C D G I J E K F B C D E G H I K J A B C E D H I K J F G 3 棵樹的森林 各棵樹的二叉樹表示 森林的二叉樹表示 (1) 森林轉(zhuǎn)化成二叉樹的規(guī)則 ? 若 F 為空 ，即 n = 0，則 對(duì)應(yīng)的 二叉樹 B 為 空二叉樹 。 ? 若 F 不空 ，則 對(duì)應(yīng) 二叉樹 B 的根 root (B) 是 F 中 第一棵樹 T1 的根 root (T1)； 其 左子樹 為 B (T11, T12, …, T 1m)，其中，T11, T12, …, T 1m 是 root (T1) 的子樹； 其 右子樹 為 B (T2, T3, …, T n)，其中， T2, T3, …, T n 是除 T1 外 其它樹構(gòu)成的森林 。 (2) 二叉樹轉(zhuǎn)換為森林的規(guī)則 ? 如果 B 為空，則對(duì)應(yīng)的 森林 F 也為空。 ? 如果 B 非空，則 F 中 第一棵樹 T1 的根為 root； T1 的根的子樹森林 { T11, T12, …,