【正文】 C B E G D F A p (14) A B C D E F G i 訪問： C B E G D F A p=NULL (15) 五、建立二叉樹的存儲結(jié)構(gòu) 不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法 以字符串的形式 “ 根 左子樹 右子樹 ” 定義一棵二叉樹 例如 : 以空白字符“ ”表示 A B C D A(B( ,C( , )),D( , )) 空樹 只含一個根結(jié)點的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 Status CreateBiTree(BiTree amp。 } //根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點，遍歷右子樹 pop(s,p)。 } } //While return OK。 p ) //有值且非空時 push(s, plchild)； //null 值可能進(jìn)棧 pop (s,p)。 例如 : B C D E L A X W 中序： B、 L、 E、 A、 C、 W、 X、 D Status InOrderTraverse(BiTree t, Visit){ initstack(s)。 若有左 孩 子，返回第一步。 pre(T L)。 pre(T L)。 返回 返回 pre(T R)。// 遍歷右子樹 } } void pre(BiTree T) { if(T) { printf(%d\t,Tdata)。 A F E D C B G 第 1次經(jīng)過時訪問＝先序遍歷 第 2次經(jīng)過時訪問＝中序遍歷 第 3次經(jīng)過時訪問＝后序遍歷 2. 二叉樹遍歷的時間效率和空間效率 時間效率 :O(n) //每個結(jié)點只訪問一次 空間效率 :O(n) //棧占用的最大輔助空間 （精確值：樹深為 k的遞歸遍歷需要 k+1個輔助單元?。? A D B C D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C 先序遍歷 : A D B C L D R B L D R L D R A D C L D R 中序遍歷序列： B D A C 中序遍歷 : A D B C L R D L R D L R D A D C L R D 后序遍歷序列： D B C A 后序遍歷 : B A B C D E F G H K 復(fù)習(xí)回顧： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A lchild data rchild parent lchild data rchild void Preorder (BiTree T, void( *visit)(TElemTypeamp。 struct Node *lchild,*rchild； } tree。 LRD(rootrchild)。 printf(“%d”,rootdata)。 //訪問 D DLR(rootlchild)。 e)) { // 先序遍歷二叉樹 if (T) { visit(Tdata)。 遍歷用途 ——它是樹結(jié)構(gòu)插入、刪除、修改、查找和排序運(yùn)算的前提，是二叉樹一切運(yùn)算的基礎(chǔ)和核心。 struct TriTNode *lchild, *rchild。 A D E B C F ? ? ? ? ? ? ? root lchild data rchild 結(jié)點結(jié)構(gòu) : 1. 二叉鏈表 A B D C E F 討論：有 n個結(jié)點二叉樹的二叉鏈表有多少空鏈域？ 解釋 1: 2*n（ n1） = n+1 解釋 2: 2*n0+n1 = n0+n1+n2+1 = n+1 n+1個 typedef struct BiTNode { // 結(jié)點結(jié)構(gòu) TElemType data。 二叉樹的順序存儲表示 討論： 不是完全二叉樹怎么辦？ 答： 一律轉(zhuǎn)為完全二叉樹 ！ 方法很簡單 ， 將各層空缺處統(tǒng)統(tǒng)補(bǔ)上 “ 虛結(jié)點 ” ， 其內(nèi)容為空 。 A B C D E F G H I [1] [2] [3] [4] [5] [6] [7] [8] [9] A B C G E I D H F 問：順序存儲后能否復(fù)原成唯一對應(yīng)的二叉樹形狀？ 答：若是完全 /滿二叉樹則可以做到唯一復(fù)原。 度為 2的結(jié)點＝ 葉子總數(shù)－ 1=499個。 分析： k層的 489個葉子的父結(jié)點占上層的 245個結(jié)點（ ?489/2? ) 上層（ k=9)右邊的 0度結(jié)點數(shù)還有 291245=11個！ 另一法： 可先求 2度結(jié)點數(shù) ,再由此得到葉子總數(shù)。 答： 易求出總層數(shù)和末層葉子數(shù)。 ② ：滿二叉樹和 完全二叉樹 有什么區(qū)別 ？ 答： 滿二叉樹是每一層都是滿的二叉樹 ， 而完全二叉樹雖然前 n1層是滿的 ， 但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點 。 Ａ )２ k1 Ｂ ) log2k Ｃ ) ２ k－１ Ｄ )２ k 課堂練習(xí)： 1. 樹Ｔ中各結(jié)點的度的最大值稱為樹Ｔ的 。 這其實是順序二叉樹的含義。 性質(zhì) 2: 深度為 k的二叉樹至多有 2k1個結(jié)點（ k0）。 DestroyBiTree(amp。T, definition)。T)。 InOrderTraverse(T, Visit())。 RightSibling(T, e)。 Parent(T, e)。 邏輯結(jié)構(gòu)： 一對二（ 1： 2） 基本特征 : ① 每個結(jié)點最多可有兩棵子樹（不存在度大于 2的結(jié)點）； ② 左子樹和右子樹次序不能顛倒（有序樹）。 二叉樹 5. 樹的運(yùn)算 要明確： 1. 普通樹 （ 即多叉樹 ） 若不轉(zhuǎn)化為二叉樹 ， 則運(yùn)算很難實現(xiàn) 。 重大缺陷：復(fù)原困難 （ 不能唯一復(fù)原就沒有實用價值 ） 。 2. 若干術(shù)語（續(xù)） ——即樹的數(shù)據(jù)元素及其分支 ——結(jié)點掛接的子樹數(shù) （有幾個直接后繼就是幾度。T) // 將樹清空 刪除類： DestroyTree(amp。T) // 初始化置空樹 插入類： CreateTree(amp。其中，每個集合本身又是一棵樹，被稱作這個根的 子樹 （ SubTree）。第 6章 樹和二叉樹 第 6章 樹和二叉樹 樹的定義和基本術(shù)語 二叉樹 遍歷二叉樹和線索二叉樹 樹和森林 赫夫曼樹及其應(yīng)用 特點：非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼（ 1： n） 樹的定義和基本術(shù)語 1. 樹的定義 2. 若干術(shù)語 3. 邏輯結(jié)構(gòu) 4. 存儲結(jié)構(gòu) 5. 樹的運(yùn)算 1. 樹的定義 注 1： 過去許多書籍中都定義樹為 n≥1，曾經(jīng)有“空樹不是樹”的說法，但現(xiàn)在樹的定義已修改。在任何一棵非空樹中 ： （ 1） 有且僅有 一個結(jié)點稱為根 （ root）； （ 2） 當(dāng) n1時，其余的結(jié)點可分為 m(m0)個 互不相交的 有限集合 T1,T2， … ， Tm。 //至少有 15個 基本操作： 查 找 類 插 入 類 刪 除 類 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。p, i, c) // 將以 c為根的樹插入為結(jié)點 p的第 i棵子樹 ClearTree(amp。p, i) // 刪除結(jié)點 p的第 i棵子樹 樹的表示法有幾種： ? 圖形表示法 ? 嵌套集合表示法 ? 廣義表表示法 ? 凹入表示法 ? 左孩子－右兄弟表示法 這些表示法的示意圖參見教材 P120圖 廣義表表示法 ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 根作為由子樹森林組成的表的名字寫在表的左邊 左孩子－右兄弟表示法 A B C D E F G H I J K L M 數(shù)據(jù) 左孩子 右兄弟 ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) 2. 若干術(shù)語 ——即上層的那個結(jié)點 (直接前驅(qū) ) ——即下層結(jié)點的子樹的根 (直接后繼 ) ——同一雙親下的同層結(jié)點（孩子之間互稱兄弟） ——即雙親位于同一層的結(jié)點（但并非同一雙親） ——即從根到該結(jié)點所經(jīng)分支的所有結(jié)點 ——即該結(jié)點下層子樹中的任一結(jié)點 A B C G E I D H F J M L K 根 葉子 森林 有序樹 無序樹 ——即根結(jié)點 (沒有前驅(qū) ) ——即終端結(jié)點 (沒有后繼 ) ——指 m棵不相交的樹的集合 (例如刪除 A后的子樹個數(shù) ) 雙親 孩子 兄弟 堂兄弟 祖先 子孫 ——結(jié)點各子樹從左至右有序，不能互換（左為第一） ——結(jié)點各子樹可互換位置。 討論 3：樹的鏈?zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？ 可規(guī)定為：從上至下 、 從左至右將樹的結(jié)點依次存入內(nèi)存 。 解決思路：先研究最簡單、最有規(guī)律的樹狀結(jié)構(gòu)，然后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹。 二叉樹的定義 二叉樹的性質(zhì) 二叉樹的存儲結(jié)構(gòu) （二叉樹的運(yùn)算見 ） 二叉樹的定義 定義：是 n（ n≥0）個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成 。 Value(T, e)。 LeftSibling(T, e)。 PreOrderTraverse(T, Visit())。 InitBiTree(amp。 CreateBiTree(amp。T)。 二叉樹的性質(zhì) (3+2) 討論 1：第 i層的結(jié)點數(shù)至多是多少？ （利用二叉樹的特性可輕松求出） 性質(zhì) 1: 在二叉樹的第 i層上至多有 2i1個結(jié)點（ i0）。 A O B C G E K D J F I H N M L 深度為 4的滿二叉樹 深度為 4的 完全二叉樹 A B C G E I D H F J 為何要研究這兩種特殊形式？ 因為它們在順序存儲方式下可以復(fù)原！ 解釋：完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。最多呢？ Ａ )２ 9 Ｂ )２ 8 Ｃ )９ Ｄ )２ 9－ 1 k 的二叉樹的結(jié)點總數(shù)，最多為 個。不能隨意顛倒 。 489 488 10 由于最后一層葉子數(shù)為 489個，是 奇數(shù) ，說明有 1個結(jié)點只有非空左子樹；而完全二叉樹中不可能出現(xiàn)只有非空右子樹的結(jié)點 (0個 )。 請注意葉子結(jié)點總數(shù) ≠ 末層葉子數(shù) ！ 還應(yīng)當(dāng)加上第 k1層 （ 靠右邊 ） 的 0度結(jié)點個數(shù) 。 第 i層上的滿結(jié)點數(shù)為 2i1 所以， 全部葉子數(shù)＝ 489(末層 )＋ 11(