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