數(shù)據(jù)結(jié)構(gòu)第5章樹和二叉樹.ppt

樹的邏輯結(jié)構(gòu)樹的存儲結(jié)構(gòu)二叉樹的邏輯結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)及實現(xiàn)樹 森林與二叉樹的轉(zhuǎn)換哈夫曼樹 第5章樹和二叉樹 本章的主要內(nèi)容是 樹的定義 樹 n n 0 個結(jié)點的有限集合 當(dāng)n 0時 稱為空樹 任意一棵非空樹滿足以下條件 有且僅有一個特定的稱為根的結(jié)點 當(dāng)n 1時 除根結(jié)點之外的其余結(jié)點被分成m m 0 個互不相交的有限集合T1 T2 Tm 其中每個集合又是一棵樹 并稱為這個根結(jié)點的子樹 5 1樹的邏輯結(jié)構(gòu) 樹的定義是采用遞歸方法 a 一棵樹結(jié)構(gòu) b 一個非樹結(jié)構(gòu) c 一個非樹結(jié)構(gòu) 5 1樹的邏輯結(jié)構(gòu) 樹的定義 樹的應(yīng)用舉例 文件結(jié)構(gòu) 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 結(jié)點的度 結(jié)點所擁有的子樹的個數(shù) 樹的度 樹中各結(jié)點度的最大值 5 1樹的邏輯結(jié)構(gòu) 5 1樹的邏輯結(jié)構(gòu) 葉子結(jié)點 度為0的結(jié)點 也稱為終端結(jié)點 分支結(jié)點 度不為0的結(jié)點 也稱為非終端結(jié)點 樹的基本術(shù)語 孩子 雙親 樹中某結(jié)點子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點 這個結(jié)點稱為它孩子結(jié)點的雙親結(jié)點 兄弟 具有同一個雙親的孩子結(jié)點互稱為兄弟 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 路徑 如果樹的結(jié)點序列n1 n2 nk有如下關(guān)系 結(jié)點ni是ni 1的雙親 1 i k 則把n1 n2 nk稱為一條由n1至nk的路徑 路徑上經(jīng)過的邊的個數(shù)稱為路徑長度 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 祖先 子孫 在樹中 如果有一條路徑從結(jié)點x到結(jié)點y 那么x就稱為y的祖先 而y稱為x的子孫 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 結(jié)點所在層數(shù) 根結(jié)點的層數(shù)為1 對其余任何結(jié)點 若某結(jié)點在第k層 則其孩子結(jié)點在第k 1層 樹的深度 樹中所有結(jié)點的最大層數(shù) 也稱高度 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 層序編號 將樹中結(jié)點按照從上層到下層 同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù) 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 有序樹 無序樹 如果一棵樹中結(jié)點的各子樹從左到右是有次序的 稱這棵樹為有序樹 反之 稱為無序樹 數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 森林 m m 0 棵互不相交的樹的集合 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 同構(gòu) 對兩棵樹 若通過對結(jié)點適當(dāng)?shù)刂孛?就可以使這兩棵樹完全相等 結(jié)點對應(yīng)相等 結(jié)點對應(yīng)關(guān)系也相等 則稱這兩棵樹同構(gòu) 5 1樹的邏輯結(jié)構(gòu) 樹的基本術(shù)語 樹結(jié)構(gòu)和線性結(jié)構(gòu)的比較 線性結(jié)構(gòu) 樹結(jié)構(gòu) 無前驅(qū) 無雙親 無后繼 無孩子 一個前驅(qū) 一個后繼 一個雙親 多個孩子 一對一一對多 5 1樹的邏輯結(jié)構(gòu) 樹的抽象數(shù)據(jù)類型定義 ADTTreeData樹是由一個根結(jié)點和若干棵子樹構(gòu)成 樹中結(jié)點具有相同數(shù)據(jù)類型及層次關(guān)系OperationInitTree前置條件 樹不存在輸入 無功能 初始化一棵樹輸出 無后置條件 構(gòu)造一個空樹 5 1樹的邏輯結(jié)構(gòu) DestroyTree前置條件 樹已存在輸入 無功能 銷毀一棵樹輸出 無后置條件 釋放該樹占用的存儲空間Root前置條件 樹已存在輸入 無功能 求樹的根結(jié)點輸出 樹的根結(jié)點的信息后置條件 樹保持不變 樹的抽象數(shù)據(jù)類型定義 5 1樹的邏輯結(jié)構(gòu) Parent前置條件 樹已存在輸入 結(jié)點x功能 求結(jié)點x的雙親輸出 結(jié)點x的雙親的信息后置條件 樹保持不變Depth前置條件 樹已存在輸入 無功能 求樹的深度輸出 樹的深度后置條件 樹保持不變 樹的抽象數(shù)據(jù)類型定義 5 1樹的邏輯結(jié)構(gòu) PreOrder前置條件 樹已存在輸入 無功能 前序遍歷樹輸出 樹的前序遍歷序列后置條件 樹保持不變PostOrder前置條件 樹已存在輸入 無功能 后序遍歷樹輸出 樹的后序遍歷序列后置條件 樹保持不變endADT 樹的抽象數(shù)據(jù)類型定義 5 1樹的邏輯結(jié)構(gòu) 樹的遍歷操作 樹的遍歷 從根結(jié)點出發(fā) 按照某種次序訪問樹中所有結(jié)點 使得每個結(jié)點被訪問一次且僅被訪問一次 如何理解訪問 抽象操作 可以是對結(jié)點進(jìn)行的各種處理 這里簡化為輸出結(jié)點的數(shù)據(jù) 如何理解次序 樹通常有前序 根 遍歷 后序 根 遍歷和層序 次 遍歷三種方式 5 1樹的邏輯結(jié)構(gòu) 樹結(jié)構(gòu) 非線性結(jié)構(gòu) 線性結(jié)構(gòu) 遍歷的實質(zhì) 前序遍歷 樹的前序遍歷操作定義為 若樹為空 則空操作返回 否則 訪問根結(jié)點 按照從左到右的順序前序遍歷根結(jié)點的每一棵子樹 5 1樹的邏輯結(jié)構(gòu) 前序遍歷序列 ABDEHIFCG 后序遍歷 樹的后序遍歷操作定義為 若樹為空 則空操作返回 否則 按照從左到右的順序后序遍歷根結(jié)點的每一棵子樹 訪問根結(jié)點 5 1樹的邏輯結(jié)構(gòu) 后序遍歷序列 DHIEFBGCA 層序遍歷 樹的層序遍歷操作定義為 從樹的第一層 即根結(jié)點 開始 自上而下逐層遍歷 在同一層中 按從左到右的順序?qū)Y(jié)點逐個訪問 5 1樹的邏輯結(jié)構(gòu) 層序遍歷序列 ABCDEFGHI 5 2樹的存儲結(jié)構(gòu) 實現(xiàn)樹的存儲結(jié)構(gòu) 關(guān)鍵是什么 什么是存儲結(jié)構(gòu) 樹中結(jié)點之間的邏輯關(guān)系是什么 思考問題的出發(fā)點 如何表示結(jié)點的雙親和孩子 如何表示樹中結(jié)點之間的邏輯關(guān)系 數(shù)據(jù)元素以及數(shù)據(jù)元素之間的邏輯關(guān)系在存儲器中的表示 雙親表示法 基本思想 用一維數(shù)組來存儲樹的各個結(jié)點 一般按層序存儲 數(shù)組中的一個元素對應(yīng)樹中的一個結(jié)點 包括結(jié)點的數(shù)據(jù)信息以及該結(jié)點的雙親在數(shù)組中的下標(biāo) 5 2樹的存儲結(jié)構(gòu) templatestructPNode Tdata 數(shù)據(jù)域intparent 指針域 雙親在數(shù)組中的下標(biāo) 5 2樹的存儲結(jié)構(gòu) 樹的雙親表示法實質(zhì)上是一個靜態(tài)鏈表 雙親表示法 下標(biāo)dataparent 5 2樹的存儲結(jié)構(gòu) 如何查找雙親結(jié)點 時間性能 雙親表示法 5 2樹的存儲結(jié)構(gòu) 雙親表示法 如何查找孩子結(jié)點 時間性能 下標(biāo)dataparent firstchild 下標(biāo)dataparent rightsib 5 2樹的存儲結(jié)構(gòu) 雙親表示法 如何查找兄弟結(jié)點 時間性能 鏈表中的每個結(jié)點包括一個數(shù)據(jù)域和多個指針域 每個指針域指向該結(jié)點的一個孩子結(jié)點 如何確定鏈表中的結(jié)點結(jié)構(gòu) 5 2樹的存儲結(jié)構(gòu) 孩子鏈表表示法 5 2樹的存儲結(jié)構(gòu) 缺點 浪費空間 A B C D E F G H I 鏈表中的每個結(jié)點包括一個數(shù)據(jù)域和多個指針域 每個指針域指向該結(jié)點的一個孩子結(jié)點 如何確定鏈表中的結(jié)點結(jié)構(gòu) 5 2樹的存儲結(jié)構(gòu) 孩子鏈表表示法 方案二 指針域的個數(shù)等于該結(jié)點的度 其中 data 數(shù)據(jù)域 存放該結(jié)點的數(shù)據(jù)信息 degree 度域 存放該結(jié)點的度 child1 childd 指針域 指向該結(jié)點的孩子 5 2樹的存儲結(jié)構(gòu) 缺點 結(jié)點結(jié)構(gòu)不一致 A2 B3 C2 E1 I0 G0 H0 F0 D0 孩子鏈表表示法 基本思想 把每個結(jié)點的孩子排列起來 看成是一個線性表 且以單鏈表存儲 則n個結(jié)點共有n個孩子鏈表 這n個單鏈表共有n個頭指針 這n個頭指針又組成了一個線性表 為了便于進(jìn)行查找采用順序存儲 最后 將存放n個頭指針的數(shù)組和存放n個結(jié)點的數(shù)組結(jié)合起來 構(gòu)成孩子鏈表的表頭數(shù)組 5 2樹的存儲結(jié)構(gòu) 如何確定鏈表中的結(jié)點結(jié)構(gòu) 將結(jié)點的所有孩子放在一起 構(gòu)成線性表 structCTNode intchild CTNode next 5 2樹的存儲結(jié)構(gòu) templatestructCBNode Tdata CTNode firstchild 孩子鏈表表示法 012345678 下標(biāo)datafirstchild ABCDEFGHI 5 2樹的存儲結(jié)構(gòu) 如何查找孩子結(jié)點 時間性能 012345678 下標(biāo)datafirstchild ABCDEFGHI 5 2樹的存儲結(jié)構(gòu) 如何查找雙親結(jié)點 時間性能 雙親孩子表示法 5 2樹的存儲結(jié)構(gòu) 孩子兄弟表示法 5 2樹的存儲結(jié)構(gòu) 某結(jié)點的第一個孩子是惟一的某結(jié)點的右兄弟是惟一的 templatestructTNode Tdata TNode firstchild rightsib 5 2樹的存儲結(jié)構(gòu) 結(jié)點結(jié)構(gòu) data 數(shù)據(jù)域 存儲該結(jié)點的數(shù)據(jù)信息 firstchild 指針域 指向該結(jié)點第一個孩子 rightsib 指針域 指向該結(jié)點的右兄弟結(jié)點 孩子兄弟表示法 5 2樹的存儲結(jié)構(gòu) 孩子兄弟表示法 如何查找兄弟結(jié)點 時間性能 5 2樹的存儲結(jié)構(gòu) 孩子兄弟表示法 如何查找孩子結(jié)點 時間性能 二叉樹的定義 二叉樹是n n 0 個結(jié)點的有限集合 該集合或者為空集 稱為空二叉樹 或者由一個根結(jié)點和兩棵互不相交的 分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成 5 3二叉樹的邏輯結(jié)構(gòu) 問題轉(zhuǎn)化 將樹轉(zhuǎn)換為二叉樹 從而利用二叉樹解決樹的有關(guān)問題 研究二叉樹的意義 二叉樹的特點 每個結(jié)點最多有兩棵子樹 二叉樹是有序的 其次序不能任意顛倒 5 3二叉樹的邏輯結(jié)構(gòu) 注意 二叉樹和樹是兩種樹結(jié)構(gòu) 二叉樹的基本形態(tài) 5 3二叉樹的邏輯結(jié)構(gòu) 5 3二叉樹的邏輯結(jié)構(gòu) 具有3個結(jié)點的樹和具有3個結(jié)點的二叉樹的形態(tài) 二叉樹和樹是兩種樹結(jié)構(gòu) 特殊的二叉樹 斜樹1 所有結(jié)點都只有左子樹的二叉樹稱為左斜樹 2 所有結(jié)點都只有右子樹的二叉樹稱為右斜樹 3 左斜樹和右斜樹統(tǒng)稱為斜樹 1 在斜樹中 每一層只有一個結(jié)點 2 斜樹的結(jié)點個數(shù)與其深度相同 5 3二叉樹的邏輯結(jié)構(gòu) 斜樹的特點 滿二叉樹在一棵二叉樹中 如果所有分支結(jié)點都存在左子樹和右子樹 并且所有葉子都在同一層上 滿二叉樹的特點 葉子只能出現(xiàn)在最下一層 只有度為0和度為2的結(jié)點 5 3二叉樹的邏輯結(jié)構(gòu) 特殊的二叉樹 滿二叉樹 5 3二叉樹的邏輯結(jié)構(gòu) 不是滿二叉樹 雖然所有分支結(jié)點都有左右子樹 但葉子不在同一層上 滿二叉樹在同樣深度的二叉樹中結(jié)點個數(shù)最多滿二叉樹在同樣深度的二叉樹中葉子結(jié)點個數(shù)最多 特殊的二叉樹 完全二叉樹對一棵具有n個結(jié)點的二叉樹按層序編號 如果編號為i 1 i n 的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點在二叉樹中的位置完全相同 5 3二叉樹的邏輯結(jié)構(gòu) 特殊的二叉樹 在滿二叉樹中 從最后一個結(jié)點開始 連續(xù)去掉任意個結(jié)點 即是一棵完全二叉樹 5 3二叉樹的邏輯結(jié)構(gòu) A 1 5 2 3 4 6 7 9 10 B C D E F G H I J 不是完全二叉樹 結(jié)點10與滿二叉樹中的結(jié)點10不是同一個結(jié)點 特殊的二叉樹 1 葉子結(jié)點只能出現(xiàn)在最下兩層 且最下層的葉子結(jié)點都集中在二叉樹的左部 2 完全二叉樹中如果有度為1的結(jié)點 只可能有一個 且該結(jié)點只有左孩子 3 深度為k的完全二叉樹在k 1層上一定是滿二叉樹 完全二叉樹的特點 5 3二叉樹的邏輯結(jié)構(gòu) 特殊的二叉樹 二叉樹的基本性質(zhì) 性質(zhì)5 1二叉樹的第i層上最多有2i 1個結(jié)點 i 1 證明 當(dāng)i 1時 第1層只有一個根結(jié)點 而2i 1 20 1 結(jié)論顯然成立 假定i k 1 k i 時結(jié)論成立 即第k層上至多有2k 1個結(jié)點 則i k 1時 因為第k 1層上的結(jié)點是第k層上結(jié)點的孩子 而二叉樹中每個結(jié)點最多有2個孩子 故在第k 1層上最大結(jié)點個數(shù)為第k層上的最大結(jié)點個數(shù)的二倍 即2 2k 1 2k 結(jié)論成立 5 3二叉樹的邏輯結(jié)構(gòu) 性質(zhì)5 2一棵深度為k的二叉樹中 最多有2k 1個結(jié)點 最少有k個結(jié)點 證明 由性質(zhì)1可知 深度為k的二叉樹中結(jié)點個數(shù)最多 2k 1 每一層至少要有一個結(jié)點 因此深度為k的二叉樹 至少有k個結(jié)點 5 3二叉樹的邏輯結(jié)構(gòu) 二叉樹的基本性質(zhì) 性質(zhì)5 3在一棵二叉樹中 如果葉子結(jié)點數(shù)為n0 度為2的結(jié)點數(shù)為n2 則有 n0 n2 1 證明 設(shè)n為二叉樹的結(jié)點總數(shù) n1為二叉樹中度為1的結(jié)點數(shù) 則有 n n0 n1 n2在二叉樹中 除了根結(jié)點外 其余結(jié)點都有唯一的一個分枝進(jìn)入 由于這些分枝是由度為1和度為2的結(jié)點射出的 一個度為1的結(jié)點射出一個分枝 一個度為2的結(jié)點射出兩個分枝 所以有 n n1 2n2 1因此可以得到 n0 n2 1 5 3二叉樹的邏輯結(jié)構(gòu) 二叉樹的基本性質(zhì) 5 3二叉樹的邏輯結(jié)構(gòu) 在有n個結(jié)點的滿二叉樹中 有多少個葉子結(jié)點 二叉樹的基本性質(zhì) 性質(zhì)5 3在一棵二叉樹中 如果葉子結(jié)點數(shù)為n0 度為2的結(jié)點數(shù)為n2 則有 n0 n2 1 性質(zhì)5 4具有n個結(jié)點的完全二叉樹的深度為log2n 1 5 3二叉樹的邏輯結(jié)構(gòu) 證明 假設(shè)具有n個結(jié)點的完全二叉樹的深度為k 根據(jù)完全二叉樹的定義和性質(zhì)2 有下式成立2k 1 n 2k 最少結(jié)點數(shù) 最多結(jié)點數(shù) 完全二叉樹的基本性質(zhì) 5 3二叉樹的邏輯結(jié)構(gòu) 證明 假設(shè)具有n個結(jié)點的完全二叉樹的深度為k 根據(jù)完全二叉樹的定義和性質(zhì)2 有下式成立2k 1 n 2k 完全二叉樹的基本性質(zhì) 性質(zhì)5 5對一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號 則對于任意的序號為i 1 i n 的結(jié)點 簡稱為結(jié)點i 有 1 如果i 1 則結(jié)點i的雙親結(jié)點的序號為i 2 如果i 1 則結(jié)點i是根結(jié)點 無雙親結(jié)點 2 如果2i n 則結(jié)點i的左孩子的序號為2i 如果2i n 則結(jié)點i無左孩子 3 如果2i 1 n 則結(jié)點i的右孩子的序號為2i 1 如果2i 1 n 則結(jié)點i無右孩子 5 3二叉樹的邏輯結(jié)構(gòu) 完全二叉樹的基本性質(zhì) 對一棵具有n個結(jié)點的完全二叉樹中從1開始按層序編號 則結(jié)點i的雙親結(jié)點為i 2 結(jié)點i的左孩子為2i 結(jié)點i的右孩子為2i 1 5 3二叉樹的邏輯結(jié)構(gòu) 性質(zhì)5表明 在完全二叉樹中 結(jié)點的層序編號反映了結(jié)點之間的邏輯關(guān)系 完全二叉樹的基本性質(zhì) 二叉樹的抽象數(shù)據(jù)類型定義 ADTBiTreeData由一個根結(jié)點和兩棵互不相交的左右子樹構(gòu)成 結(jié)點具有相同數(shù)據(jù)類型及層次關(guān)系OperationInitBiTree前置條件 無輸入 無功能 初始化一棵二叉樹輸出 無后置條件 構(gòu)造一個空的二叉樹 5 3二叉樹的邏輯結(jié)構(gòu) DestroyBiTree前置條件 二叉樹已存在輸入 無功能 銷毀一棵二叉樹輸出 無后置條件 釋放二叉樹占用的存儲空間InsertL前置條件 二叉樹已存在輸入 數(shù)據(jù)值x 指針parent功能 將數(shù)據(jù)域為x的結(jié)點插入到二叉樹中 作為結(jié)點parent的左孩子 如果結(jié)點parent原來有左孩子 則將結(jié)點parent原來的左孩子作為結(jié)點x的左孩子輸出 無后置條件 如果插入成功 得到一個新的二叉樹 二叉樹的抽象數(shù)據(jù)類型定義 5 3二叉樹的邏輯結(jié)構(gòu) DeleteL前置條件 二叉樹已存在輸入 指針parent功能 在二叉樹中刪除結(jié)點parent的左子樹輸出 無后置條件 如果刪除成功 得到一個新的二叉樹Search前置條件 二叉樹已存在輸入 數(shù)據(jù)值x功能 在二叉樹中查找數(shù)據(jù)元素x輸出 指向該元素結(jié)點的指針后置條件 二叉樹不變 二叉樹的抽象數(shù)據(jù)類型定義 5 3二叉樹的邏輯結(jié)構(gòu) PreOrder前置條件 二叉樹已存在輸入 無功能 前序遍歷二叉樹輸出 二叉樹中結(jié)點的一個線性排列后置條件 二叉樹不變InOrder前置條件 二叉樹已存在輸入 無功能 中序遍歷二叉樹輸出 二叉樹中結(jié)點的一個線性排列后置條件 二叉樹不變 二叉樹的抽象數(shù)據(jù)類型定義 5 3二叉樹的邏輯結(jié)構(gòu) PostOrder前置條件 二叉樹已存在輸入 無功能 后序遍歷二叉樹輸出 二叉樹中結(jié)點的一個線性排列后置條件 二叉樹不變LeverOrder前置條件 二叉樹已存在輸入 無功能 層序遍歷二叉樹輸出 二叉樹中結(jié)點的一個線性排列后置條件 二叉樹不變endADT 二叉樹的抽象數(shù)據(jù)類型定義 5 3二叉樹的邏輯結(jié)構(gòu) 二叉樹的遍歷操作 二叉樹的遍歷是指從根結(jié)點出發(fā) 按照某種次序訪問二叉樹中的所有結(jié)點 使得每個結(jié)點被訪問一次且僅被訪問一次 二叉樹遍歷操作的結(jié)果 5 3二叉樹的邏輯結(jié)構(gòu) 二叉樹的遍歷方式 DLR LDR LRD DRL RDL RLD 如果限定先左后右 則二叉樹遍歷方式有三種 前序 DLR中序 LDR后序 LRD 層序遍歷 按二叉樹的層序編號的次序訪問各結(jié)點 5 3二叉樹的邏輯結(jié)構(gòu) 考慮二叉樹的組成 前序 根 遍歷若二叉樹為空 則空操作返回 否則 訪問根結(jié)點 前序遍歷根結(jié)點的左子樹 前序遍歷根結(jié)點的右子樹 5 3二叉樹的邏輯結(jié)構(gòu) 前序遍歷序列 ABDGCEF 二叉樹的遍歷操作 中序 根 遍歷若二叉樹為空 則空操作返回 否則 中序遍歷根結(jié)點的左子樹 訪問根結(jié)點 中序遍歷根結(jié)點的右子樹 5 3二叉樹的邏輯結(jié)構(gòu) 中序遍歷序列 DGBAECF 二叉樹的遍歷操作 后序 根 遍歷若二叉樹為空 則空操作返回 否則 后序遍歷根結(jié)點的左子樹 后序遍歷根結(jié)點的右子樹 訪問根結(jié)點 5 3二叉樹的邏輯結(jié)構(gòu) 后序遍歷序列 GDBEFCA 二叉樹的遍歷操作 層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層 即根結(jié)點 開始 從上至下逐層遍歷 在同一層中 則按從左到右的順序?qū)Y(jié)點逐個訪問 5 3二叉樹的邏輯結(jié)構(gòu) 層序遍歷序列 ABCDEFG 二叉樹的遍歷操作 5 3二叉樹的邏輯結(jié)構(gòu) a b c d e f 二叉樹遍歷操作練習(xí) 前序遍歷結(jié)果 a b cd ef中序遍歷結(jié)果 a b c d e f后序遍歷結(jié)果 abcd ef 5 3二叉樹的邏輯結(jié)構(gòu) 若已知一棵二叉樹的前序 或中序 或后序 或?qū)有?序列 能否唯一確定這棵二叉樹呢 例 已知前序序列為ABC 則可能的二叉樹有5種 二叉樹的遍歷操作 5 3二叉樹的邏輯結(jié)構(gòu) 例 已知前序遍歷序列為ABC 后序遍歷序列為CBA 則下列二叉樹都滿足條件 若已知一棵二叉樹的前序序列和后序序列 能否唯一確定這棵二叉樹呢 二叉樹的遍歷操作 若已知一棵二叉樹的前序序列和中序序列 能否唯一確定這棵二叉樹呢 怎樣確定 例如 已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI 如何構(gòu)造該二叉樹呢 5 3二叉樹的邏輯結(jié)構(gòu) 二叉樹的遍歷操作 前序 ABCDEFGHI中序 BCAEDGHFI 前序 BC中序 BC 5 3二叉樹的邏輯結(jié)構(gòu) 前序 DEFGHI中序 EDGHFI 前序 FGHI中序 GHFI 5 3二叉樹的邏輯結(jié)構(gòu) 前序 DEFGHI中序 EDGHFI 1 根據(jù)前序序列的第一個元素建立根結(jié)點 2 在中序序列中找到該元素 確定根結(jié)點的左右子樹的中序序列 3 在前序序列中確定左右子樹的前序序列 4 由左子樹的前序序列和中序序列建立左子樹 5 由右子樹的前序序列和中序序列建立右子樹 5 3二叉樹的邏輯結(jié)構(gòu) 已知一棵二叉樹的前序序列和中序序列 構(gòu)造該二叉樹的過程如下 二叉樹的遍歷操作 順序存儲結(jié)構(gòu) 二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的結(jié)點 并且結(jié)點的存儲位置 下標(biāo) 應(yīng)能體現(xiàn)結(jié)點之間的邏輯關(guān)系 父子關(guān)系 如何利用數(shù)組下標(biāo)來反映結(jié)點之間的邏輯關(guān)系 完全二叉樹和滿二叉樹中結(jié)點的序號可以唯一地反映出結(jié)點之間的邏輯關(guān)系 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 完全二叉樹的順序存儲 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 以編號為下標(biāo) 二叉樹的順序存儲 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 以編號為下標(biāo) 按照完全二叉樹編號 一棵斜樹的順序存儲會怎樣呢 深度為k的右斜樹 k個結(jié)點需分配2k 1個存儲單元 一棵二叉樹改造后成完全二叉樹形態(tài) 需增加很多空結(jié)點 造成存儲空間的浪費 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 二叉樹的順序存儲結(jié)構(gòu)一般僅存儲完全二叉樹 二叉鏈表 基本思想 令二叉樹的每個結(jié)點對應(yīng)一個鏈表結(jié)點 鏈表結(jié)點除了存放與二叉樹結(jié)點有關(guān)的數(shù)據(jù)信息外 還要設(shè)置指示左右孩子的指針 結(jié)點結(jié)構(gòu) 其中 data 數(shù)據(jù)域 存放該結(jié)點的數(shù)據(jù)信息 lchild 左指針域 存放指向左孩子的指針 rchild 右指針域 存放指向右孩子的指針 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) templatestructBiNode Tdata BiNode lchild rchild 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 二叉鏈表 二叉鏈表 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 具有n個結(jié)點的二叉鏈表中 有多少個空指針 二叉鏈表 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 具有n個結(jié)點的二叉鏈表中 有n 1個空指針 二叉鏈表存儲結(jié)構(gòu)的類聲明 templateclassBiTree public BiTree root NULL BiTree BiNode root BiTree voidPreOrder BiNode root voidInOrder BiNode root voidPostOrder BiNode root voidLeverOrder BiNode root private BiNode root voidCreat BiNode root voidRelease BiNode root 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 前序遍歷 遞歸算法 templatevoidBiTree PreOrder BiNode root if root NULL return else coutdata PreOrder root lchild PreOrder root rchild 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 前序遍歷算法的執(zhí)行軌跡 二叉樹前序遍歷的非遞歸算法的關(guān)鍵 在前序遍歷過某結(jié)點的整個左子樹后 如何找到該結(jié)點的右子樹的根指針 解決辦法 在訪問完該結(jié)點后 將該結(jié)點的指針保存在棧中 以便以后能通過它找到該結(jié)點的右子樹 在前序遍歷中 設(shè)要遍歷二叉樹的根指針為root 則有兩種可能 若root NULL 則表明 如何處理 若root NULL 則表明 如何處理 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 前序遍歷 非遞歸算法 訪問結(jié)點序列 A 棧S內(nèi)容 B D A B 前序遍歷的非遞歸實現(xiàn) 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) A D B C 訪問結(jié)點序列 A 棧S內(nèi)容 B D A 前序遍歷的非遞歸實現(xiàn) 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) A D B C D 訪問結(jié)點序列 A 棧S內(nèi)容 B D C 前序遍歷的非遞歸實現(xiàn) 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) A D B C C 1 棧s初始化 2 循環(huán)直到root為空且棧s為空2 1當(dāng)root不空時循環(huán)2 1 1輸出root data 2 1 2將指針root的值保存到棧中 2 1 3繼續(xù)遍歷root的左子樹2 2如果棧s不空 則2 2 1將棧頂元素彈出至root 2 2 2準(zhǔn)備遍歷root的右子樹 前序遍歷 非遞歸算法 偽代碼 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 前序遍歷 非遞歸算法 偽代碼 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) templatevoidBiTree PreOrder BiNode root top 1 采用順序棧 并假定不會發(fā)生上溢while root NULL top 1 while root NULL coutdata s top root root root lchild if top 1 root s top root root rchild 中序遍歷 遞歸算法 templatevoidBiTree InOrder BiNode root if root NULL return else InOrder root lchild coutdata InOrder root rchild 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 后序遍歷 遞歸算法 templatevoidBiTree PostOrder BiNode root if root NULL return else PostOrder root lchild PostOrder root rchild coutdata 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 層序遍歷 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 遍歷序列 A A B C B D C E F G D E F G 層序遍歷 隊列Q初始化 2 如果二叉樹非空 將根指針入隊 3 循環(huán)直到隊列Q為空3 1q 隊列Q的隊頭元素出隊 3 2訪問結(jié)點q的數(shù)據(jù)域 3 3若結(jié)點q存在左孩子 則將左孩子指針入隊 3 4若結(jié)點q存在右孩子 則將右孩子指針入隊 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 二叉樹的建立 為了建立一棵二叉樹 將二叉樹中每個結(jié)點的空指針引出一個虛結(jié)點 其值為一特定值如 以標(biāo)識其為空 把這樣處理后的二叉樹稱為原二叉樹的擴展二叉樹 為什么如此處理 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 如何由一種遍歷序列生成該二叉樹 遍歷是二叉樹各種操作的基礎(chǔ) 可以在遍歷的過程中進(jìn)行各種操作 例如建立一棵二叉樹 擴展二叉樹的前序遍歷序列 AB D C 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 二叉樹的建立 設(shè)二叉樹中的結(jié)點均為一個字符 假設(shè)擴展二叉樹的前序遍歷序列由鍵盤輸入 root為指向根結(jié)點的指針 二叉鏈表的建立過程是 首先輸入根結(jié)點 若輸入的是一個 字符 則表明該二叉樹為空樹 即root NULL 否則輸入的字符應(yīng)該賦給root data 之后依次遞歸建立它的左子樹和右子樹 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 二叉樹的建立 templateBiTree BiTree BiNode root creat root voidBiTree Creat BiNode root cin ch if ch root NULL else root newBiNode root data ch creat root lchild creat root rchild 建立二叉遞歸算法 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 二叉樹算法設(shè)計練習(xí) 遍歷二叉樹是二叉樹各種操作的基礎(chǔ) 遍歷算法中對每個結(jié)點的訪問操作可以是多種形式及多個操作 根據(jù)遍歷算法的框架 適當(dāng)修改訪問操作的內(nèi)容 可以派生出很多關(guān)于二叉樹的應(yīng)用算法 voidInOrder BiNode root if root NULL return else InOrder root lchild coutdata InOrder root rchild 二叉樹算法設(shè)計練習(xí) 設(shè)計算法求二叉樹的結(jié)點個數(shù) voidCount BiNode root n為全局量并已初始化為0 if root Count root lchild n Count root rchild 二叉樹算法設(shè)計練習(xí) 設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點 voidPreOrder BiNode root if root if root lchild 二叉樹算法設(shè)計練習(xí) 設(shè)計算法求二叉樹的深度 intDepth BiNode root if root NULL return0 else hl Depth root lchild hr Depth root rchild returnmax hl hr 1 二叉樹算法設(shè)計練習(xí) 設(shè)計算法求樹中結(jié)點x的第i個孩子 templateTNode Search TNode root Tx inti if root data x j 1 p root firstchild while p NULL templatestructTNode Tdata TNode firstchild rightsib 三叉鏈表 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 在二叉鏈表中 如何求某結(jié)點的雙親 三叉鏈表 在二叉鏈表的基礎(chǔ)上增加了一個指向雙親的指針域 結(jié)點結(jié)構(gòu) 其中 data lchild和rchild三個域的含義同二叉鏈表的結(jié)點結(jié)構(gòu) parent域為指向該結(jié)點的雙親結(jié)點的指針 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 三叉鏈表 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 三叉鏈表的靜態(tài)鏈表形式 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 線索鏈表 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 如何保存二叉樹的某種遍歷序列 中序遍歷序列 DGBAFCF 如果二叉樹不改變 如何保存 線索鏈表 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 如何保存二叉樹的某種遍歷序列 中序遍歷序列 DGBAFCF 如果二叉樹改變 如何保存 線索鏈表 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 如何保存二叉樹的某種遍歷序列 中序遍歷序列 DGBAFCF 如何將二叉鏈表與中序鏈表結(jié)合 線索鏈表 線索 將二叉鏈表中的空指針域指向前驅(qū)結(jié)點和后繼結(jié)點的指針被稱為線索 線索化 使二叉鏈表中結(jié)點的空鏈域存放其前驅(qū)或后繼信息的過程稱為線索化 線索二叉樹 加上線索的二叉樹稱為線索二叉樹 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 如何保存二叉樹的某種遍歷序列 將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點和后繼結(jié)點 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 結(jié)點結(jié)構(gòu) 線索鏈表 enumflag Child Thread templatestructThrNode Tdata ThrNode lchild rchild flagltag rtag 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 線索鏈表 結(jié)點結(jié)構(gòu) 二叉樹的遍歷方式有4種 故有4種意義下的前驅(qū)和后繼 相應(yīng)的有4種線索二叉樹 前序線索二叉樹 中序線索二叉樹 后序線索二叉樹 層序線索二叉樹 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 線索二叉樹 中序線索二叉樹 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 線索二叉樹 中序序列 DGBAECF templateclassInThrBiTree public InThrBiTree ThrNode root InThrBiTree ThrNode Next ThrNode p voidInOrder ThrNode root private ThrNode root voidCreat ThrNode root voidThrBiTree ThrNode root 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序線索鏈表類的聲明 分析 建立線索鏈表 實質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索 而前驅(qū)或后繼的信息只有在遍歷該二叉樹時才能得到 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序線索鏈表的建立 構(gòu)造函數(shù) A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 已經(jīng)建立起二叉鏈表 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 1 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 1 1 1 1 1 1 A 頭指針 B C D E F G 0 0 0 0 0 0 0 0 0 0 0 0 0 0 中序線索鏈表的建立過程 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序遍歷二叉鏈表p為正在訪問的結(jié)點pre為剛訪問的結(jié)點 1 1 1 1 1 1 1 1 在遍歷過程中 訪問當(dāng)前結(jié)點root的操作為 如果root的左 右指針域為空 則將相應(yīng)標(biāo)志置1 若root的左指針域為空 則令其指向它的前驅(qū) 這需要設(shè)指針pre始終指向剛剛訪問過的結(jié)點 顯然pre的初值為NULL 若pre的右指針域為空 則令其指向它的后繼 即當(dāng)前訪問的結(jié)點root 令pre指向剛剛訪問過的結(jié)點root 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序線索鏈表的建立 1 建立二叉鏈表 將每個結(jié)點的左右標(biāo)志置為0 2 遍歷二叉鏈表 建立線索 2 1如果二叉鏈表root為空 則空操作返回 2 2對root的左子樹建立線索 2 3對根結(jié)點root建立線索 2 3 1若root沒有左孩子 則為root加上前驅(qū)線索 2 3 2若root沒有右孩子 則將root右標(biāo)志置為1 2 3 3若結(jié)點pre右標(biāo)志為1 則為pre加上后繼線索 2 3 4令pre指向剛剛訪問的結(jié)點root 2 4對root的右子樹建立線索 5 4二叉樹的存儲結(jié)構(gòu)及實現(xiàn) 中序線索鏈表的建立 構(gòu)造函數(shù) 5 5樹 森林與二叉樹的轉(zhuǎn)換 是哪些樹結(jié)構(gòu)的存儲結(jié)構(gòu) 樹和二叉樹之間具有對應(yīng)關(guān)系 5 5樹 森林與二叉樹的轉(zhuǎn)換 樹和二叉樹之間的對應(yīng)關(guān)系樹 兄弟關(guān)系二叉樹 雙親和右孩子樹 雙親和長子二叉樹 雙親和左孩子 5 5樹 森林與二叉樹的轉(zhuǎn)換 1 兄弟加線 樹和二叉樹之間的對應(yīng)關(guān)系 5 5樹 森林與二叉樹的轉(zhuǎn)換 2 保留雙親與第一孩子連線 刪去與其他孩子的連線 樹和二叉樹之間的對應(yīng)關(guān)系 1 兄弟加線 3 順時針轉(zhuǎn)動 使之層次分明 5 5樹 森林與二叉樹的轉(zhuǎn)換 樹和二叉樹之間的對應(yīng)關(guān)系 2 保留雙親與第一孩子連線 刪去與其他孩子的連線 1 兄弟加線 A B C D E F G 3 順時針轉(zhuǎn)動 使之層次分明 5 5樹 森林與二叉樹的轉(zhuǎn)換 樹和二叉樹之間的對應(yīng)關(guān)系 2 保留雙親與第一孩子連線 刪去與其他孩子的連線 1 兄弟加線 樹轉(zhuǎn)換為二叉樹 加線 樹中所有相鄰兄弟之間加一條連線 去線 對樹中的每個結(jié)點 只保留它與第一個孩子結(jié)點之間的連線 刪去它與其它孩子結(jié)點之間的連線 層次調(diào)整 以根結(jié)點為軸心 將樹順時針轉(zhuǎn)動一定的角度 使之層次分明 5 5樹 森林與二叉樹的轉(zhuǎn)換 ABEFCDG ABEFCDG 樹的前序遍歷等價于二叉樹的前序遍歷 5 5樹 森林與二叉樹的轉(zhuǎn)換 EFBCGDA EFBCGDA 樹的后序遍歷等價于二叉樹的中序遍歷 5 5樹 森林與二叉樹的轉(zhuǎn)換 森林轉(zhuǎn)換為二叉樹 將森林中的每棵樹轉(zhuǎn)換成二叉樹 從第二棵二叉樹開始 依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子 當(dāng)所有二叉樹連起來后 此時所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹 5 5樹 森林與二叉樹的轉(zhuǎn)換 5 5樹 森林與二叉樹的轉(zhuǎn)換 二叉樹轉(zhuǎn)換為樹或森林 加線 若某結(jié)點x是其雙親y的左孩子 則把結(jié)點x的右孩子 右孩子的右孩子 都與結(jié)點y用線連起來 去線 刪去原二叉樹中所有的雙親結(jié)點與右孩子結(jié)點的連線 層次調(diào)整 整理由 兩步所得到的樹或森林 使之層次分明 5 5樹 森林與二叉樹的轉(zhuǎn)換 5 5樹 森林與二叉樹的轉(zhuǎn)換 森林的遍歷 森林有兩種遍歷方法 前序 根 遍歷 前序遍歷森林即為前序遍歷森林中的每一棵樹 后序 根 遍歷 后序遍歷森林即為后序遍歷森林中的每一棵樹 5 5樹 森林與二叉樹的轉(zhuǎn)換 相關(guān)概念 葉子結(jié)點的權(quán)值 對葉子結(jié)點賦予的一個有意義的數(shù)值量 二叉樹的帶權(quán)路徑長度 設(shè)二叉樹具有n個帶權(quán)值的葉子結(jié)點 從根結(jié)點到各個葉子結(jié)點的路徑長度與相應(yīng)葉子結(jié)點權(quán)值的乘積之和 記為 WPL 5 6哈夫曼樹及哈夫曼編碼 哈夫曼樹 給定一組具有確定權(quán)值的葉子結(jié)點 帶權(quán)路徑長度最小的二叉樹 例 給定4個葉子結(jié)點 其權(quán)值分別為 2 3 4 7 可以構(gòu)造出形狀不同的多個二叉樹 5 6哈夫曼樹及哈夫曼編碼 WPL 32WPL 41WPL 30 哈夫曼樹的特點 1 權(quán)值越大的葉子結(jié)點越靠近根結(jié)點 而權(quán)值越小的葉子結(jié)點越遠(yuǎn)離根結(jié)點 2 只有度為0 葉子結(jié)點 和度為2 分支結(jié)點 的結(jié)點 不存在度為1的結(jié)點 5 6哈夫曼樹及哈夫曼編碼 2 3 4 7 WPL 32WPL 41WPL 30 2 3 4 7 7 4 2 3 哈夫曼算法基本思想 初始化 由給定的n個權(quán)值 w1 w2 wn 構(gòu)造n棵只有一個根結(jié)點的二叉樹 從而得到一個二叉樹集合F T1 T2 Tn 選取與合并 在F中選取根結(jié)點的權(quán)值最小的兩棵二叉樹分別作為左 右子樹構(gòu)造一棵新的二叉樹 這棵新二叉樹的根結(jié)點的權(quán)值為其左 右子樹根結(jié)點的權(quán)值之和 刪除與加入 在F中刪除作為左 右子樹的兩棵二叉樹 并將新建立的二叉樹加入