【正文】 映 第 14 頁 樹的表示 (縮進(jìn)形式 ) A B E K L C D F G H I J M 下一頁 上一頁 停止放映 第 15 頁 樹的表示 (廣義表形式 ) ( A ( B ( E (K,L),F),C(G),D( H (M),I,J ))) 第一層 第二層 第三層 第四層 下一頁 上一頁 停止放映 第 16 頁 基本術(shù)語 結(jié)點 、 結(jié)點度 、 根 、 支 、 葉結(jié)點 子結(jié)點 、 父結(jié)點 、 兄弟結(jié)點 樹的度 、 路徑 、 長度 、 高度 、 深度 森林 、 有序 、 無序 下一頁 上一頁 停止放映 第 17 頁 結(jié)點（ Node） 結(jié)點 包括一個數(shù)據(jù)元素及若干個指向其它子樹的分支；例如 ， A， B， C， D等 。下一頁 第 4單元 非線性數(shù)據(jù)結(jié)構(gòu) 樹、二叉樹 主講：劉志強 西安交通大學(xué) 計算機教學(xué)實驗中心 計算機軟件基礎(chǔ) Fundamentals of Computer software 下一頁 上一頁 停止放映 第 2 頁 思考問題 數(shù)據(jù)間不是一一對應(yīng)的數(shù)據(jù)結(jié)構(gòu)如何描述？在計算機中存放？例如 ? 父子關(guān)系 ? 、 ? 隸屬關(guān)系 ?等。 根結(jié)點 無前趨結(jié)點 （ 或無父結(jié)點 ） 的結(jié)點；例如 ， A結(jié)點 。 下一頁 上一頁 停止放映 第 18 頁 基本術(shù)語（二） 子結(jié)點 某結(jié)點子樹的根為該結(jié)點的子結(jié)點；例如 ， 結(jié)點 A的子結(jié)點為 B， C， D。 對樹中每個結(jié)點而言 ， 其子樹的集合即為森林 。 CREATE（ x， T1， T2， … ,Tk) 生成一個結(jié)點 x,下帶子樹 T1,T2,… ,Tk。 下一頁 上一頁 停止放映 第 26 頁 樹的存儲結(jié)構(gòu)（三） 二叉鏈表實現(xiàn)方式 （ 孩子兄弟表示法 ） 以二叉鏈表作為樹的存儲結(jié)構(gòu) 。 – D中元素 ,或有兩個互不相交后繼 ,或無后繼 。 由性質(zhì)一可見 ， 深度為 k的二叉樹的最大結(jié)點數(shù)為： k i=1 i=1 k ? （ 第 i層上的最大結(jié)點數(shù) ） = ? 2i1 = 2k1 下一頁 上一頁 停止放映 第 36 頁 驗證二叉樹的性質(zhì) 1 2 3 8 6 5 7 4 10 9 11 12 13 14 15 該二叉樹的第 3層有 231 個結(jié)點。 } SBNode。 下一頁 上一頁 停止放映 第 47 頁 滿二叉樹存儲舉例 1 4 3 2 5 7 6 1 2 3 4 5 6 7 1 2 3 4 5 6 7 第 i個結(jié)點就存放在第 i個位置上； 第 i個結(jié)點（ i1)的父結(jié)點就存放在第 i/2個位置 。 – 若 2* i +1? n,則結(jié)點 i 的右子結(jié)點的編號為 2*i+1,否則 ,結(jié)點 i為葉結(jié)點 . ? 同理 ,完全二叉樹也可以采用一維樹組作為存儲結(jié)構(gòu) ,且方法完全同滿二叉樹 ,只不過 n ? 2k 1 罷了 . 下一頁 上一頁 停止放映 第 50 頁 平衡二叉樹 二叉樹上任一結(jié)點的左子樹深度減去右子樹深度的差值 ， 稱為該結(jié)點的平衡因子 。 ? 即： 根 左子 右子 a b c 下一頁 上一頁 停止放映 第 57 頁 二叉樹的遍歷舉例 o o o o o o o o o A B C D E F G H I 前序遍歷序列： ABDEGCFHI 中序遍歷序列： DBGEACHFI 后序遍歷序列： DGEBHIFCA 下一頁 上一頁 停止放映 第 58 頁 二叉樹遍歷算法 二叉樹 遍 歷方法分為： – 遞歸算法 – 非遞歸算法 遞歸算法和非遞歸算法中又分： – 前序法 – 中序法 – 后序法 下一頁 上一頁 停止放映 第 59 頁 二叉樹遍歷算法（遞歸算法） 二叉鏈表的 C語言描述： struct tnode { char data； struct tnode *lchild， *rchild ； } ； typedef struct tnode TNODE。 – step4 當(dāng)前元素進(jìn)棧 , p取 plc。 } if ( top !=1) { p=stack[top]。 d c b a （ 1） （ 2） c d b a （ 3） b*（ cd） a （ 5） a+b*（ cd） （ 4） a+b*（ cd） f e （ 6） e/f a+b*（ cd） （ 7） a+b*（ cd） e/f 下一頁 上一頁 停止放映 第 67 頁 樹、森林與二叉樹的轉(zhuǎn)換 ? 由于二叉樹的存儲結(jié)構(gòu)比較簡單 ，處理起來也比較方便 ， 所以有時需要把復(fù)雜的樹 ， 轉(zhuǎn)換為簡單的二叉樹后再作處理 。 舉例： o o o o o o o o o o o o o o 加線 抹線 o o o o o o o 旋轉(zhuǎn) o o o o o o o 下一頁 上一頁 停止放映 第 69 頁 森林轉(zhuǎn)換成二叉樹 操作算法： – 將森林中每棵樹的樹根連接起來； – 將每棵樹轉(zhuǎn)換成對應(yīng)的二叉樹； – 以森林中第一棵樹的根為軸順時針旋轉(zhuǎn)一個角度 。 p=prc。 int top=1。 if (rootlc!=NULL) proorder_t(rootlc)。 （ a） 平衡二叉樹 （ b） 非平衡二叉樹 O O O O O O O O O O O O O O 下一頁 上一頁 停止放映 第 51 頁 二叉排序樹定義（一） 二叉排序樹 或者是空二叉樹； 或者是： 左子樹上所有結(jié)點的值均小于根結(jié)點的值； 右子樹上所有結(jié)點的值均大于等于根結(jié)點的值； 左 、 右子樹本身又是一棵二叉排序樹 。右子存放在第 2*i+1位置。