【正文】 若二叉樹為空樹，則空操作；否則， （ 1）中序遍歷左子樹； （ 2）訪問根結點； （ 3）中序遍歷右子樹。而二叉樹是非 線性結構， 每個結點有兩個后繼 ， 則存在 如何遍歷 即按什么樣的 搜索 路徑 遍歷的問題。 一、問題的提出 “訪問 ”的含義可以很廣， 如：輸出結點的信息等。 a b c d e f g h 49 二叉樹的遍歷 50 一、問題的提出 二、先左后右的遍歷算法 三、算法的遞歸描述 四、中序遍歷算法的非遞歸描述 五、遍歷算法的應用舉例 51 遍歷 ： 順著某一條搜索路徑 巡訪 二叉樹中的結點，使得每個結點 均被訪問一次 ，而且 僅被訪問一次 。 // 左右孩子指針、 雙親指針 } TriTNode, *TriTree。 C 語言的類型描述如下 : 1. 二叉鏈表 lchild data rchild 結點結構 : 45 A D E B C F ? ? ? ? ? ? ? root A B D C F E 在有 n個結點的二叉鏈表中，有 ？ 個空指針域 n+1 46 typedef struct TriTNode { // 結點結構 TElemType data。 struct BiTNode *lchild, *rchild。 特點： 結點間關系蘊含在其存儲位置中； 浪費空間，適于存滿二叉樹和完全二叉樹。樹中各結點的編號與等高度的完全二叉樹中對應位置上結點的編號相同。 39 二叉樹的存儲結構 二、 二叉樹的鏈式存儲表示 一、 二叉樹的順序存儲表示 40 二叉樹的順序存儲結構中結點的存放次序是：對該樹中每個結點進行編號 ,其編號從小到大的順序就是結點存放在連續(xù)存儲單元的先后次序。 特點 : (1)葉子結點只可能在層次最底的兩層上出現(xiàn) .(2)對任一結點，若其右分支下子孫的最大層次為 l， 則其左分支下子孫的最大層次必為 l 或 l+1. 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 37 證明： 設 完全二叉樹的深度為 k 即 k1 ≤ log2 n k 因為 k 只能是整數(shù)，因此， k = ?log2n? + 1 ? 性質 4 ： 具有 n 個結點的完全二叉樹的 深度 為 ?log2n? +1 則根據(jù)性質 2得 2k11 n ≤ 2k 1 2k1≤ n 2k 38 ?性質 5 ： 若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結點： (1) 若 i=1，則該結點是二叉樹的根，無雙親 , 否則，編號為 ?i/2? 的結點為其 雙親 結點 。 34 ?性質 2 ： 深度為 k 的二叉樹上至多含 2k1 個結點 . (k≥ 1) 證明： 基于上一條性質，深度為 k 的二叉樹上的結點數(shù)至多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 35 ? 性質 3 ： 對任何一棵二叉樹，若它含有 n0 個葉子結點、n2 個度為 2 的結點，則必存在關系式： n0 = n2+1 證明： 設 二叉樹上結點總數(shù) n = n0 + n1 + n2 又 二叉樹上分支總數(shù) b = n1 + 2n2 而 b = n 1 由此， n1 + 2n2 = n0 + n1 + n2 1 即 n0 = n2 + 1 36 兩類 特殊 的二叉樹： 滿二叉樹 ： 指的是深度為 k且含有 2k1個結點的二叉樹。 (i≥ 1) 用歸納法證明 ： 歸納基 ： 歸納假設： 歸納證明： i = 1 層時，只有一個根結點， 2i1 = 20 = 1； 假設對所有的 j， 1≤ j ? i， 命題成立 。 DeleteChild(T, p, LR)。 DestroyBiTree(amp。 30 ClearBiTree(amp。 InsertChild(T, p, LR, c) // 根據(jù) LR為 0或 1，插入 c為 T中 p所指結點的左或右子樹。 CreateBiTree(amp。 Assign(T, amp。 29 InitBiTree(amp。 PostOrderTraverse(T, Visit()) // 后序遍歷 。 PreOrderTraverse(T, Visit()) // 先序遍歷 。 BiTreeEmpty(T)。 LeftSibling(T, e)。 LeftChild(T, e)。 Value(T, e)。 N N N L R N 25 思考：二叉樹與樹的區(qū)別？ 二叉樹與無序樹的區(qū)別 二叉樹與有序樹的區(qū)別 二叉樹就是度為 2的有序樹嗎？ 所以，二叉樹不是前面定義的樹的特殊形式， 而是另外一種數(shù)據(jù)結構。 A B C D E F G H K 根結點 左子樹 右子樹 24 二叉樹的五種基本形態(tài)： 空樹 只含根結點 L R 右子樹為空樹 左子樹為空樹 左右子樹均不為空樹 二叉樹特點： ?每個結點至多有二棵子樹 (即不存在度大于 2的結點 )。 有序樹： (１ ) 有確定的根； (２ ) 樹根和子樹根之間為有向關系。 A root B E F K L C G D H I J M F 19 子樹之間不存在確定的次序關系 （ 能互換 ） 。 18 任何一棵非空樹是一個二元組 Tree = （ root， F） 其中： root 被稱為根結點， F 被稱為子樹森林。 祖先 結點：從根結點到該結點所經(jīng)分支上的所有結點。 雙親 結點：孩子結點的上層結點叫該結點的雙親結點。 樹中葉子結點所在的最大層次。 D H I J M （終端結點） （非終端結點） 17 (從根到結點的 )路徑 ： 結點的層次 : 樹 的 深度： 由從 根 到該結點所經(jīng)分支和結點構成。 度為零的結點。 分支的個數(shù)。T, amp。T) // 將樹清空 刪除類： DestroyTree(amp。T, amp。T) // 初始化構造空樹 插入類： CreateTree(amp。 (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root, (2) 當 n1時，其余結點可分為 m (m0)個互 不相交的有限集 T1, T2, …, T m, 其中每一 個子集本身又是一棵樹 ,稱為根 root的子樹。 樹是一類重要的非線性數(shù)據(jù)結構，是以分支關系定義的層次結構。1 2 樹的類型定義和基本術語 二叉樹 二叉樹的遍歷和線索二叉樹 樹和森林 哈夫曼樹與哈夫曼編碼 3 樹的類型定義和基本術語 4 ? 樹的定義 ? 定義：樹 (Tree)是 n(n≥0)個結點的有限集 T， 其中： – 當 n≥1時，有且僅有一個特定的結點，稱為樹的 根 (Root)， – 當 n 1時，其余結點可分為 m(m0)個 互不相交 的有限集 T1,T2,…… Tm，其中每一個集合本身又是一棵樹，稱為根的 子樹 (SubTree)。 ? 特點： – 樹中各子樹是互不相交的集合。 ?5 A 只有根結點的 樹 A B C D E F G H I J K L M 有子樹的 樹 根 子 樹 6 A B C D E F G H I J M K L A( ) T1 T3 T2 樹根 B(E, F(K, L)), C(G), D(H, I, J(M)) 7 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關系 R： ADT Tree { 若 D為空集，則稱為空樹； 否則 : } ADT Tree 基本操作 P： 8 基本操作： 查 找 類 插 入 類 刪 除 類 9 Root(T) // 求樹的根結點 查找類： Value(T, cur_e) // 求當前結點的元素值 Parent(T, cur_e) // 求當前結點的雙親結點 LeftChild(T, cur_e) // 求當前結點的最左孩子 RightSibling(T, cur_e) // 求當前結點的右兄弟 TreeEmpty(T) // 判定樹是否為空樹 TreeDepth(T) // 求樹的 深度 TraverseTree( T, Visit() ) // 遍歷 樹中結點的最大層次 10 InitTree(amp。T, definition) // 按定義構造樹 Assign(T, cur_e, value) // 給當前結點賦值 InsertChild(amp。p, i, c) // 將以 c為根的樹插入為結點 p的第 i棵子樹 11 ClearTree(amp。T) // 銷毀樹結構 DeleteChild(amp。p, i) // 刪除 T中結點 p的第 i棵子樹 12 樹的四種表示法： 一、樹形表示法 二、凹入表示法 三、嵌套集合表示法 四、廣義表表示法 13 一、樹形表示法 二、凹入表示法 三、嵌套集合表示法 四、廣義表表示法 A B C D F E G H I J M K L A B E K L F C G D H M I J G F K L I J M H A B D C E (A(B(E(K,L),F),C(G),D(H(M),I,J))) (樹根 (子樹 1， 子樹 2， … ， 子樹 n)) 14 一、樹形表示法 二、凹入表示法 三、嵌套集合表示法 四、廣義表表示法 A B C D F E G H J M K L A B E K G L C F D H M J ( A ( B ( E ( K, G , L), C , F ), D ( H ( M ), J ) ) ) F K L J M H A B D E G C 練習 15 基 本 術 語 16 結 點 : 結點的度 : 樹 的 度 : 葉子結點 : 分支結點 : 一個數(shù)據(jù)元素 +若干指向子樹的分支。 (結點擁有子樹數(shù)目 ) 樹中所有結點的度的最大值。 度大于零的結點。 A B C D E F G H I J M K L 定義根結點的層次為 1,第 t層結點子樹的根結點的層次為 t+1。 孩子 結點：某結點子樹的根結點稱為該結點的孩子結點。 兄弟 結點：同一雙親的孩子結點。 子孫 結點：以某結點為根的子樹中的任一結點稱為此結點 ~。 森林： 是 m（ m≥ 0）棵互 不相交的樹