【正文】 1 數據結構 6 樹和二叉樹 2 ? 樹的類型定義 ? 二叉樹的類型定義 ? 二叉樹的存儲結構 ? 遍歷二叉樹和線索二叉樹 ? 樹和森林 ? 赫夫曼樹 主要內容 3 –社會的組織結構 –家族的族譜 –計算機中的目錄組織 描述層次結構，是一種一對多的邏輯關系 樹型結構實例 4 ? 樹的定義 (Tree) – 樹 是由 n(n0)個結點組成的有限集合 – 如果 n=0，稱為空樹 – 如果 n0，則 ? 有一個特定的稱之為 根 (root)的結點，它只有直接后繼，但 沒有直接前驅 ? 除根以外的其它結點劃分為 m(m=0)個 互不相交 的有限集合 T0,T1,…,T m1，每個集合又是一棵樹，并且稱之為根的 子樹 遞歸定義 5 A B C D E F G H I J K L M 根 子樹 樹 (邏輯上 )的特點 ? 每棵子樹的根結點有且僅有一個直接前驅，但可以有 0個或多個直接后繼 6 A B C D E F G H I J K L M 樹的基本概念 ? 結點 分支結點 葉子結點 根結點 內部結點 結點 度不為 0的結點 度為 0的結點 7 樹的基本概念 ? 結點的度和樹的度 ?結點的度即結點擁有的子樹個數 。 ?樹的度是樹內各結點的度的最大值 。 A B C D E F G H I J K L M 3 2 1 3 2 0 0 1 0 0 0 0 0 8 樹的基本概念 ? 結點的層次和樹的深度 (高度 ) ?結點的層次從根開始定義 。 根位于第 1層 ， 根的孩子位于第2層 ， 余則類推 。 ?樹的深度即樹中結點的最大層次 。 第 1層 第 2層 第 3層 第 4層 樹的高度為4 A B C D E F G H I J K L M 9 樹的基本概念 ? 孩子、雙親、兄弟 ?結點的子樹的根稱為結點的 孩子 。 ?該結點稱為其孩子的 雙親 。 ?同一雙親的孩子間互稱 兄弟 。 A B C D E F G H I J K L M 孩子 雙親 10 樹的基本概念 ? 祖先、子孫 結點的 祖先 是從根到該結點所經分支上的所有結點； 以某結點為根的子樹中的任一結點都稱該結點的 子孫 。 A B C D E F G H I J K L M 11 樹的基本概念 ? 森林： m(m=0)棵互不相交的樹的集合 B E F K L D H M I J C G A C G B D E F K L H M I J 12 –樹的有序性 ：若樹中結點的子樹的相對位置不能隨意改變，則稱該樹為 有序樹 ，否則稱該樹為 無序樹 。 樹的基本概念 = 有序樹 無序樹A B D C A C B D 13 有序樹中最左邊的子樹的根稱其第一個孩子 ， 最右邊的子樹的根稱其最后一個孩子 。 老大 老二 老三 ? 有序樹的第一個孩子和最后一個孩子 樹的基本概念 A B D C 14 樹的常用表示法 A E F B I J G H C D F G I J A B C E D H 凹入表示 嵌套集合 廣義表 A(B(E,F),C,D(G(J),H,I)) A B E F C D G J H I 15 ? 為何要重點研究每結點最多只有兩個“叉” 的樹？ – 樹太一般，子樹的個數無限制，表示困難 – 二叉樹的結構最簡單，規(guī)律性最強 – 可以證明， 所有樹都能轉為唯一對應的二叉樹 ，不失一般性。 16 二叉樹的基本定義 ? 二叉樹的定義 – 是 n≥0個結點的有窮集合 – 該集合或者為空、或者由一個根結點和兩個分別稱為左子樹和右子樹的互不相交的二叉樹組成。 – 當集合為空時，稱該二叉樹為空二叉樹。 – 邏輯結構：一對二 (1:2) – 基本特征 : ?樹的一種 ?每個結點最多有 2棵子樹 (即度 =2) B C A D E 17 二叉樹與樹的區(qū)別 ? 樹至少 應有 一個 結點 ， 而 二叉樹 可以為 空 ； ? 樹的孩子結點沒有限制 ， 而二叉樹中的每個結點最多有 2個孩子結點； ? 樹的子樹沒有順序 ， 但如果二叉樹的根結點只有一棵子樹 ，必須明確區(qū)分它是左子樹還是右子樹 ， 因為兩者將構成不同形態(tài)的二叉樹 。 18 二叉樹的五種基本形態(tài) A Φ B A D E B A D E B C A D E 19 問：具有 3個結點的二叉樹可能有幾種不同形態(tài)？ 有 5種 Φ 二叉樹的基本形態(tài) 20 2的 樹 是二叉樹。 2的 有序樹 是二叉樹。 樹 可以有以下五種形態(tài)： 1種 21 二叉樹的性質 ? 性質 1： – 在二叉樹的第 i層最多有 2i1個結點 (i=1) – 證明： ? 當 i=1時，顯然成立 ? 假設當 i=k時，也成立，即第 k層最多 2k1個結點 ? 當 i=k+1時，由于二叉樹的每個結點最多有 2個孩子，所以第 k+1層最多有 2*2k1=2(k+1)1個結點 ? 故對于任意 i(i=1)，二叉樹的第 i層最多有 2i1個結點 提問：第 i層上至少有 個結點？ 1 22 二叉樹的性質 ? 性質 2： – 深度為 k的二叉樹最多有 2k1個結點 (k=1) – 證明： ? 由性質 1可知：第 i層最多有 2i1個結點 ? 所以總的結點數最多為 k=4 1 2 3 4 23 二叉樹的性質 ? 性質 3： – 對任何一棵二叉樹 T，若葉子結點數 (即度為 0的結點數 )為 n0，度為 2的結點數為 n2，則 n0=n2+1 – 證明： ? 總結點數 n=n0+n1+n2 ? 設分支數為 B，則 n=B+1 ? 又 B=n1+2n2 48 951 0 1 161 272 31結點無外乎度為 0、 2三種情況 ? ”五個手指四個叉” ? 除了樹根，其余每個結點”上方”都有一個分支 ? 度為 2的結點“下方”有 2個分支 ? 度為 1的結點“下方”有 1個分支 ? 度為 0的結點“下方”有 0個分支 ? 解方程組： 得： n0=n2+1 ? ? ??????? ???0 1 21212n n n nnBB n n24 樹的葉子數與其它結點數的關系 ? 設 度為 m的樹中度為 0,1,2,…,m 的結點數分別為n0,n1,n2,…,n m，結點總數為 n，分支數為 B，則下面二式成立 ? n=n0+n1+n2+…+n m (1) ? n=B+1=n1+2n2+…+mn m+1 (2) ? 由 (1)和 (2)得葉子結點數 n0=1+n2+2n3+…+(m 1)nm 25 48 951 0 1 161 2 1 371 4 1 52 31? 滿二叉樹 (Full Binary Tree) – 深度為 k，結點數為 2k1 – 即結點數達到最大值 48 951 0 1 161 2 1 371 4 1 52 31特殊形態(tài)的二叉樹 ? 完全二叉樹 (Complete Binary Tree) – 樹中每個結點的編號（從上到下，從左到右）都與一個同深度的滿二叉樹的結點一一對應 – 葉子結點只可能在層次最大的兩層上出現 完全二叉樹和和滿二叉樹相比，就是最底層最右邊連續(xù)缺少一些結點 26 特殊形態(tài)的二叉樹 2h1 結論： 深度為 h且具有 2h1個結點的二叉樹為滿二叉樹。 思考：深度為 h的完全二叉樹至少有多少個結點？ 27 二叉樹的性質 ? 性質 4： – 具有 n個結點的非空完全二叉樹的深度為 – 證明： ? 設深度為 k，則： 2k11 n =2k1 ? 由此推出： 2k1 = n 2k ? 兩邊求對數： k1 = log2n k ? 所以： 241 231 48 951 0 1 161 2 1 371 4 1 52 3128 二叉樹的性質 ? 性質 5： – 若將一棵有 n個結點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結點編號： – (1)若 i=1，則結點 i是樹根，無雙親 若 i1，則其雙親是結點 ?i/2? – (2)若 2in，則結點 i無左孩子 (即 i為葉結點 )，否則其左孩子為 2i – (3)若 2i+1n，則結點 i無右孩子，否則其右孩子為 2i+1 – 由 (2)(3)可以推導出 (1) 48 951 06 72 31理解： 結點 i如果有左孩子的話，其編號應該為 2i 如果 2in，則左孩子不存在 29 二叉樹的性質 ? 性質 6： – 具有 n個結點的非空二叉樹共有 n1個分支。 – 證明： ?除了根結點以外，每個結點有且僅有一個雙親結點，即每個結點與其雙親結點之間僅有一個分支存在，因此，具有 n個結點的非空二叉樹的分支總數為 n1。 30 (n0)個結點的樹的高度最低是多少？最高是多少？ (n0)個結點的二叉樹的高度最低是多少？最高是多少？ 推論 ? n個結點的樹： 高最多為 n， 最低為 2。 ? n個結點的二叉樹： – 高最多為 n(單支樹 )，最低為 ?log2n?+1(完全二叉樹 )。 自測題 31 自測題 ( ) 2 2 2 2 6層 (設根是第 1層 )有 8個葉結點，則該完全二叉樹的結點個數最多是 ( ) A. 39 B. 52 C. 111 D. 119 32 完全二叉樹性質的推論 ? n個結點的完全二叉樹中： – 度為 1的結點數為 (n+1)%2 – 度為 0的結點數為 ?(n+1)/2? – 度為 2的結點數為 ?(n+1)/2?1 – 編號最大的分支結點是 ?n/2? – 編號最小的葉子結點是 ?n/2?+1 ? 具有 n0個葉子結點的完全二叉樹中共有 2n0個 結點或 2n01個結點。 33 一棵完全二叉樹有 1000個結點，則它必 有 個葉子結點； 有 個度為 2的結點； 有 個結點只有非空左子樹； 有 個結點只有非空右子樹。 ?(1000+1)/2? =500 葉子總數 1=499 1 0 因為最后一個結點坐標是偶數，所以必為左子樹。有 1個結點只有非空左子樹，有 0個結點只有非空右子樹。 自測題 34 自測題 124個葉結點的完全二叉樹，最多有 ( )個結點。 626個結點，葉子結點的個數應為 ( )。 35 自測題 1025個結點的二叉樹的高 h為 ( ) 。 1025之間 1024之間 3的樹有 2個度為 1的結點， 3個度為 2的結點，4個度為 3的結點，則該樹有 ______個葉子結點。 12 36 二叉樹 ? 本節(jié)小結 – 二叉樹的概念和類型定義 ?注意和樹的類型定義的對比 – 二叉樹的性質 ?要求自己能推導、應用、推廣 37 ? 二叉樹的順序存儲結構 – 用一維數組來表示 define MAX_TREE_SIZE 100 typedef datatype SqBiTree[