數(shù)據(jù)結(jié)構(gòu)-二叉排序樹-文庫吧資料
2024-08-22 15:47本頁面
【正文】 2 24 37 13 X A 1 B BL BR AR 0 LL型 BLBBRAAR A B BL BR AR X B A AL BL BR X ALABLBBR RR型 B A AL BL BR X X X A B CL BL CR C AR 0 1 LR型 BLBCLC CR AAR A B CL BL CR C AR 1 X X A B CL AL CR C BR 0 1 X X RL型 B A CL AL CR C BR 1 X X ALACLC CR BBR 例：按下列關(guān)鍵字的次序生成一棵 AVL樹。 其二叉排序樹為： ASL = (1 + 2 + 3 + 4 + 5 + 6)/6 = 21/6 12 24 37 45 53 90 二叉排序樹的性能取決于樹的形態(tài)，而二叉樹的形態(tài) 取決于插入結(jié)點(diǎn)的順序。 二叉排序樹的性能取決于樹的形態(tài)，而二叉樹的形態(tài) 取決于插入結(jié)點(diǎn)的順序 。 4. 二叉排序樹的刪除算法 可分 三種情況 討論： 刪除一個(gè)結(jié)點(diǎn)后，仍是二叉排序樹。root){ //輸入一個(gè)關(guān)鍵字序列，生成一棵二叉排序樹的二叉鏈表結(jié)構(gòu) root=NULL； read(x)； while (x≠ 結(jié)束標(biāo)志 ){ s=(BiTree)malloc(sizeof(BiTNode)) s→key=x ； …… ； //生成新結(jié)點(diǎn) s→lchild =NULL ； s→rchild =NULL ； ins_ bstree(root, s)； read(x)； } return (root)。 每次插入的結(jié)點(diǎn)只能成為新的 葉子結(jié)點(diǎn) 例：關(guān)鍵字序列為 {45， 24， 53， 12， 14， 90 } 45 24 12 14 53 90 中序遍歷 :12,14,24,45,53,90 (1) 插入算法： status ins_bstree(BiTree amp。 66 不 對(duì) 二叉排序樹進(jìn)行中序遍歷，得到一個(gè)有序序列 1）若給定值 等于 根結(jié)點(diǎn)的關(guān)鍵字，則查找成功； 2）若給定值 小于 根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找； 3）若給定值 大于 根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。(1) 若它的左子樹不空，則左子樹上 所有 結(jié)點(diǎn)的值 均小于 根結(jié)點(diǎn)的值； 1．定義： 二叉排序樹 (二叉搜索樹 或 二叉查找樹 ) 或者是一棵空樹；或者是具有如下特性的二叉樹 (3) 它的左、右子樹 也都 分別 是二叉排序樹 。 (2) 若它的右子樹不空，則右子樹上 所有 結(jié)點(diǎn) 的值 均大于等于 根結(jié)點(diǎn)的值； 二叉排序樹 50 30 80 20 90 10 85 40 35 25 23 88 例如 : 是二叉排序樹。 否則 若二叉排序樹 為空 ，則查找不成功； 2. 二叉排序樹的查找算法： 50 30 80 20 90 85 40 35 88 32 例如 : 二叉排序樹 查找關(guān)鍵字 = 50 , 35 , 90 , 95 , 二叉鏈表類型定義： typedef struct BiTNode{ KeyType key； …… //其它成員 struct BiTNode *lchild； struct BiTNode *rchild； } BiTNode， *BiTree； 二叉排序樹的查找： BiTree bstsrch(BiTree bt， KeyType k){ //二叉排序樹的存儲(chǔ)結(jié)構(gòu)為二叉鏈表，函數(shù)返回結(jié)點(diǎn)的//關(guān)鍵字為 k的指針，若查找不成功，返回空指針 if (t==NULL） return NULL； else if（ bt→key==k ） ret
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1