【導讀】樣簡單，例如元素有多個前驅(qū)、多個后繼。樹，稱為T的子樹。除根外，每個元素有且僅有一個前驅(qū)，有零個或多個后繼。分支結(jié)點：度不為0的結(jié)點，又稱為非末端結(jié)點。結(jié)點的層次：根結(jié)點定義為第1層，根的兒子定義為第2層，...，樹的深度（高度）：各結(jié)點層次的最大值。n1到nk有一條路徑。根沒有雙親，葉子沒有孩子；vi是vj的雙親，則L=L-1;有序樹和無序樹的區(qū)別；集合表示的一種直觀表示，用圖表示集合。將一棵樹描述為一個廣義表，樹根為單元素，子樹就對應子表。性質(zhì)3深度為h的k叉樹最多有個結(jié)點。以上性質(zhì)的證明請同學們自己完成！可以用順序存儲，也可以用鏈式存儲。

　　

【正文】 1， 則 p lchild就是其前驅(qū)結(jié)點； 若 p ltag=0， 則 p lchild指的是左兒子，前驅(qū)是誰？ 根據(jù)中序遍歷的規(guī)則 ，前驅(qū)在左子樹上，而且是中序 遍歷左子樹的最后一個結(jié)點，即左子樹的最右下結(jié)點。 p if(p ltag==1) return(p lson) else { q=p lson。 while(q rson!=NULL) q=q rson } rerturn(q) 。 167。 線索二叉樹 二、線索的使用 后繼： 若 p rtag=1， 則 p rson就是其后繼結(jié)點； 若 p rtag=0， 則 p rson指的是右兒子，后繼是誰？ 根據(jù)中序遍歷的規(guī)則， 后繼在右子樹上，而且是中序 遍歷右子樹的第一個結(jié)點，即右子樹的最左下結(jié)點。 p if(p rtag==1) return(p rson) else { q=p rson。 while q lson!=NULL) q=qlson } rerturn(q) 。 167。 線索二叉樹 二、線索的使用 167。 線索二叉樹 前序線索二叉樹，找前趨、后繼的方法 前驅(qū)： 假設 p指向當前結(jié)點，找 p所指結(jié)點的前驅(qū)、后繼 若 p ltag=1， 則 p lson就是其前驅(qū)結(jié)點； 若 p ltag=0， 則 p lson指的是左兒子，前驅(qū)是誰？ 根據(jù)前序遍歷的規(guī)則， 前趨不在左、右子樹上，而 是與父親有關。分幾種情況： （ 1） P是根，則無前驅(qū)； P 二、線索的使用 167。 線索二叉樹 （ 2） P是父親的左兒子或是右兒子但無左兄弟， 前驅(qū)是父親； p p 二、線索的使用 167。 線索二叉樹 （ 3） P是父親的右兒子，且有左兄弟，其前驅(qū)是前序 遍歷父親左子樹上的最后一個結(jié)點（是最右下結(jié) 點嗎？） p p 二、線索的使用 167。 線索二叉樹 后繼： 若 p rtag=1， 則 p rson就是其后繼結(jié)點； 若 p rtag=0， 則 p rson指的是右兒子，后繼是誰？ 根據(jù)前序遍歷的規(guī)則， 后繼在左、右子樹上，如果 p 有左子樹 ， 則后繼是左子樹的根，否則是右子樹的根； p p 二、線索的使用 167。 線索二叉樹 后序線索二叉樹，找前趨、后繼的方法 前驅(qū)： 假設 p指向當前結(jié)點，找 p所指結(jié)點的前驅(qū)、后繼 若 p ltag=1， 則 p lson就是其前驅(qū)結(jié)點； 若 p ltag=0， 則 p lson指的是左兒子，前驅(qū)是誰？ 根據(jù)后序遍歷的規(guī)則， 若 p的右子樹不空，則前驅(qū) 是右子樹的根，否則是左子樹的根； p p 二、線索的使用 167。 線索二叉樹 后繼： 若 p rtag=1， 則 p rson就是其后繼結(jié)點； 若 p rtag=0， 則 p rson指的是右兒子，后繼是誰？ 根據(jù)后序遍歷的規(guī)則， 后繼不在左、右子樹上，而與 雙親有關。 分 幾種情況： p （ 1） P是根，則無后繼； （ 2） P是父親的右兒子或是左兒子但無右兄弟， 后繼是父親； p 二、線索的使用 （ 3） P是父親的左兒子，且有右兄弟，其后繼驅(qū)是 后序遍歷右子樹上的第一個結(jié)點。（是最左 下結(jié)點嗎？） p 167。 線索二叉樹 二、線索的使用 167。 線索二叉樹 三、二叉樹的線索化 方法： 在進行某種方式遍歷的同時，把其中的空指針改為 記線索（左指針空時，指向前驅(qū)；右指針空時指向 后繼）。 在此，僅介紹中序線索二叉樹的算法實現(xiàn)，設為 P為當前結(jié)點， pre為 p的前驅(qū)結(jié)點，算法描述如下： 167。 線索二叉樹 三、二叉樹的線索化 中序線索化： void inth (Hbitree *p) //將 P所指二叉樹中序線索化，調(diào)用該函數(shù)之前， pre為 Null，而樹中所有結(jié)點的 ltag和 rtag都為 0。 { if (p!=NULL) { inth (plchild)。 左子樹線索化 167。 線索二叉樹 三、二叉樹的線索化 if (plchild==NULL) pltag=1。 if (prchild==NULL) prtag=1。 if (pre!=NULL) { if(prertag==1) prerchild=p。 if (pltag=1) plchild=pre。 } pre=p。 nth (prchild)。 //右子樹線索化 } } p 是正在訪問的結(jié)點 pre 剛剛訪問過的結(jié)點 167。 線索二叉樹 四、線索二叉樹的插入、刪除 在線索二叉樹中插入、刪除，除了象一般二叉樹那樣調(diào)整結(jié)點外，還必須要維護線索，更麻煩！ 維護線索有時比建立線索還難，所以，一般是 采用先插入或刪除結(jié)點，然后重建線索！ 167。 樹、森林和二叉樹 森林： m(m=0)棵互不相交的樹的集合。 F={ T1,T2, ... , Tm } 一、樹、森林和二叉樹的轉(zhuǎn)化 樹 二叉樹 樹 二叉樹 樹的左兒子、右兄弟存儲，即：凡是兄弟就連起來 （右指針），然后只保留雙親到第一個孩子的連線 而去掉到其他孩子的連線。 二叉樹 樹 如果一個結(jié)點是雙親的左兒子，則將該結(jié)點的右兒子， 右兒子的右兒子， ...，均與其雙親相連，然后去掉雙親 到右兒子的連線。 167。 樹、森林和二叉樹 一、樹、森林和二叉樹的轉(zhuǎn)化 舉例： a b c d e f g h i j a b c d e f g h i j 167。 樹、森林和二叉樹 一、樹、森林和二叉樹的轉(zhuǎn)化 a b c d e f g h i j a b c d e f g h i j 167。 樹、森林和二叉樹 一、樹、森林和二叉樹的轉(zhuǎn)化 森林 二叉樹 森林 二叉樹 F={T1,T2, ... ,Tm}， 若 m=0， 則二叉樹為空； 否則，二叉樹的根為 T1的根， T1的子樹森林轉(zhuǎn)化為二叉樹 的左子樹，森林 {T2,T3, ... ,Tm}轉(zhuǎn)化為二叉樹的右 子樹。（遞歸） 或，每棵樹分別轉(zhuǎn)換為二叉 樹，然后 Ti的二叉樹作為 Ti1的二叉樹的右子樹 167。 樹、森林和二叉樹 一、樹、森林和二叉樹的轉(zhuǎn)化 二叉樹 森林 同二叉樹還原為樹一樣！ a b c e f g h i d 舉例： a b c d e f g h i a b c d e f g h i 167。 樹、森林和二叉樹 二、樹、森林的遍歷 樹的遍歷 先根方式：首先訪問根結(jié)點，然后依次 先根方式 遍歷根的各 個子樹； 后根方式：首先依次 后根方式 遍歷根的各個子樹，然后訪問 根結(jié)點 a b c d e f 先根序列： abcefd 后根序列： befcda 分別對應于二叉樹的 哪種遍歷序列？ 167。 樹、森林和二叉樹 先序方式：訪問第一棵樹根結(jié)點； 先序遍歷 第一棵樹的根的子樹森林； 先序遍歷 除第一棵樹以外的子樹森林； 森林的遍歷 中序方式： 中序遍歷 第一棵樹的根結(jié)點的子樹森林； 訪問第一棵樹的根； 中序遍歷 除第一棵樹以外的子樹森林； a b c e f g h i d 先序序列： 中序序列： abcdefghi bcdafehig 二、樹、森林的遍歷 167。 二叉分類樹（二叉排序樹、二叉查找樹） 特殊二叉樹之一： 一、二叉分類樹的定義及特點 二叉分類樹 (Binary Sort Tree): 非遞歸定義：二叉樹中，任何結(jié)點均滿足條件： “大于或等于其 左子樹上的結(jié)點 ，小于 其右 子樹上的結(jié)點 （若存在的話）”。 遞歸定義：若二叉樹是空，則是二叉分類樹；否則： 若左子樹不空，它的結(jié)點均小于等于根結(jié)點； 若右子樹不空，它的結(jié)點均大于根結(jié)點； 左、右子樹又都是二叉分類樹！ 特點：中序遍歷二叉分類樹，得到的序列是一個有序序列！ 167。 二叉分類樹（二叉排序樹、二叉查找樹） 特殊二叉樹之一： 舉例： 10 5 30 2 7 6 9 20 28 中序遍歷序列： 2 5 6 7 9 10 20 28 30 上次課內(nèi)容回顧 線索二叉樹： 為什么提出線索二叉樹？ 線索有哪些？（遍歷） 如何記錄線索？（全線索、部分線索） 如何使用線索？（找前驅(qū)、后繼） 建立線索、維護線索 樹、森林和二叉樹的關系： 轉(zhuǎn)換 樹、森林的遍歷 特殊二叉樹之一：二叉分類樹： 定義、特點 建立 非遞歸定義： 二叉樹中，任何結(jié)點均滿足條件：“大于或等于其左子樹上的結(jié)點 ，小于 其右 子樹上的結(jié)點 （若存在的話）”。 167。 二叉分類樹（二叉排序樹、二叉查找樹） 特殊二叉樹之一： 二、二叉分類樹的建立（采用二叉鏈式存儲結(jié)構(gòu)） 二叉分類樹的建立，只要將數(shù)據(jù)元素鏈到合適的位置即可， 可以看作在二叉樹中插入一個元素，但位置靈活（滿足性質(zhì)） 開始，二叉樹空，插入到空二叉樹中，即該數(shù)據(jù)元素就是根； 然后，讀入數(shù)據(jù)元素，與根比較，若比根大則 在右子樹中 插入 ，否則 在左子樹中插入 。 前面我們介紹了一般二叉樹的建立，是比較難的，原因是 根據(jù)結(jié)構(gòu)建立二叉樹，如果不考慮結(jié)構(gòu)，僅僅是考慮滿足某種 性質(zhì)，就簡單多了。如二叉分類樹的建立。 基本思想 167。 二叉分類樹（二叉排序樹、二叉查找樹） 特殊二叉樹之一： 二、二叉分類樹的建立（采用二叉鏈式存儲結(jié)構(gòu)） void Insert (Btreenode *BST ,elemtype X ) { if(BST= =NULL) { Btreenode *p= new Btreenode。 p data = X。 pleft=pright=NULL。 BST=p。 } else if (BSTdata = X ) Insert ( BST left,X)。 //在左子樹中插入 else Insert (BSTright,X)。 //在右子樹中插入 } 算法 (插入一個元素的算法 ) 167。 二叉分類樹（二叉排序樹、二叉查找樹） 特殊二叉樹之一： 二、二叉分類樹的建立（采用二叉鏈式存儲結(jié)構(gòu)） Btreenode *Creat (int n) //建立含有 n個結(jié)點的二叉排序樹 { Btreenode *BST= NULL。 for ( int i=1。 i=n。 i++) { cinx。 //輸入關鍵字序列 Insert ( BST,x)。 } return BST 。} 只要反復調(diào)用二叉排序樹的插入算法即可，算法描述為： 167。 二叉分類樹（二叉排序樹、二叉查找樹） 特殊二叉樹之一： 舉例： 給定數(shù)據(jù)元素： 5 1 3