【正文】 p) {// 若二叉樹中存在和 x相同的元素，則 p指向該結(jié)點并返回 true if (T) { if (Tdata==x) { p=T。 p=T。 p=prchild。 p=plchild。 p=prchild。 T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R)。 pre(T L)。 // 訪問結(jié)點 PreOrder(Tlchild, Visit)。 “遍歷 ”是任何類型均有的操作， 對線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因為每個結(jié)點均只有一個后繼 )， 故不需要另加討論。 // 左右孩子指針 } BiTNode, *BiTree。 特點 : (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é)點的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結(jié)點： (1) 若 i=1，則該結(jié)點是二叉樹的根，無雙親 , 否則，編號為 ?i/2? 的結(jié)點為其 雙親 結(jié)點 。 DestroyBiTree(amp。 Assign(T, amp。 BiTreeEmpty(T)。 N N N L R N 思考：二叉樹與樹的區(qū)別？ 二叉樹與無序樹的區(qū)別 二叉樹與有序樹的區(qū)別 二叉樹就是度為 2的有序樹嗎？ 所以，二叉樹不是前面定義的樹的特殊形式， 而是另外一種數(shù)據(jù)結(jié)構(gòu)。 任何一棵非空樹是一個二元組 Tree = （ root， F） 其中： root 被稱為根結(jié)點， F 被稱為子樹森林。 D H I J M （終端結(jié)點） （非終端結(jié)點） (從根到結(jié)點的 )路徑 ： 結(jié)點的層次 : 樹 的 深度： 由從 根 到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成。T) // 將樹清空 刪除類： DestroyTree(amp。 樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)。 數(shù)據(jù)關(guān)系 R： ADT Tree { 若 D為空集，則稱為空樹； 否則 : } ADT Tree 基本操作 P： 基本操作： 查 找 類 插 入 類 刪 除 類 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() ) // 遍歷 樹中結(jié)點的最大層次 InitTree(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 練習(xí) 基 本 術(shù) 語 結(jié) 點 : 結(jié)點的度 : 樹 的 度 : 葉子結(jié)點 : 分支結(jié)點 : 一個數(shù)據(jù)元素 +若干指向子樹的分支。 孩子 結(jié)點：某結(jié)點子樹的根結(jié)點稱為該結(jié)點的孩子結(jié)點。 子樹之間存在確定的次序關(guān)系 （ 不能互換 ） 。 Parent(T, e)。 InOrderTraverse(T, Visit()) // 中序遍歷 。T, definition)。 二叉樹 的重要特性 ? 性質(zhì) 1 ： 在二叉樹的第 i 層上至多有 2i1 個結(jié)點。 // 0號單元存儲根結(jié)點 SqBiTree bt。 // 左右孩子指針、 雙親指針 } TriTNode, *TriTree。 D L R LDR、 LRD、 DLR RDL、 RLD、 DRL 二、先左后右的遍歷算法 先 （根） 序的遍歷算法 中 （根） 序的遍歷算法 后 （根） 序的遍歷算法 根 左 子 樹 右 子 樹 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點； （ 2）先序遍歷左子樹； （ 3）先序遍歷右子樹。 pre(tlchild)。 T D printf(D)。 p=T。 p=plchild。 p=prchild。 } // 根指針進(jìn)棧，遍歷左子樹 else { //根指針退棧，訪問根結(jié)點， Pop(S,p)。 p=plchild。 }//else }//if else return FALSE。 CountLeaf( Trchild, count)。 } //else } // CountLeaf 算法二 123456789 求二叉樹的深度 算法基本思想 : 從二叉樹深度的定義可知， 二叉樹的深度應(yīng)為其左、右子樹深度的最大值加 1。 } 算法 建立二叉樹的存儲結(jié)構(gòu) 不同的定義方法對應(yīng)不同的建立存儲結(jié)構(gòu)的算法 ? 按先序遍歷序列建二叉樹 ? 按給定的表達(dá)式建二叉樹 ? 由先序和中序序列建二叉樹 作業(yè) 以先序遍歷序列的形式 根 左子樹 右子樹 定義一棵二叉樹 例如 : A B C D 以空白字符“ ”表示 A(B( ,C( , )),D( , )) 空樹 只含一個根結(jié)點的二叉樹 A 以字符串“ A ” 表示 以下列字符串表示 A B C D 算法 Status CreateBiTree(BiTree amp。 // 生成根結(jié)點 CreateBiTree(Tlchild)。 遞歸建右子樹 。 } PND S void CrtExptree(BiTree amp。 ch==??)) { if (!IN(ch, OP)) CrtNode( t, ch )。 // 建子樹并入棧 PND Pop(S, c) } break。 T,char ch) { if (!(T= new BiTNode)) exit(OVERFLOW)。 Trchild = rc。 H G E D F C B A 線索二叉樹 ? 何謂線索二叉樹？ ? 線索鏈表的遍歷算法 ? 如何建立線索鏈表？ 一、何謂線索二叉樹？ 遍歷二叉樹的結(jié)果是， 求得結(jié)點的一個線性序列。 // 左右指針 PointerTag LTag, RTag。 ※ 中序遍歷的第一個結(jié)點 ？ ※ 在中序線索化鏈表中結(jié)點 *p的后繼 ？ 根結(jié)點左子樹上處于 “最左下” 的結(jié)點。 //當(dāng) *q不是 return (q)。 //第 一個結(jié)點 while (pRTag==Thread amp。 三、如何建立 (中序 )線索鏈表？ void InThreading(BiThrTree p) { if (p) { // 對以 p為根的非空二叉樹進(jìn)行中序線索化 InThreading(plchild)。 假設(shè)新結(jié)點 *q是插入到指定結(jié)點 *p和 *p的右子樹之間的結(jié)點，插入后， *q作為 *p的右子樹的根結(jié)點。 qrtag=prtag。 缺點： 就插入和刪除結(jié)點而言，除需修 改指針外，還須相應(yīng)的修改線索。 // 根結(jié)點的位置和結(jié)點個數(shù) } PTree。 Ⅲ. 以上兩種方法在實際應(yīng)用中都會遇到一些困難。 ChildPtr firstchild。 結(jié)點結(jié)構(gòu) : firstchild data nextsibling 三、孩子 兄弟表示法 (二叉鏈表存儲） A B C D E F G root A B C E D F G 如何找結(jié)點 *x的第 i個孩子？ x A B C D E F H G I 分別用雙親表示法、孩子鏈表、孩子 —兄弟表示法表示圖示樹?；蛘?，可以先將森林中的每一棵樹變?yōu)槎鏄洌缓髮⒏鞫鏄涞母Y(jié)點視為兄弟連在一起。 由 ROOT( T1 ) 對應(yīng)得到二叉樹的根 root。 應(yīng)當(dāng)注意的是， 和樹對應(yīng)的二叉樹，其左、右子樹的概念已改變?yōu)椋? 左是孩子，右是兄弟。 先序遍歷 森林中第一棵樹的子樹森林 。 一、求樹的深度 二、輸出樹中所有從根到葉子的路徑 三、建樹的存儲結(jié)構(gòu) 樹的遍歷的應(yīng)用 data firstchild 0 A 1 B 2 C 3 D 4 E 5 F 6 G 6