特殊二叉樹ppt課件-資料下載頁
2025-05-01 12:11本頁面
【正文】 驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的指針。 ? 前驅(qū)線索 ：在結(jié)點(diǎn)的空指針域中存放的該結(jié)點(diǎn)在某次遍歷次序下的前驅(qū)結(jié)點(diǎn)的指針。 ? 后繼線索 ：在結(jié)點(diǎn)的空指針域中存放的該結(jié)點(diǎn)在某次遍歷次序下的后繼結(jié)點(diǎn)的指針。 ? 線索化 ：對(duì)一棵二叉樹中所有結(jié)點(diǎn)的空指針域按某種遍歷次序加線索的過程。 ? 線索二叉樹 ：被線索化了的二叉樹。 ?增加線索標(biāo)志域后的結(jié)點(diǎn)結(jié)構(gòu)為： le f t lta g d a t a r ta g r ig h t對(duì) ltag,rtag定義如下 ： ltag= 0 left域指向結(jié)點(diǎn)左孩子 1 left域指向結(jié)點(diǎn)某種遍歷下的前驅(qū) rtag= 0 right域指向結(jié)點(diǎn)右孩子 1 right域指向結(jié)點(diǎn)某種遍歷下的后繼 ?該結(jié)點(diǎn)結(jié)構(gòu)的類型定義為 Struct TTreeNode { //定義線索二叉樹的結(jié)點(diǎn)類型 ElemType data。 //值域 int ltag,rtag。 //線索標(biāo)志域 TTreeNode *left。 //左指針域 TTreeNode *right。 //右指針域 } G A E B C D F H NULL 中序線索二叉樹 0 A 0^ 1 B 0 0 C 00 D 1 1 E 0 1 F 1 ^1 G 1 1 H 1BGDAEHCF G A E B C D F H NULL G A E B C D F H G A E B C D F H NULL 先序線索二叉樹 G A E B C D F H 后序線索二叉樹 ABDGCEHF GDBHEFCA NULL 利用線索進(jìn)行遍歷 例：如何在中序線索二叉樹上尋找一個(gè)結(jié)點(diǎn) p的中序后繼結(jié)點(diǎn) 0 A 0^ 1 B 0 0 C 00 D 1 1 E 0 1 F 1 ^1 G 1 1 H 1 (1) 若 p結(jié)點(diǎn)的右線索標(biāo)志域?yàn)?1, 則 pright直接指向 p的中序后繼結(jié)點(diǎn) (2) 若 p結(jié)點(diǎn)的右線索標(biāo)志域?yàn)?0, p的中序后繼結(jié)點(diǎn)必是其右子樹中第一個(gè)中序遍到的結(jié)點(diǎn) ,也就是 p的右子樹中 “ 最左下 ” 結(jié)點(diǎn) . RK x R2 R1 p 0 R1 0 0 0 0 x 0 0 0 0 R2 0 0 0 0 Rk 0 1 0 p 練習(xí)： 1. 已知一棵二叉樹的中序序列為 cbedahgijf,后序序列為 cedbhjigfa，畫出其前序線索二叉樹 2. 二叉樹在線索后，仍不能有效求解的問題是 A. 先序線索二叉樹中求先序后繼 B. 中序線索二叉樹中求中序后繼 C. 中序線索二叉樹中求中序前驅(qū) D. 后序線索二叉樹中求后序后繼 D 平衡二叉樹 一、定義 平衡二叉樹是對(duì)二叉搜索樹的一種改進(jìn) ， 簡稱平衡樹，又稱 AVL樹 。 平衡二叉樹 ：若一棵二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹的高度至多相差 1 平衡因子 ： 二叉樹中每個(gè)結(jié)點(diǎn)的左子樹高度減去右子樹高度定義為該結(jié)點(diǎn)的平衡因子 。平衡樹中每個(gè)結(jié)點(diǎn)的平衡因子只能是 0或 1。 3620 4816 30 6528251510 325 12 604511 10 0 00 022 10 2 00110 20 0 10 平衡二叉樹 二、最小不平衡二叉樹 若插入后某些結(jié)點(diǎn)的左子樹高度增加 1， 具體分為以下三種情況： (1) 若插入前 ， 一些結(jié)點(diǎn)的左子樹高度 hL 與右子樹高度 hR相等 ， 即平衡因子為 0， 則 插入后將使平衡因子變?yōu)?1， 但仍符合平衡 的條件 ， 不必對(duì)它們加以調(diào)整 (2) 若插入前一些結(jié)點(diǎn)的hL小于 hR，即平衡因子為 1，則插入后將使平衡因子變?yōu)?0，平衡更加理想，更不必進(jìn)行調(diào)整 (3) 若插入前一些結(jié)點(diǎn)的hL大于 hR，即平衡因子為 1，則插入后將使平衡因子變?yōu)?2，破壞了平衡樹的限制條件，需對(duì)它們加以調(diào)整，使整個(gè)二叉搜索樹恢復(fù)為平衡樹。 最小不平衡子樹 ：指以離插入結(jié)點(diǎn)最近、且平衡因子絕對(duì)值大于 1的結(jié)點(diǎn)做根的子樹。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1