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

　　

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