數(shù)據(jù)結(jié)構(gòu)二叉排序樹(shù)-展示頁(yè)
2025-06-26 06:52本頁(yè)面
【正文】 Tree）又稱二叉查找樹(shù)，亦稱二叉搜索樹(shù)。 它或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)： （1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； （2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； （3）左、右子樹(shù)也分別為二叉排序樹(shù)；一、 查找：步驟：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。若大于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹(shù)。平均情況分析（在成功查找兩種的情況下）：在一般情況下，設(shè) P（n，i）且它的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為 i 時(shí)的平均查找長(zhǎng)度。 則 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6注意：這里 P(3)、P(2) 是具有 3 個(gè)結(jié)點(diǎn)、2 個(gè)結(jié)點(diǎn)的二叉分類(lèi)樹(shù)的平均查找長(zhǎng)度。P(3) = （1+2+2）/ 3 = 5/3P(2) = （1+2）/ 2 = 3/2∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(ni1) + 1) * (ni1) ] / n∴ P（n）= P（n,i）/ n = 2(1+I/n)lnn因?yàn)?2(1+I/n)lnn≈ 故P(n)=O(logn)二、 插入刪除與次優(yōu)二叉樹(shù)相對(duì)，二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表。新插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉子節(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子結(jié)點(diǎn)。判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。若二叉樹(shù)為空。注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。{ t=new BiTree。 tdata=key。 } if(keytdata ) InsertBST(tlchild,key)。 } //n個(gè)數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹(shù)
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1