【正文】 1 2 樹的類型定義和基本術(shù)語 二叉樹 二叉樹的遍歷和線索二叉樹 樹和森林 哈夫曼樹與哈夫曼編碼 3 樹的類型定義和基本術(shù)語 4 ? 樹的定義 ? 定義：樹 (Tree)是 n(n≥0)個結(jié)點(diǎn)的有限集 T， 其中： – 當(dāng) n≥1時，有且僅有一個特定的結(jié)點(diǎn)，稱為樹的 根 (Root)， – 當(dāng) n 1時，其余結(jié)點(diǎn)可分為 m(m0)個 互不相交 的有限集 T1,T2,…… Tm，其中每一個集合本身又是一棵樹，稱為根的 子樹 (SubTree)。 ? 特點(diǎn)： – 樹中各子樹是互不相交的集合。 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。 ?5 A 只有根結(jié)點(diǎn)的 樹 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ù)元素的集合。 (1) 在 D中存在唯一的稱為根的數(shù)據(jù)元素 root, (2) 當(dāng) n1時，其余結(jié)點(diǎn)可分為 m (m0)個互 不相交的有限集 T1, T2, …, T m, 其中每一 個子集本身又是一棵樹 ,稱為根 root的子樹。 數(shù)據(jù)關(guān)系 R： ADT Tree { 若 D為空集，則稱為空樹； 否則 : } ADT Tree 基本操作 P： 8 基本操作： 查 找 類 插 入 類 刪 除 類 9 Root(T) // 求樹的根結(jié)點(diǎn) 查找類： Value(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn) LeftChild(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) // 求當(dāng)前結(jié)點(diǎn)的右兄弟 TreeEmpty(T) // 判定樹是否為空樹 TreeDepth(T) // 求樹的 深度 TraverseTree( T, Visit() ) // 遍歷 樹中結(jié)點(diǎn)的最大層次 10 InitTree(amp。T) // 初始化構(gòu)造空樹 插入類： CreateTree(amp。T, definition) // 按定義構(gòu)造樹 Assign(T, cur_e, value) // 給當(dāng)前結(jié)點(diǎn)賦值 InsertChild(amp。T, amp。p, i, c) // 將以 c為根的樹插入為結(jié)點(diǎn) p的第 i棵子樹 11 ClearTree(amp。T) // 將樹清空 刪除類： DestroyTree(amp。T) // 銷毀樹結(jié)構(gòu) DeleteChild(amp。T, amp。p, i) // 刪除 T中結(jié)點(diǎn) 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 練習(xí) 15 基 本 術(shù) 語 16 結(jié) 點(diǎn) : 結(jié)點(diǎn)的度 : 樹 的 度 : 葉子結(jié)點(diǎn) : 分支結(jié)點(diǎn) : 一個數(shù)據(jù)元素 +若干指向子樹的分支。 分支的個數(shù)。 (結(jié)點(diǎn)擁有子樹數(shù)目 ) 樹中所有結(jié)點(diǎn)的度的最大值。 度為零的結(jié)點(diǎn)。 度大于零的結(jié)點(diǎn)。 D H I J M （終端結(jié)點(diǎn)） （非終端結(jié)點(diǎn)） 17 (從根到結(jié)點(diǎn)的 )路徑 ： 結(jié)點(diǎn)的層次 : 樹 的 深度： 由從 根 到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成。 A B C D E F G H I J M K L 定義根結(jié)點(diǎn)的層次為 1,第 t層結(jié)點(diǎn)子樹的根結(jié)點(diǎn)的層次為 t+1。 樹中葉子結(jié)點(diǎn)所在的最大層次。 孩子 結(jié)點(diǎn)：某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。 雙親 結(jié)點(diǎn)：孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。 兄弟 結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)。 祖先 結(jié)點(diǎn)：從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。 子孫 結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)稱為此結(jié)點(diǎn) ~。 18 任何一棵非空樹是一個二元組 Tree = （ root， F） 其中： root 被稱為根結(jié)點(diǎn)， F 被稱為子樹森林。 森林： 是 m（ m≥ 0）棵互 不相交的樹的集合。 A root B E F K L C G D H I J M F 19 子樹之間不存在確定的次序關(guān)系 （ 能互換 ） 。 子樹之間存在確定的次序關(guān)系 （ 不能互換 ） 。 有序樹： (１ ) 有確定的根； (２ ) 樹根和子樹根之間為有向關(guān)系。 有向樹： 無序 樹： D H I J M D I H J M = 20 雙親在同一層的結(jié)點(diǎn) A B C D E F G H I J K L M 結(jié)點(diǎn) A的度： 結(jié)點(diǎn) B的度： 結(jié)點(diǎn) M的度： 葉子： 結(jié)點(diǎn) A的孩子： 結(jié)點(diǎn) B的孩子： 結(jié)點(diǎn) I的雙親： 結(jié)點(diǎn) L的雙親： 結(jié)點(diǎn) B， C， D為兄弟 結(jié)點(diǎn) K， L為兄弟 樹的度： 結(jié)點(diǎn) A的層次： 結(jié)點(diǎn) M的層次： 樹的深度： 結(jié)點(diǎn) F， G為堂兄弟 結(jié)點(diǎn) A是結(jié)點(diǎn) F， G的祖先 結(jié)點(diǎn) B的子孫： 3 2 0 B， C， D E， F 3 K， L， F， G， M， I ， J D E 1 4 例 E， K， L， F 4 21 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 第一個數(shù)據(jù)元素 (無前驅(qū) ) 根結(jié)點(diǎn) (無前驅(qū) ) 最后一個數(shù)據(jù)元素 (無后繼 ) 多個葉子結(jié)點(diǎn) (無后繼 ) 其它數(shù)據(jù)元素 (一個前驅(qū)、一個后繼 ) 其它數(shù)據(jù)元素 (一個前驅(qū)、多個后繼 ) 22 二叉樹 23 二叉樹 或?yàn)?空樹 ；或是由一個 根結(jié)點(diǎn)加上 兩棵 分別稱為 左子樹 和 右子樹 的、互不相交的 二叉樹 組成。 A B C D E F G H K 根結(jié)點(diǎn) 左子樹 右子樹 24 二叉樹的五種基本形態(tài)： 空樹 只含根結(jié)點(diǎn) L R 右子樹為空樹 左子樹為空樹 左右子樹均不為空樹 二叉樹特點(diǎn)： ?每個結(jié)點(diǎn)至多有二棵子樹 (即不存在度大于 2的結(jié)點(diǎn) )。 ?二叉樹的子樹有左、右之分，其次序不能任意顛倒。 N N N L R N 25 思考：二叉樹與樹的區(qū)別？ 二叉樹與無序樹的區(qū)別 二叉樹與有序樹的區(qū)別 二叉樹就是度為 2的有序樹嗎？ 所以，二叉樹不是前面定義的樹的特殊形式， 而是另外一種數(shù)據(jù)結(jié)構(gòu)。 否 26 練習(xí)：具有 3個結(jié)點(diǎn)的二叉樹有多少種？ 27 二叉樹的主要基本操作 ： 查 找 類 插 入 類 刪 除 類 ADT BinaryTree： P121 28 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()) // 層序遍歷 。 29 InitBiTree(amp。T)。 Assign(T, amp。e, value)。 CreateBiTree(amp。T, definition)。 InsertChild(T, p, LR, c) // 根據(jù) LR為 0或 1，插入 c為 T中 p所指結(jié)點(diǎn)的左或右子樹。 p所指結(jié)點(diǎn)的原右或左子樹成為 c的右子樹。 30 ClearBiTree(amp。T)。 DestroyBiTree(amp。T)。 DeleteChild(T, p, LR)。 31 二叉樹 的重要特性 32 33 ? 性質(zhì) 1 ： 在二叉樹的第 i 層上至多有 2i1 個結(jié)點(diǎn)。 (i≥ 1) 用歸納法證明 ： 歸納基 ： 歸納假設(shè)： 歸納證明： i = 1 層時，只有一個根結(jié)點(diǎn)， 2i1 = 20 = 1； 假設(shè)對所有的 j， 1≤ j ? i， 命題成立 。 二叉樹上每個結(jié)點(diǎn)至多有兩棵子樹， 則第 i 層的結(jié)點(diǎn)數(shù) = 2i2? 2 = 2i1 。 34 ?性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k1 個結(jié)點(diǎn) . (k≥ 1) 證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ ? ? ? ? ? ? +2k1 = 2k1 35 ? 性質(zhì) 3 ： 對任何一棵二叉樹，若它含有 n0 個葉子結(jié)點(diǎn)、n2 個度為 2 的結(jié)點(diǎn)，則必存在關(guān)系式： n0 = n2+1 證明： 設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2 又 二叉樹上分支總數(shù) b = n1 + 2n2 而 b = n 1 由此， n1 + 2n2 = n0 + n1 + n2 1 即 n0 = n2 + 1 36 兩類 特殊 的二叉樹： 滿二叉樹 ： 指的是深度為 k且含有 2k1個結(jié)點(diǎn)的二叉樹。特點(diǎn)： 每一層上的結(jié)點(diǎn)數(shù)都是最 大結(jié)點(diǎn)數(shù) . 完全二叉樹 ： 樹中所含的 n 個結(jié)點(diǎn)和滿二叉樹中 編號為 1 至 n 的結(jié)點(diǎn) 一一對應(yīng)。 特點(diǎn) : (1)葉子結(jié)點(diǎn)只可能在層次最底的兩層上出現(xiàn) .(2)對任一結(jié)點(diǎn)，若其右分支下子孫的最大層次為 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 證明： 設(shè) 完全二叉樹的深度為 k 即 k1 ≤ log2 n k 因?yàn)? k 只能是整