第五章樹(shù)和二叉樹(shù)(編輯修改稿)
2025-08-17 17:10 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ta) { q=p。 p=plchild。 } else { q=p。 p=prchild。 } } if (p==NULL) printf(“未發(fā)現(xiàn)數(shù)據(jù)域?yàn)?%d的結(jié)點(diǎn) \n”, x)。 else if (plchild==NULL) // 被刪結(jié)點(diǎn)無(wú)左子樹(shù) { if (q==NULL) t=prchild。 else if (qlchild==p) qlchild=prchild。 else qrchild=prchild。 } 2022/8/17 22 else // 被刪結(jié)點(diǎn)有左子樹(shù) { // 查找被刪結(jié)點(diǎn)的左子樹(shù)中的最右結(jié)點(diǎn)，即剛好小于 x的結(jié)點(diǎn) r=plchild。 while (rrchild != NULL) r=rrchild。 // 被刪結(jié)點(diǎn)的右子樹(shù)作為 r的右子樹(shù) rrchild=prchild。 // 被刪結(jié)點(diǎn)的左子樹(shù)根代替被刪結(jié)點(diǎn) if (q==NULL) t=plchild。 else if (qlchild==p) qlchild=plchild。 else qrchild=plchild。 } } 2022/8/17 23 二叉排序樹(shù)的查找 bitree *SEARCH(bitree *b, int x) { if (b==NULL) return (NULL)。 else { if (bdata == x) return (b)。 if (bdata x) return (SEARCH(blchild))。 else return (SEARCH(brchild))。 } } 2022/8/17 24 一棵 m 階的 B樹(shù)滿足下列條件： 每個(gè)結(jié)點(diǎn) 至多有 m個(gè) 孩子； 根結(jié)點(diǎn)至少有兩個(gè)孩子（唯一例外的是只包含一個(gè)根 結(jié)點(diǎn)的 B樹(shù)）； 除根結(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)。 所有葉結(jié)點(diǎn)在同一層，葉結(jié)點(diǎn)不包含任何關(guān)鍵字信息。 三、 B樹(shù) 2022/8/17 25 357 045 112 236 392 490 560 631 670 008 040 052 110 135 142 212 237 240 279 378 381 388 393 396 400 435 471 492 502 553 2022/8/17 26 在 B樹(shù)中包含 j個(gè)關(guān)鍵字， j+1個(gè)指針的 結(jié)點(diǎn)，一般表示形式為： A0 , K1 , A1 , K2 , A2 , … K j , Aj 2022/8/17 27 B樹(shù)的運(yùn)算 查找 插入 132 142 212 132 137 142 212 插入 137變?yōu)? 2022/8/17 28 357 490 392 400 453 460 471 393 396 560 631 670 2022/8/17 29 刪除 052 112 236 008 040 052 110 135 142 212 237 240 279 2022/8/17 3
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1