數(shù)據(jù)結(jié)構(gòu)第六章樹和二叉樹-文庫吧
2025-09-13 15:26 本頁面
【正文】 g2n +1 證明：設(shè) k為深度，由二叉樹性質(zhì)２，已知 2k11 ＜ n ≤ 2 k1 即 2k1 ≤ n ＜ 2k 即 k = log2n +1 8 9 10 11 12 4 5 6 7 2 3 1 x : 表示向下取整，值為 不大于 x的最大整數(shù) 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 613 ? 完全二叉樹 (性質(zhì) ５ )： ? 在完全二叉樹中，結(jié)點(diǎn) i的雙親為 i/2 ? 結(jié)點(diǎn) i的左孩子 LCHILD(i)=2i ? 結(jié)點(diǎn) i的右孩子 RCHILD(i)=2i+1 二叉樹 8 9 10 11 12 4 5 6 7 2 3 1 2i 2i+1 2i+2 2i+3 i i+1 i/2 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 614 二叉樹 ? 二叉樹的存儲結(jié)構(gòu) ? 順序存儲結(jié)構(gòu) ：用一個一維數(shù)組來存儲二叉樹的各個結(jié)點(diǎn) ? C語言表示 define MAX_TREE_SIZE 100 //二叉樹的最大結(jié)點(diǎn)數(shù) typedef TElemType SqBiTree[MAX_TREE_SIZE]。//0號單元存儲根結(jié)點(diǎn) SqBiTree bt。 ? 顯然，二叉樹的結(jié)點(diǎn)必須按某種次序分別存入數(shù)組的各個單元，這種次序應(yīng)能反映結(jié)點(diǎn)間的邏輯關(guān)系，否則二叉樹上的各種基本運(yùn)算在順序存儲結(jié)構(gòu)上很難實現(xiàn)。 ? 對于完全二叉樹來說，可以采用“以編號為地址”的方法，將編號為 i的結(jié)點(diǎn)存入一維數(shù)組的第 i個單元 (下標(biāo)為 i1)。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 615 二叉樹 ? 完全二叉樹的順序表示 例 : 對應(yīng)的順序存儲結(jié)構(gòu) : 將編號為 i的結(jié)點(diǎn)存入一維數(shù)組的第 i個單元 (下標(biāo)為 i1) 8 9 10 4 5 6 7 2 3 1 9 8 7 6 5 4 3 2 1 0 10 9 8 7 6 5 4 3 2 1 下標(biāo) → 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 616 ? 非完全二叉樹的順序表示 例 : 對應(yīng)的順序存儲結(jié)構(gòu) : 一維數(shù)組的 21單元中只用上了 7個 .最壞情況下 ,一個深度為 k且只有 k個結(jié)點(diǎn)的單支樹 ,卻需要長度為 2k1的一維數(shù)組 ? 總結(jié) ? 順序存儲結(jié)構(gòu)適合存儲完全二叉樹 ? 對于非完全二叉樹，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)更合適 二叉樹 A B D C E G F D C B A F E G 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 617 二叉樹 ? 二叉鏈表 ? 結(jié)點(diǎn)結(jié)構(gòu) : 通常每個結(jié)點(diǎn)中設(shè)置三個域 ,即值域、左指針域和右指針域，其結(jié)點(diǎn)結(jié)構(gòu)如下： 其中 data表示值域， lchild和 rchild分別表示左指針域和右指針域，用以分別存儲指向左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)的指針。 ? TElemType可以是任何相應(yīng)的數(shù)據(jù)類型如 int、 float或 char等。 lchild data rchild typedef struct BiTNode { TElemType data。 struct BiTNode *lchild, *rchild。 } BiTNode, *BITree。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 618 二叉樹 F E C D C B A A ^ B ^ D ^ C ^ E ^ G ^ ^ F ^ 鏈?zhǔn)酱鎯? 示例節(jié)點(diǎn) 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 619 二叉樹 ? 三叉鏈表 通常每個結(jié)點(diǎn)中設(shè)置四個域 ,即值域、左指針域、右指針域和雙親指針域，其結(jié)點(diǎn)結(jié)構(gòu)如下： 其中 data表示值域，用于存儲放入結(jié)點(diǎn)的數(shù)據(jù)， lchild和rchild分別表示左指針域和右指針域，用以分別存儲指向左兒子結(jié)點(diǎn)和右兒子結(jié)點(diǎn)的指針 ,parent指向雙親結(jié)點(diǎn)。 lchild data parent rchild 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 620 遍歷二叉樹 ? 遍歷二叉樹 ? 定義：二叉樹的遍歷 (Traverse)是指按一定的規(guī)律訪問二叉樹的每個結(jié)點(diǎn)，且每個結(jié)點(diǎn)只被訪問一次的過程。 ? 對二叉樹的遍歷過程實際上是將非線性結(jié)構(gòu)的二叉樹中的結(jié)點(diǎn)排列成一個線性序列的過程。 ? 本節(jié)僅討論二叉鏈表的遍歷過程。設(shè)訪問根結(jié)點(diǎn)用 D表示，遍歷左、右子樹用 L、 R表示 ? 遍歷分類：在任一結(jié)點(diǎn)上，有三種執(zhí)行操作：訪問結(jié)點(diǎn)本身，遍歷該結(jié)點(diǎn)左子樹，遍歷該結(jié)點(diǎn)右子樹。操作次序主要分為三種： 1. 左、根、右；也稱為 中序遍歷、 LDR； 2. 根、左、右；也稱為 先序遍歷、 DLR； 3. 左、右、根；也稱為 后序遍歷、 LRD。 中國科大 《 數(shù)據(jù)結(jié)構(gòu) 》 621 遍歷二叉樹 ? 三種遍歷次序以遞歸的形式定義 1. 中序 (InOrd
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1