數(shù)據(jù)結(jié)構(gòu)二叉排序樹(shù)-全文預(yù)覽
【正文】 lastelement = h elements[ h size ]。 h elements [ i ] = x。 int i。 } void insert ( int x , struct priorityqueue *h ) { h capacity = maxelements。 }*tryit。InsertBST(tree,d[i])。i++) InsertBST (trchild, key )。else tlchild=trchild=NULL。 if(t==NULL) //在二叉排序樹(shù)中插入查找關(guān)鍵字key void InsertBST(t，key) { 將被插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。其特點(diǎn)是：樹(shù)的結(jié)構(gòu)通常不是一次生成的，而是在查找過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值的節(jié)點(diǎn)時(shí)再進(jìn)行插入。如圖的結(jié)點(diǎn)個(gè)數(shù)為 n = 6 且 i = 3。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹(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)鍵字，成功。平均情況分析（在成功查找兩種的情況下）：在一般情況下，設(shè) P（n，i）且它的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為 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
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號(hào)-1