【正文】 樹的類型定義 二叉樹的類型定義 二叉樹的存儲結(jié)構(gòu) 二叉樹的遍歷 線索二叉樹 樹和森林的表示方法 樹和森林的遍歷 哈夫曼樹與哈夫曼編碼 樹的類型定義 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合。 若 D為空集，則稱為空樹 。 否則 : (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root； (2) 當(dāng) n1時，其余結(jié)點可分為 m (m0)個互 不相交的有限集 T1, T2, … , Tm，其中每一 棵子集本身又是一棵符合本定義的樹， 稱為根 root的子樹。 數(shù)據(jù)關(guān)系 R： A B C D E F G H I J M K L A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) T1 T3 T2 樹根 例如 : 基本操作： 查 找 類 插 入 類 刪 除 類 Root(T) // 求樹的根結(jié)點 查找類： Value(T, cur_e) // 求當(dāng)前結(jié)點的元素值 Parent(T, cur_e) // 求當(dāng)前結(jié)點的雙親結(jié)點 LeftChild(T, cur_e) // 求當(dāng)前結(jié)點的最左孩子 RightSibling(T, cur_e) // 求當(dāng)前結(jié)點的右兄弟 TreeEmpty(T) // 判定樹是否為空樹 TreeDepth(T) // 求樹的深度 TraverseTree( T, Visit() ) // 遍歷 InitTree(amp。T) // 初始化置空樹 插入類： CreateTree(amp。T, definition) // 按定義構(gòu)造樹 Assign(T, cur_e, value) // 給當(dāng)前結(jié)點賦值 InsertChild(amp。T, amp。p, i, c) // 將以 c為根的樹插入為結(jié)點 p的第 i棵子樹 ClearTree(amp。T) // 將樹清空 刪除類： DestroyTree(amp。T) // 銷毀樹的結(jié)構(gòu) DeleteChild(amp。T, amp。p, i) // 刪除結(jié)點 p的第 i棵子樹 A B C D E F G H I J M K L A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) T1 T3 T2 樹根 例如 : 樹形圖表示的例子 A B K E L F D H M J I C G 嵌套集合表示法 A B C D E K L F G H I J M 凹入表示法 （ A(B(E(K,L),F),C(G),D(H(M),I,J))) 廣義表表示法 A B C D E F G H I J M K L 對比 樹型結(jié)構(gòu) 和 線性結(jié)構(gòu)的結(jié)構(gòu)特點 線性結(jié)構(gòu) 樹型結(jié)構(gòu) 第一個數(shù)據(jù)元素 (無前驅(qū) ) 根結(jié)點 (無前驅(qū) ) 最后一個數(shù)據(jù)元素 (無后繼 ) 多個葉子結(jié)點 (無后繼 ) 其它數(shù)據(jù)元素 (一個前驅(qū)、 一個后繼 ) 其它數(shù)據(jù)元素 (一個前驅(qū)、 多個后繼 ) 基 本 術(shù) 語 結(jié)點 : 結(jié)點的度 : 樹的度 : 葉子結(jié)點 : 分支結(jié)點 : 數(shù)據(jù)元素 +若干指向子樹的分支 分支的個數(shù) 樹中所有結(jié)點的度的最大值 度為零的結(jié)點 度大于零的結(jié)點 D H I J M (從根到結(jié)點的 )路徑 ： 孩子 結(jié)點 、 雙親 結(jié)點 兄弟 結(jié)點 、 堂兄弟 祖先 結(jié)點 、 子孫 結(jié)點 結(jié)點的層次 : 樹的深度： 由從 根 到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成 A B C D E F G H I J M K L 假設(shè)根結(jié)點的層次為 1，第 l 層的結(jié)點的子樹根結(jié)點的層次為 l+1 樹中葉子結(jié)點所在的最大層次 (１ ) 有確定的根； (２ ) 樹根和子樹根之間為有向關(guān)系。 有向樹： 有序樹： 子樹之間存在確定的次序關(guān)系。 無序樹： 子樹之間不存在確定的次序關(guān)系。 任何一棵非空樹是一個二元組 Tree = （ root， F） 其中： root 被稱為根結(jié)點 F 被稱為子樹森林 森林： 是 m（ m≥ 0）棵互 不相交的樹的集合 A root B C D E F G H I J M K L F 二叉樹的類型定義 二叉樹或為 空樹 ，或是由一個 根結(jié)點 加上 兩棵 分別稱為 左子樹 和 右子樹的、 互不交的 二叉樹 組成。 A B C D E F G H K 根結(jié)點 左子樹 右子樹 二叉樹的五種基本形態(tài)： N 空樹 只含根結(jié)點 N N N L R R 右子樹為空樹 L 左子樹為空樹 左右子樹均不為空樹 二叉樹的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 Root(T)。 Value(T, e)。 Parent(T, e)。 LeftChild(T, e)。 RightChild(T, e)。 LeftSibling(T, e)。 RightSibling(T, e)。 BiTreeEmpty(T)。 BiTreeDepth(T)。 PreOrderTraverse(T, Visit())。 InOrderTraverse(T, Visit())。 PostOrderTraverse(T, Visit())。 LevelOrderTraverse(T, Visit())。 InitBiTree(amp。T)。 Assign(T, amp。e, value)。 CreateBiTree(amp。T, definition)。 InsertChild(T, p, LR, c)。 ClearBiTree(amp。T)。 DestroyBiTree(amp。T)。 DeleteChild(T, p, LR)。 二叉樹 的重要特性 ? 性質(zhì) 1 ： 在二叉樹的第 i 層上至多有2i1 個結(jié)點 。 (i≥ 1) 用歸納法證明 ： 歸納基 ： 歸納假設(shè)： 歸納證明： i = 1 層時，只有一個根結(jié)點： 2i1 = 20 = 1； 假設(shè)對所有的 j， 1≤ j ? i， 命題成立； 二叉樹上每個結(jié)點至多有兩棵子樹， 則第 i 層的結(jié)點數(shù) = 2i2? 2 = 2i1 。 ?性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k1 個結(jié)點（ k≥ 1）。 證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點數(shù)至多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 。 ? 性質(zhì) 3 ： 對任何一棵二叉樹，若它含有 n0 個葉子結(jié)點、 n2 個度為 2 的結(jié)點，則必存在關(guān)系式： n0 = n2+1。 證明： 設(shè) 二叉樹上結(jié)點總數(shù) n = n0 + n1 + n2 又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n1 = n0 + n1 + n2 1 由此， n0 = n2 + 1 。 兩類 特殊 的二叉樹： 滿二叉樹 ： 指的是深度為 k且含有 2k1個結(jié)點的二叉樹。 完全二叉樹 ： 樹中所含的 n 個結(jié)點和滿二叉樹中 編號為 1 至 n 的結(jié)點 一一對應(yīng)。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h i j ? 性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的 深度為 ? log2n? +1 。 證明： 設(shè) 完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k1≤ n 2k 即 k1 ≤ log2 n k 因為 k 只能是整數(shù)，因此， k =?log2n? + 1 。 ?性質(zhì) 5 ： 若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親， 否則，編號為 ?i/2? 的結(jié)點為其 雙親 結(jié)點； (2) 若 2in，則該結(jié)點無左孩子， 否則，編號為 2i 的結(jié)點為其 左孩子 結(jié)點； (3) 若 2i+1n，則該結(jié)點無右孩子結(jié)點， 否則，編號為 2i+1 的結(jié)點為其 右孩子 結(jié)點 。 二叉樹的存儲結(jié)構(gòu) 二、二叉樹的鏈?zhǔn)? 存儲表示 一、 二叉樹的順序 存儲表示 define MAX_TREE_SIZE 100 //