【正文】 言 ， 可以有三條搜索路徑： ?1． 先上后下 的按層次遍歷； ?2． 先左 （ 子樹 ） 后右 （ 子樹 ） 的遍歷； ?3． 先右 （ 子樹 ） 后左 （ 子樹 ） 的遍歷 。 “遍歷 ”是任何類型均有的操作， 對線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因為每個結(jié)點均只有一個后繼 )， 故不需要另加討論。 即找一個完整而有規(guī)律的走法，得到樹中所有結(jié)點的一個線性排列。 parent lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 2． 三叉鏈表 A D E B C F ? ? ? ? ? ? ? root ? A B D C F E 練習：畫出下面二叉樹的三叉鏈表。 struct TriTNode *lchild, *rchild, *parent。 // 左右孩子指針 } BiTNode, *BiTree。 a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11 二、二叉樹的鏈式存儲表示 1. 二叉鏈表 2．三叉鏈表 3．線索鏈表 typedef struct BiTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 一、 二叉樹的順序存儲表示 實現(xiàn)： 按滿二叉樹中結(jié)點的編號，依次存放二叉 樹中的數(shù)據(jù)元素。 二叉樹的存儲結(jié)構(gòu) 二、 二叉樹的鏈式存儲表示 一、 二叉樹的順序存儲表示 define MAX_TREE_SIZE 100 // 二叉樹的最大結(jié)點數(shù) typedef TElemType SqBiTree[MAX_TREE_SIZE]。 特點 : (1)葉子結(jié)點只可能在層次最底的兩層上出現(xiàn) .(2)對任一結(jié)點，若其右分支下子孫的最大層次為 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 證明： 設(shè) 完全二叉樹的深度為 k 即 k1 ≤ log2 n k 因為 k 只能是整數(shù)，因此， k = ?log2n? + 1 ? 性質(zhì) 4 ： 具有 n 個結(jié)點的完全二叉樹的 深度 為 ?log2n? +1 則根據(jù)性質(zhì) 2得 2k11 n ≤ 2k 1 2k1≤ n 2k ?性質(zhì) 5 ： 若對含 n 個結(jié)點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親 , 否則，編號為 ?i/2? 的結(jié)點為其 雙親 結(jié)點 。 ?性質(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 = n 1 由此， n1 + 2n2 = n0 + n1 + n2 1 即 n0 = n2 + 1 兩類 特殊 的二叉樹： 滿二叉樹 ： 指的是深度為 k且含有 2k1個結(jié)點的二叉樹。 (i≥ 1) 用歸納法證明 ： 歸納基 ： 歸納假設(shè)： 歸納證明： i = 1 層時，只有一個根結(jié)點， 2i1 = 20 = 1； 假設(shè)對所有的 j， 1≤ j ? i， 命題成立 。 DeleteChild(T, p, LR)。 DestroyBiTree(amp。 ClearBiTree(amp。 InsertChild(T, p, LR, c) // 根據(jù) LR為 0或 1，插入 c為 T中 p所指結(jié)點的左或右子樹。 CreateBiTree(amp。 Assign(T, amp。 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 思考：二叉樹與樹的區(qū)別？ 二叉樹與無序樹的區(qū)別 二叉樹與有序樹的區(qū)別 二叉樹就是度為 2的有序樹嗎？ 所以，二叉樹不是前面定義的樹的特殊形式， 而是另外一種數(shù)據(jù)結(jié)構(gòu)。 A B C D E F G H K 根結(jié)點 左子樹 右子樹 二叉樹的五種基本形態(tài)： 空樹 只含根結(jié)點 L R 右子樹為空樹 左子樹為空樹 左右子樹均不為空樹 二叉樹特點： ?每個結(jié)點至多有二棵子樹 (即不存在度大于 2的結(jié)點 )。 有序樹： (１ ) 有確定的根； (２ ) 樹根和子樹根之間為有向關(guān)系。 A root B E F K L C G D H I J M F 子樹之間不存在確定的次序關(guān)系 （ 能互換 ） 。 任何一棵非空樹是一個二元組 Tree = （ root， F） 其中： root 被稱為根結(jié)點， F 被稱為子樹森林。 祖先 結(jié)點：從根結(jié)點到該結(jié)點所經(jīng)分支上的所有結(jié)點。 雙親 結(jié)點：孩子結(jié)點的上層結(jié)點叫該結(jié)點的雙親結(jié)點。 樹中葉子結(jié)點所在的最大層次。 D H I J M （終端結(jié)點） （非終端結(jié)點） (從根到結(jié)點的 )路徑 ： 結(jié)點的層次 : 樹 的 深度： 由從 根 到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成。 度為零的結(jié)點。 分支的個數(shù)。T, amp。T) // 將樹清空 刪除類： DestroyTree(amp。T, amp。T) // 初始化構(gòu)造空樹 插入類： CreateTree(amp。 (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root, (2) 當 n1時，其余結(jié)點可分為 m (m0)個互 不相交的有限集 T1, T2, … , Tm, 其中每一 個子集本身又是一棵樹 ,稱為根 root的子樹。 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。 樹的類型定義和基本術(shù)語 二叉樹的類型定義及性質(zhì) 二叉樹的存儲結(jié)構(gòu) 二叉樹的遍歷 線索二叉樹 樹和森林 哈夫曼樹與哈夫曼編碼 樹的類型定義和基本術(shù)語 ? 樹的定義 ? 定義：樹 (Tree)是 n(n≥0)個結(jié)點的有限集 T， 其中： – 當 n≥1時，有且僅有一個特定的結(jié)點，稱為樹的 根 (Root)， – 當 n 1時，其余結(jié)點可分為 m(m0)個 互不相交 的有限集 T1,T2,…… Tm，其中每一個集合本身又是一棵樹，稱為根的 子樹 (SubTree)。 ? 特點： – 樹中各子樹是互不相交的集合。 ?A 只有根結(jié)點的 樹 A B C D E F G H I J K L M 有子樹的 樹 根 子 樹 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)) 數(shù)據(jù)對象 D： D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系 R： ADT Tree { 若 D為空集，則稱為空樹； 否則 : } ADT Tree 基本操作 P： 基本操作： 查 找 類 插 入 類 刪 除 類 Root(T) // 求樹的根結(jié)點 查找類： Value(T, cur_e) // 求當前結(jié)點的元素值 Parent(T, cur_e) // 求當前結(jié)點的雙親結(jié)點 LeftChild(T, cur_e) // 求當前結(jié)點的最左孩子 RightSibling(T, cur_e) // 求當前結(jié)點的右兄弟 TreeEmpty(T) // 判定樹是否為空樹 TreeDepth(T) // 求樹的 深度 TraverseTree( T, Visit() ) // 遍歷 樹中結(jié)點的最大層次 InitTree(amp。T, definition) // 按定義構(gòu)造樹 Assign(T, cur_e, value) // 給當前結(jié)點賦值 InsertChild(amp。p, i, c) // 將以 c為根的樹插入為結(jié)點 p的第 i棵子樹 ClearTree(amp。T) // 銷毀樹結(jié)構(gòu) DeleteChild(amp。p, i) // 刪除 T中結(jié)點 p的第 i棵子樹 樹的四種表示法： 一、樹形表示法 二、凹入表示法 三、嵌套集合表示法 四、廣義表表示法 一、樹形表示法 二、凹入表示法 三、嵌套集合表示法 四、廣義表表示法 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)) 一、樹形表示法 二、凹入表示法 三、嵌套集合表示法 四、廣義表表示法 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 練習 基 本 術(shù) 語 結(jié) 點 : 結(jié)點的度 : 樹 的 度 : 葉子結(jié)點 : 分支結(jié)點 : 一個數(shù)據(jù)元素 +若干指向子樹的分支。 (結(jié)點擁有子樹數(shù)目 ) 樹中所有結(jié)點的度的最大值。 度大于零的結(jié)點。 A B C D E F G H I J M K L 定義根結(jié)點的層次為 1,第 t層結(jié)點子樹的根結(jié)點的層次為 t+1。 孩子 結(jié)點：某結(jié)點子樹的根結(jié)點稱為該結(jié)點的孩子結(jié)點。 兄弟 結(jié)點：同一雙親的孩子結(jié)點。 子孫 結(jié)點：以某結(jié)點為根的子樹中的任一結(jié)點稱為此結(jié)點 ~。 森林： 是 m（ m≥ 0）棵互 不相交的樹的集合。 子樹之間存在確定的次序關(guān)系 （ 不能互換 ） 。 有向樹： 無序 樹： D H I J M D I H J M =