數(shù)據(jù)結構二叉排序樹(已修改)
2025-06-29 06:52 本頁面
【正文】 二叉排序樹（Binary Sort Tree）又稱二叉查找樹，亦稱二叉搜索樹。 它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： （1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； （2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； （3）左、右子樹也分別為二叉排序樹；一、 查找：步驟：若根結點的關鍵字值等于查找的關鍵字，成功。否則，若小于根結點的關鍵字值，遞歸查左子樹。若大于根結點的關鍵字值，遞歸查右子樹。若子樹為空，查找不成功。平均情況分析（在成功查找兩種的情況下）：在一般情況下，設 P（n，i）且它的左子樹的結點個數(shù)為 i 時的平均查找長度。如圖的結點個數(shù)為 n = 6 且 i = 3。 則 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 個結點、2 個結點的二叉分類樹的平均查找長度。 在一般情況，P（i）為具有 i 個結點二叉分類樹的平均查找長度。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因為 2(1+I/n)lnn≈ 故P(n)=O(logn)二、 插入刪除與次優(yōu)二叉樹相對，二叉排序樹是一種動態(tài)樹表。其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的節(jié)點時再進行插入。新插入的結點一定是一個新添加的葉子節(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。三、 插入算法首先執(zhí)行查找算法，找出被插結點的父親結點。判斷被插結點是其父親結點的左、右兒子。將被插結點作為葉子結點插入。若二叉樹為空。則首先單獨生成根結點。注意：新插入的結點總是葉子結點。//在二叉排序樹中插入查找關鍵字key void InsertBST(t，key) { if(t==NULL) { t=new BiTree。 tlchild=trchild=NULL。 tdata=key。 return。 160
職業(yè)教育相關推薦
鄂ICP備17016276號-1