【文章內(nèi)容簡介】 inorder( p right ) } } * + a / d * b c e f ＊ ＋ a / b c d * e f ? 后序遍歷過程是： 得到表達式的表達式的逆波蘭表示式（運算符在兩個運算分量之后）。 后序遍歷算法是： void postorder (treepointer p) { /*后序遍歷 */ if ( p!=NULL ) { postorder( p left ) 。 postorder( p right ) printf(―%c‖ , p data ) 。 } } * + a / d * b c e f ＊ ＋ a / b c d * e f ? 檢索 檢索是按給定關鍵字值 c 在樹上找一個結點 ti ，且 ti 的關鍵字值 key 恰好等于 c 。若檢索到，函數(shù)將帶回相應結點指針；否則若沒檢索到，函數(shù)將帶回 NULL 。下述檢索算法的前提條件是， p 是檢索樹。 treepointer search( typekey c , treepointer p ) { if ( ( p key == c ) || ( p == NULL ) ) return p 。 else if ( c p key ) return search( c , p left ) 。 else return search( c , p right ) 。 } ? 插入一個結點 插入是指將一個數(shù)據(jù)項插入到樹中某一恰當位置，使樹仍保持檢索樹的性質(zhì)。顯然，首先要按 key值查出應該插入的位置，然后再插入。 void insert( keytype c , datatype d , treepointer *p ) { if ( *p == NULL ) { *p = (treepointer)malloc(sizeof(struct tree))。 (*p) key = c 。 (*p) data = d 。 (*p) left = NULL 。 (*p) right = NULL 。 }else if ( c (*p) key ) insert( c , d , amp。((*p)left) ) 。 else insert( c , d , amp。((*p)right) ) 。 } 由于 insert 的參數(shù) p 是指向指針的指針類型，在 insert 內(nèi) p 指向 指針類型的實在參數(shù) 。所以在執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)) 時，將使實在參數(shù)指針變量指向新申請來的結點。 1) 若調(diào)用 insert 時，如圖 root 為空樹。 以 amp。root 作實在參數(shù)調(diào)用 insert , 即 insert(c,d,amp。root) insert 的形式參數(shù) p 指向 root ，而 root 值為 NULL。 轉(zhuǎn)插入功能，執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)) 得 : 再執(zhí)行后邊的幾個賦值語句 , 得 : root: c 。 d p: 2) 若調(diào)用 insert時， root非空，在中間某一個結點查到空指 針，如圖；設查到該結點后，應該繼續(xù)向右查，以 amp。((*p)right) 作實在參數(shù)遞歸調(diào)用 insert，即執(zhí)行 insert(c,d, amp。((*p)right) ) insert 的形式參數(shù) p 指向本步的 (*p) right ，而 (*p) right 值為 NULL。 轉(zhuǎn)插入功能，執(zhí)行 *p=(treepointer)malloc(sizeof(struct tree)) 再執(zhí)行后邊的幾個賦值語句 , 得 : c 。 d ... ... p: ?刪除一結點 設欲刪除結點為 r，則可能有如下幾種情況。針對不同情況刪除算法不同 . r 是葉結點 :簡單刪掉 r 結點，并把 r 的父結點連接處改成 NULL 即可 。 4 2 5 1 3 r: r 只有一個左子樹 7 8 5 6 3 1 2 4 r: 7 8 5 6 4 2 3 1 r: r 只有一個子樹 : 把 r 以下部分接入 r 的父結點連接 r 處。 然后刪掉 r結點 。 r 只有一個右子樹 r 兩個方向都有子樹 : 在 r 的左子樹上找到關鍵字 key 值最大的結點 s，把 s 結點的數(shù)據(jù) data及關鍵字 key 復制到 r 結點上，然后刪除掉 s 結點。 9 s: 10 r: 4 5 14 15 12 13 3 1 2 11 8 6 7 9當然也可以在 r的右子樹上找到關鍵字 key值最小的結點s，把 s結點的數(shù)據(jù) data及關鍵字 key復制到 r結點上，然后刪除掉 s結點。 8 s: 5 r: 4 10 13 14 11 12 3 1 2 9 7 6 6使用在左子樹上找最大結點的方法，按如下步驟進行 : ① 沿 r 左子樹的右方向，向下找一個沒有 右子樹的結點 s ，圖中結點 (9) 。 ② 把該結點 s 的值復制到結點 r（即欲刪除 的結點。 ③ 把 s 的左子樹連在 s 的父結點（圖中為 結點 (5) ）的右鏈上，在圖中即連到 (5) 結點的右鏈上。 ④ 刪除 s結點，即圖中的 (9)結點。 圖 3的情況 r 兩個方向都有子樹 : 在 r 的左子樹上找到關鍵字 key 值最大的結點 s，把 s 結點的數(shù)據(jù) data及關鍵字 key 復制到 r 結點 上，然后刪除掉 s 結點。 9 s: 10 r: 4 5 14 15 12 13 3 1 2 11 8 6 7 9 綜合上述三種情況，下述函數(shù) deletenode 完成刪除一個結點。 deletenode的調(diào)用形式是： deletenode( valueofkey , amp。root ) 其中 ? value_of_key是欲刪除結點的關鍵字值； ? root是指針類型（ treepointer）變量，指向樹根。這里 用指向指針的指針作參數(shù)。 treepointer del( treepointer * , treepointer * )； /* 處理第三種情況的函數(shù)的函數(shù)原型 */ void deletenode( keytype c , treepointer *p ) { /* 刪除關鍵字值等于 c 的結點 */ treepointer r。 if ( *p == NULL ) printf( ―not found:%d\n‖ , c )。 else if ( c (*p) key ) /* c 當前結點的 key 值，被刪結點在左子樹上 */ deletenode( c , amp。((*p) left) ) 。 else if ( c (*p) key ) /* c 當前結點的 key 值，被刪結點在右子樹上 */ deletenode( c , amp。((*p) right ) ) 。 else{ r = *p 。 if ( rright == NULL ) *p = r left /* 右子樹空，接左分支 */ else if ( rleft == NULL ) *p = r right 。 /* 左子樹空，接右分支 */ else r=del( amp。(rleft),p ) 。 /* 左右均非空 */ free( r ) 。 /* 釋放 r */ } }。 4 5 6 2 7 1 3 8 root: p: deletenode( 4 , amp。root ) r: r 只有一個左子樹 treepointer del( treepointer *s, treepointer *p ) { /* 處理第三種情況，僅第三種情況調(diào)用 */ treepointer r。 if ((*s)right != NULL ) /* 右分支非空 ? */ r=del( amp。((*s)right),p ) //右分支非空 , 在右方向以下繼續(xù)查找 else { /* 找到右分支為空的結點 *s */ (*p)key =(*s) key 。 /* 復制 *s的關鍵字、數(shù)據(jù)到 *p結點 */ (*p)data =(*s) data 。 r = *s 。 /* r記載該 *s結點，為 free做準備 */ *s