第五章樹和二叉樹-wenkub
2022-08-18 17:10:54 本頁面
【正文】 *p的右孩子開始，沿左指針鏈往下查找，直 到找到一個沒有左孩子的結(jié)點為止。 } else prtag＝ 0。 // 若前驅(qū)結(jié)點不為空，且其右孩子為空，則建立該前驅(qū)結(jié)點指向當(dāng)前結(jié)點的后續(xù)線索 if (pre!=NULL amp。 lchild ltag rtag data rchild 標(biāo)志位如果為 0，表示指針指向孩子結(jié)點，為 1表示指針為線索 2022/8/17 4 0 A 0 0 B 0 0 E 1 1 C 1 1 D 1 1 F 0 0 G 0 1 H 1 1 I 1 NULL NULL t 2022/8/17 5 中序線索化算法 INTHREAD(bithptr *p,bithptr *pre) // p為當(dāng)前結(jié)點， pre為 p的前驅(qū)結(jié)點，開始調(diào)用時 p為根結(jié)點指針， pre為 NULL { if (p!=NULL) { INTHREAD(plchild,pre)。 datatype data。若增加指針 域來存放前驅(qū)和后繼結(jié)點信息，將大大降低存儲 空間的利用率（密度）?？疾? n 個結(jié)點的二叉樹， 其中有 n+1 個空指針域，它們可以被用來存放 “ 線 索 ” 加了線索的二叉樹稱為線索二叉樹。 struct node *lchild,*rchild。 // 左子樹線索化 // 若當(dāng)前結(jié)點的左子樹為空，則建立指向其前驅(qū)結(jié)點的前驅(qū)線索 if (plchild = = NULL) { pltag＝ 1。amp。 pre＝ p。 中序線索二叉樹中，查找指定結(jié)點 *p的中序后繼結(jié)點 2022/8/17 7 p R1 R2 Rk 最左下結(jié)點 2022/8/17 8 中序線索二叉樹中求中序后繼結(jié)點的算法 bithptr *INORDERNEXT(bithptr *p) { bithptr *q。 return(q)。 do { printf(“\t%d\n”,pdata)。 s＝ INORDERNEXT(p)。 qrchild＝ prchild。amp。 struct node *lchild,*rchild。 // 不做任何插入操作 else if ( sdata bdata ) INSERT(blchild, s)。 b=NULL。 // 產(chǎn)生一個樹結(jié)點 sdata=x。 // 插入該結(jié)點 }while(x!=1)。 // q指向 p的前驅(qū)結(jié)點 while (p!=NULL amp。 } else { q=p。 else if (qlchild==p) qlchild=prchild。 // 被刪結(jié)點的右子樹作為 r的右子樹 rrchild=prchild。 } } 2022/8/17 23 二叉排序樹的查找 bitree *SEARCH(bitree *b, int x) { if (b==NULL) return (NULL)。 } } 2022/8/17 24 一棵 m 階的 B樹滿足下列條件： 每個結(jié)點 至多有 m個 孩子； 根結(jié)點至少有兩個孩子（唯一例外的是只包含一個根 結(jié)點的 B樹）； 除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少有 ? m/2? 個 孩子； 有 n+1個孩子的非葉結(jié)點恰好包含 n個關(guān)鍵字 (A0 , K1 , A1 , K2 , A2 , … K n, An)。 2022/8/17 32 帶權(quán)路徑長度 ( Weighted Path Length, WPL ) 樹的帶權(quán)路徑長度是樹的各葉結(jié)點所帶的權(quán)值 與該結(jié)點到根的路徑長度的乘積的和。 (2
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1