樹和森林的概念二叉樹二叉樹遍歷二叉樹的計數線索化二叉-資料下載頁

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

　　

【正文】 heap[j].key ) break。 else { heap[i] = heap[j]。 //下面的上浮 i = j。 j = 2*j+1。 //向下滑動 } } 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)。 //向上調整為堆 CurrentSize++。 //堆元素增一 return 1。 } 最小堆的向上調整算法 template class Type void MinHeapType :: FilterUp ( int start ) { //從 start 開始 ,向上直到 0,調整堆 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 最小堆的向上調整 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]。 //最小元素出隊列 heap[0] = heap[CurrentSize1]。 CurrentSize。 //用最小元素填補 FilterDown ( 0, CurrentSize1 )。 //調整 return 1。 } 樹的存儲表示 ? 廣義表表示 樹的廣義表表示 (結點的 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 用左子女 右兄弟表示實現樹的類定義 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。 //根指針及當前指針 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 中搜索結點 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 ( ) { //讓樹的根結點成為樹的當前結點 if ( root == NULL ) { current = NULL。 return 0。 } else { current = root。 return 1。 } } template class Type int TreeType :: Parent ( ) { //在樹中找當前結點的雙親 , 成為當前結點 TreeNodeType * p = current, *t。 if ( current == NULL || current == root ) { current = NULL。 return 0。 } //空樹或根為當前結點 , 返回 0 t = root。 int k = FindParent ( t, p )。 //從 t找 p雙親 return k。 } template class Type int TreeType :: FindParent ( TreeNodeType *t, TreeNodeType *p ) { //在根為 t 的樹中找 p 的雙親 , 成為當前結點 TreeNodeType *q = tfirstChild。 while ( q != NULL amp。amp。 q != p ) { //循環根的長子的兄弟鏈 ,遞歸在子樹中搜索 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。 //未找到雙親 ,當前結點不變 } template class Type int Tree Type :: FirstChild ( ) { //在樹中找當前結點的長子 ,成為當前結點 if (current != NULL amp。amp。 currentfirstChild != NULL ) { current = current→firstChild 。 return 1。 } current = NULL。 return 0。 } template class Type int Tree Type :: NextSibling ( ) { //在樹中找當前結點的兄弟 ,成為當前結點 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 的結點 , 找到 //后該結點成為當前結點 ,否則當前結點不變 。 //函數返回成功標志 ： =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。 } 森林與二叉樹的轉換 森林與二叉樹的對應關系 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) 森林轉化成二叉樹的規則 ? 若 F 為空 ，即 n = 0，則 對應的 二叉樹 B 為 空二叉樹 。 ? 若 F 不空 ，則 對應 二叉樹 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 外 其它樹構成的森林 。 (2) 二叉樹轉換為森林的規則 ? 如果 B 為空，則對應的 森林 F 也為空。 ? 如果 B 非空，則 F 中 第一棵樹 T1 的根為 root； T1 的根的子樹森林 { T11, T12, …,