數(shù)據(jù)結(jié)構(gòu)PPT樹和二叉樹PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)PPT樹和二叉樹樹和二叉樹 引 言第1頁/共188頁第2頁/共188頁6.1 樹的定義樹的定義 和基本術(shù)語和基本術(shù)語第3頁/共188頁 樹的定義第4頁/共188頁第5頁/共188頁數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集，則稱為空樹為空集，則稱為空樹 。 否則否則: (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root； (2) 當(dāng)當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互個(gè)互 不相交的有限集不相交的有限集T1, T2, , Tm，其中每一，其中每一 棵子集本身又是一

2、棵符合本定義的樹，棵子集本身又是一棵符合本定義的樹， 稱為根稱為根root的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R：ADT Tree第6頁/共188頁 基本操作：基本操作：查查 找找 類類 插插 入入 類類刪刪 除除 類類第7頁/共188頁 Root(T) / 求樹的根結(jié)點(diǎn)求樹的根結(jié)點(diǎn) 查找類：查找類：Value(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的元素值求當(dāng)前結(jié)點(diǎn)的元素值 Parent(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)的最左孩子求當(dāng)前結(jié)點(diǎn)的最左孩子 RightSibling(T, cur_e) / 求當(dāng)前結(jié)點(diǎn)

3、的右兄弟求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T) / 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) / 求樹的深度求樹的深度TraverseTree( T, Visit() ) / 遍歷遍歷第8頁/共188頁InitTree(&T) / 初始化置空樹初始化置空樹 插入類：插入類：CreateTree(&T, definition) / 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e, value) / 給當(dāng)前結(jié)點(diǎn)賦值給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T, &p, i, c) / 將以將以c為根的樹插入為結(jié)點(diǎn)為根的樹插入為結(jié)點(diǎn)p的第的第i棵子樹棵子樹第9頁/共188

4、頁 ClearTree(&T) / 將樹清空將樹清空 刪除類：刪除類：DestroyTree(&T) / 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(&T, &p, i) / 刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)p的第的第i棵子樹棵子樹第10頁/共188頁 樹的表示形式樹的表示形式第11頁/共188頁ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2樹根例如例如: :第12頁/共188頁第13頁/共188頁基基 本本 術(shù)術(shù) 語語第14頁/共188頁結(jié)點(diǎn)結(jié)點(diǎn): :結(jié)點(diǎn)的度結(jié)點(diǎn)的度: :樹的度樹的度: :葉子結(jié)點(diǎn)葉子結(jié)點(diǎn): :分支結(jié)點(diǎn)分支結(jié)點(diǎn): :數(shù)據(jù)

5、元素及若干指向子樹的分支擁有的子樹數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM第15頁/共188頁(從根到結(jié)點(diǎn)的)路徑：路徑：結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次: :樹的深度：樹的深度： 由從根根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l 層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次孩子結(jié)點(diǎn)：結(jié)點(diǎn)子樹的根雙親結(jié)點(diǎn)：孩子結(jié)點(diǎn)的直接前驅(qū)兄弟結(jié)點(diǎn)：同一雙親的孩子間堂兄弟：雙親在同一層的結(jié)點(diǎn)祖先結(jié)點(diǎn)：從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)第16頁/共188頁() 有確定的根；() 樹根和子樹根之間為有向關(guān)系。有向樹

6、：有向樹：有序樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：無序樹：子樹之間不存在確定的次序關(guān)系。第17頁/共188頁任何一棵非空樹是一個(gè)二元組 Tree = （root，F(xiàn)）其中：root 被稱為根結(jié)點(diǎn) F 被稱為子樹森林森林：森林：是m（m0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF第18頁/共188頁對(duì)比對(duì)比樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)的結(jié)構(gòu)特點(diǎn)第19頁/共188頁線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素第一個(gè)數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點(diǎn)根結(jié)點(diǎn) ( (無前驅(qū)無前驅(qū)) )最后一個(gè)數(shù)據(jù)元素最后一個(gè)數(shù)據(jù)元素 (無后繼無后繼)多個(gè)葉子結(jié)點(diǎn)多

7、個(gè)葉子結(jié)點(diǎn) ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 一個(gè)后繼一個(gè)后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個(gè)前驅(qū)、一個(gè)前驅(qū)、 多個(gè)后繼多個(gè)后繼) )第20頁/共188頁6.2 二二 叉叉 樹樹第21頁/共188頁6.2.1 二叉樹的定義二叉樹的定義 二叉樹（二叉樹（Binary Tree）或?yàn)榭諛?，或是由一個(gè)）或?yàn)榭諛洌蚴怯梢粋€(gè)根結(jié)點(diǎn)加上兩棵分別稱為根結(jié)點(diǎn)加上兩棵分別稱為左子樹左子樹和和右子樹右子樹的、的、互不相交的互不相交的二叉樹組成。二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹第22頁/共188頁二叉樹的五種基本形態(tài)：二叉樹的五種基本形態(tài)：N空樹空

8、樹只含根結(jié)點(diǎn)只含根結(jié)點(diǎn)NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹第23頁/共188頁第24頁/共188頁二叉樹的主要基本操作二叉樹的主要基本操作：查查 找找 類類插插 入入 類類刪刪 除除 類類第25頁/共188頁 Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Vi

9、sit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();第26頁/共188頁 InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);第27頁/共188頁ClearBiTree(&T); DestroyBiTree(&T);DeleteChild(T, p, LR);第28頁/共188頁6.2.2 二叉樹二叉樹 的性質(zhì)的性質(zhì)第29頁/

10、共188頁用歸納法證明用歸納法證明： 歸納基歸納基： 歸納假設(shè)：歸納假設(shè)： 歸納證明：歸納證明：i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i-1 = 20 = 1；假設(shè)對(duì)所有的 j，1 j i，命題成立；二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第 i 層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。第30頁/共188頁證明：證明： 基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1 。第31頁/共188頁證明：證明：設(shè)設(shè) 二叉樹上結(jié)點(diǎn)總數(shù) n = n0 + n1 + n2又又 二叉樹上分支總數(shù) b = n1+2n2 而 b = n-1 = n0 + n1 + n2

11、 - 1由此，由此， n0 = n2 + 1 。第32頁/共188頁兩類兩類特殊特殊的二叉樹：的二叉樹：滿二叉樹滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)編號(hào)為為 1 至至 n 的結(jié)點(diǎn)的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789 10 11 12 13 14 15abcdefghij第33頁/共188頁 性質(zhì)性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度深度為 log2n +1 。證明：證明：設(shè)設(shè)完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k-1 n 2k 即 k-1 log2 n n，則該結(jié)點(diǎn)無左孩子， 否則，編號(hào)為 2i 的

12、結(jié)點(diǎn)為其左孩子左孩子結(jié)點(diǎn)；(3) 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號(hào)為2i+1 的結(jié)點(diǎn)為其右孩子右孩子結(jié)點(diǎn)。第35頁/共188頁第36頁/共188頁6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)蕉?、二叉樹的鏈?zhǔn)?存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)一、一、 二叉樹的順序二叉樹的順序 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)第37頁/共188頁#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù)typedef TElemType SqBiTreeMAX_ TREE_SIZE; / 0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTree bt;一、一、 二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)第38頁/共18

13、8頁個(gè)足以反映整個(gè)二叉樹結(jié)構(gòu)的線性個(gè)足以反映整個(gè)二叉樹結(jié)構(gòu)的線性序列，如下圖所示。序列，如下圖所示。二叉樹的順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)第39頁/共188頁第40頁/共188頁第41頁/共188頁第42頁/共188頁練習(xí)練習(xí):ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326第43頁/共188頁二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線索鏈表線索鏈表第44頁/共188頁ADEBCF rootlchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):1.

14、1. 二叉鏈表二叉鏈表二叉鏈表二叉鏈表第45頁/共188頁ABCDEF二叉樹二叉樹第46頁/共188頁typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :第47頁/共188頁ADEBCF root 2三叉鏈表三叉鏈表parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):第48頁/共188頁 typedef struct

15、 TriTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;parent lchild data rchild結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :第49頁/共188頁0123456B2C0A -1D2E3F4 data parent結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):3 3雙親鏈表雙親鏈表LRTagLRRRL第50頁/共188頁 typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu)

16、結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int *parent; / 指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域 BPTNode typedef struct BPTree / 樹結(jié)構(gòu)樹結(jié)構(gòu) BPTNode nodesMAX_TREE_SIZE; int num_node; / 結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置 BPTree第51頁/共188頁6.3.1二叉樹的遍歷二叉樹的遍歷6.3 遍歷二叉樹和遍歷二叉樹和線索二叉樹線索二叉樹第52頁/共188頁一、問題的提出一、問題的提出二、先左后右的遍歷算法二、先左后右的遍歷算法三、算法的遞歸描述三、算法的遞歸描述四、中

17、序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述五五、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例第53頁/共188頁 如何按著某條搜索路徑如何按著某條搜索路徑巡訪巡訪二叉二叉樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)樹中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被均被訪問一次訪問一次，而且，而且僅被訪問一次僅被訪問一次。一、問題的提出一、問題的提出“訪問訪問”的含義可以很廣，如：輸出結(jié)的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。點(diǎn)的信息等。第54頁/共188頁 “遍歷遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)， 每個(gè)結(jié)點(diǎn)有兩個(gè)后繼每個(gè)結(jié)點(diǎn)有兩個(gè)后

18、繼，則存在如何遍歷存在如何遍歷即按什么樣的搜索搜索路徑路徑遍歷的問題。第55頁/共188頁二叉樹的遍歷方法二叉樹的遍歷方法 二叉樹由根、左子樹、右子樹三部分組成 二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：令：L L：遍歷左子樹 D D：訪問根結(jié)點(diǎn) R R：遍歷右子樹 有六種遍歷方法： D DL LR R，L LD DR R，L LR RD D， D DR RL L，R RD DL L，R RL LD D 約定先左后右,有三種遍歷方法： D DL LR R、L LD DR R、L LR RD D ，分別稱為 先序遍歷、中序遍歷、后序遍歷 A A F F G G E E D D C

19、 C B B第56頁/共188頁58 先序遍歷（先序遍歷（ D DL LR R ） 若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹；）先序遍歷左子樹； （3 3）先序遍歷右子樹）先序遍歷右子樹； 先序遍歷序列：先序遍歷序列： A A F F G G E E D D C C B B例：先序遍歷右圖所示的二叉樹例：先序遍歷右圖所示的二叉樹 （1 1）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)A A （2 2）先序遍歷左子樹：即按先序遍歷左子樹：即按D DL LR R的順序遍歷的順序遍歷左子樹左子樹 （3 3）先序遍歷右子樹：即按）先序遍歷右子樹：即按D DL LR R的順序遍

20、歷的順序遍歷右子樹右子樹A BCDFGE二、先左后右的遍歷算法二、先左后右的遍歷算法第57頁/共188頁59中序遍歷（中序遍歷（ L LD DR R ）若二叉樹非空若二叉樹非空（1 1）中序遍歷左子樹）中序遍歷左子樹（2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn)（3 3）中序遍歷右子樹）中序遍歷右子樹 中序遍歷序列： A A F F G G E E D D C C B B例：中序遍歷右圖所示的二叉樹例：中序遍歷右圖所示的二叉樹 （1 1）中序遍歷左子樹：即按）中序遍歷左子樹：即按L LD DR R的順序遍歷的順序遍歷左子樹左子樹 （2 2）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) A A （3 3）中序遍歷右子樹：即按中序遍

21、歷右子樹：即按L LD DR R的順序遍歷的順序遍歷右子樹右子樹D BCGFAE第58頁/共188頁60后序遍歷（后序遍歷（L LR RD D）若二叉樹非空若二叉樹非空（1 1）后序遍歷左子樹）后序遍歷左子樹（2 2）后序遍歷右子樹）后序遍歷右子樹（3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) 后序遍歷序列：例：后序遍歷右圖所示的二叉樹例：后序遍歷右圖所示的二叉樹 （1 1）后序遍歷左子樹：即按）后序遍歷左子樹：即按L LR RD D的順序遍歷的順序遍歷左子樹左子樹 （2 2）后序遍歷右子樹：即按）后序遍歷右子樹：即按L LR RD D的順序遍歷的順序遍歷右子樹右子樹 （3 3）訪問根結(jié)點(diǎn)）訪問根結(jié)點(diǎn) A

22、A A A F F G G E E D D C C B BD GCEAFB第59頁/共188頁61 e e d d c c b b f f a a + + * * / / - - - - 后序遍歷序列： 中序遍歷序列： 先序遍歷序列：例：先例：先中序遍歷序遍歷、中序遍歷、中序遍歷序遍歷、中序遍歷、后后序遍歷下圖所示的二叉樹序遍歷下圖所示的二叉樹前綴表達(dá)式前綴表達(dá)式中綴表達(dá)式中綴表達(dá)式后綴表達(dá)式后綴表達(dá)式- + a * b - c d /e fa + b * c - d - e /fa b c d -* + e f /-第60頁/共188頁R A DE C HF GBK練習(xí)：求下列二叉鏈表和二叉

23、樹的三種遍歷次序練習(xí)：求下列二叉鏈表和二叉樹的三種遍歷次序ABCDEFGHK第61頁/共188頁這實(shí)際上是這實(shí)際上是先序遍歷的遞歸定義，先序遍歷的遞歸定義，我們知道遞歸定義包括兩個(gè)部分：我們知道遞歸定義包括兩個(gè)部分：1 1）基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）；（也叫終止項(xiàng)）； 2 2）遞歸項(xiàng)遞歸項(xiàng) 若二叉樹非空若二叉樹非空 （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹；先序遍歷遞歸定義先序遍歷遞歸定義遞歸項(xiàng)遞歸項(xiàng)上面介紹了三種遍歷方法，顯然是用遞歸的方式給出的三種遍歷方上面介紹了三種遍歷方法，顯然是用遞歸的方式給出的三種遍歷

24、方法，以先序?yàn)槔悍?，以先序?yàn)槔合刃虮闅v（先序遍歷（D DL LR R）的定義：）的定義：該定義隱含著該定義隱含著若二叉樹為空，結(jié)束若二叉樹為空，結(jié)束 三、算法的遞歸描述三、算法的遞歸描述第62頁/共188頁上面先序遍歷的定義等價(jià)于：上面先序遍歷的定義等價(jià)于：若二叉樹為空，結(jié)束若二叉樹為空，結(jié)束 基本項(xiàng)基本項(xiàng)（也叫終止項(xiàng)）（也叫終止項(xiàng)）若二叉樹非空若二叉樹非空 遞歸項(xiàng)遞歸項(xiàng) （1 1）訪問根結(jié)點(diǎn)；）訪問根結(jié)點(diǎn)； （2 2）先序遍歷左子樹）先序遍歷左子樹 （3 3）先序遍歷右子樹；）先序遍歷右子樹； 下面給出下面給出先序、中序、后序遍歷遞歸算法，為了增加算法的先序、中序、后序遍歷遞歸算法，為了

25、增加算法的可讀性，這里對(duì)書上算法作了簡化，沒有考慮訪問結(jié)點(diǎn)出錯(cuò)的可讀性，這里對(duì)書上算法作了簡化，沒有考慮訪問結(jié)點(diǎn)出錯(cuò)的情況（即我們假設(shè)調(diào)用函數(shù)情況（即我們假設(shè)調(diào)用函數(shù)visit( )visit( )訪問結(jié)點(diǎn)總是成功的。訪問結(jié)點(diǎn)總是成功的。第63頁/共188頁1先序遍歷遞歸算法先序遍歷遞歸算法 void PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的函數(shù)。本算法是訪問結(jié)點(diǎn)的函數(shù)。本算法/先序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)先序遍歷以為根

26、結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)/Visit( ) if (T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 / 若二叉樹不為空，訪問根結(jié)點(diǎn)；遍歷左子樹，遍歷右子樹若二叉樹不為空，訪問根結(jié)點(diǎn)；遍歷左子樹，遍歷右子樹 Visit(T-data)； PreOrderTraverse(T-lchild, Visit); PreOrderTraverse(T-rchild, Visit); /PreOrderTraverse最簡單的最簡單的Visit函數(shù)是：函數(shù)是： Status PrintElement(TElemType e) /輸出元素輸出元素e的值的值 printf(e); ret

27、urn OK; D D A A B B C C E E FFT T第64頁/共188頁2 中序遍歷遞歸算法中序遍歷遞歸算法 void InOrderTraverse(BiTree T, Status(*Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的函數(shù)。本算法中是訪問結(jié)點(diǎn)的函數(shù)。本算法中序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit( ) if (T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 / 若二叉樹不為空，遍歷左子樹，訪問根結(jié)點(diǎn)，遍歷右子樹

28、若二叉樹不為空，遍歷左子樹，訪問根結(jié)點(diǎn)，遍歷右子樹 InOrderTraverse(T-lchild, Visit); Visit(T-data)； InOrderTraverse(T-rchild, Visit); / InOrderTraverse 你能寫出你能寫出后序遍歷遞歸算法了吧后序遍歷遞歸算法了吧?第65頁/共188頁3 后序遍歷遞歸算法后序遍歷遞歸算法 void PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) /采用二叉鏈表存貯二叉樹，采用二叉鏈表存貯二叉樹， visit( )是訪問結(jié)點(diǎn)的函數(shù)。本算法中是訪問結(jié)點(diǎn)的

29、函數(shù)。本算法中序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)序遍歷以為根結(jié)點(diǎn)指針的二叉樹，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit( ) if (T) /若二叉樹為空，結(jié)束返回若二叉樹為空，結(jié)束返回 / 若二叉樹不為空，遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn)若二叉樹不為空，遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn) PostOrderTraverse(T-lchild, Visit); PostOrderTraverse(T-rchild, Visit); Visit(T-data)； /PostOrderTraverse 第66頁/共188頁G HD E FB CA第67頁/共188頁四、中序遍歷算法的非

30、遞歸描述四、中序遍歷算法的非遞歸描述Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用是對(duì)數(shù)據(jù)元素操作的應(yīng)用/函數(shù)函數(shù).中序遍歷二叉樹中序遍歷二叉樹T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)/用函數(shù)用函數(shù)Visit。 InitStack(S); Push(S, T); / 根指針進(jìn)棧根指針進(jìn)棧 while (!StackEmpty(S) while (GetTop(S, p) & p) Push(S, p-lchild); /

31、向左走到盡頭向左走到盡頭 Pop(S, p); / 空指針退?？罩羔樛藯?if (!StackEmpty(S) / 訪問結(jié)點(diǎn)，向右一步訪問結(jié)點(diǎn)，向右一步 Pop(S, p); if (!Visit(p-data) return ERROR; Push(S, p-rchild); return OK; / InOrderTraverse第68頁/共188頁Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用是對(duì)數(shù)據(jù)元素操作的應(yīng)用/函數(shù)。中序遍歷二叉樹函

32、數(shù)。中序遍歷二叉樹T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)/用函數(shù)用函數(shù)Visit。 InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; / 非空指針進(jìn)棧，繼續(xù)左進(jìn)非空指針進(jìn)棧，繼續(xù)左進(jìn) else /上層指針退棧，訪問其所指結(jié)點(diǎn)，再向右進(jìn)上層指針退棧，訪問其所指結(jié)點(diǎn)，再向右進(jìn) Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse第69頁/共188頁

33、ABCDGEFABCNULLSGetToplchild)& (!T-rchild) count+; / 對(duì)葉子結(jié)點(diǎn)計(jì)數(shù) CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); / if / CountLeaf第73頁/共188頁2、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)算法基本思想算法基本思想: : 從二叉樹深度的定義可知，二叉樹的二叉樹的深度應(yīng)為其左、右子樹深度的最大值加深度應(yīng)為其左、右子樹深度的最大值加1 1。由此，需先分別求得左、右子樹的深度，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、求得左、

34、右子樹深度的最大值，然后加右子樹深度的最大值，然后加 1 1 。 首先分析二叉樹的深度二叉樹的深度和它的左左、右子右子樹深度樹深度之間的關(guān)系。第74頁/共188頁int Depth (BiTree T ) / 返回二叉樹的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;第75頁/共188頁3、復(fù)制二

35、叉樹、復(fù)制二叉樹其基本操作為：生成一個(gè)結(jié)點(diǎn)。其基本操作為：生成一個(gè)結(jié)點(diǎn)。根元素根元素T左子樹左子樹右子樹右子樹根元素根元素NEWT左子樹左子樹右子樹右子樹左子樹左子樹右子樹右子樹(后序遍歷后序遍歷)第76頁/共188頁BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = (BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生

36、成一個(gè)二叉樹的結(jié)點(diǎn)生成一個(gè)二叉樹的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)槠鋽?shù)據(jù)域?yàn)閕tem,左指針域?yàn)樽笾羔樣驗(yàn)閘ptr,右指針域?yàn)橛抑羔樣驗(yàn)閞ptr)第77頁/共188頁BiTNode *CopyTree(BiTNode *T) if (!T ) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild);/復(fù)制左子樹 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild);/復(fù)制右子樹 else newrptr = NULL; newT = GetTreeNode(T-data, ne

37、wlptr, newrptr); return newT; / CopyTree第78頁/共188頁ABCDEFGHK D C B H K G F E A例如：下列二叉例如：下列二叉樹的復(fù)制過程如樹的復(fù)制過程如下：下：newT第79頁/共188頁 為二叉樹建立二叉鏈表為二叉樹建立二叉鏈表 輸入：輸入：二叉樹的先序序列二叉樹的先序序列 結(jié)果：結(jié)果：二叉樹的二叉鏈表二叉樹的二叉鏈表 遍歷操作訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次遍歷操作訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次。是否可在利用。是否可在利用遍歷，建立遍歷，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)

38、點(diǎn)的鏈接？的鏈接？基本思想基本思想：輸入（輸入（在空子樹處添加在空子樹處添加* *的二叉樹的）先序序列（設(shè)每的二叉樹的）先序序列（設(shè)每個(gè)元素是個(gè)元素是一個(gè)字符）按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)一個(gè)字符）按先序遍歷的順序，建立二叉鏈表的所有結(jié)點(diǎn)并完成相應(yīng)結(jié)點(diǎn)的鏈接并完成相應(yīng)結(jié)點(diǎn)的鏈接第80頁/共188頁 D D A A B B C C E E F F T T 先序序列：A B D F C E（在空子樹處添加（在空子樹處添加* *的二叉樹的）先序序列：的二叉樹的）先序序列： A B D A B D * * F F * * * * * *C E C E * * * * * * A A F F

39、 E E D D C C B B* A A F F E E D D C C B B第81頁/共188頁Status CreateBiTree(BiTree &T) /輸入（在空子樹處添加*的二叉樹的）先序序列（設(shè)每個(gè)元/素是一個(gè)字 符）按先序遍歷的順序，建立二叉鏈表，并將/該二叉鏈表根結(jié)點(diǎn)指針賦給T scanf (&ch); if (ch= = * )T=NULL; / 若ch= = * 則T=NULL返回 else / 若ch! = * if (! (T=(BiTNode * )malloc(sizeof(BiTNode) exit(OVERFLOW); T-date = ch; / 建立（

40、根）結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹 CreateBiTree(T-rchild); /構(gòu)造右子樹 return OK;/CreateBiTree第82頁/共188頁84分析：若二叉樹的任意兩個(gè)結(jié)點(diǎn)的值都不相同，則二叉樹的前序序列和中序序列能唯一確定一棵二叉樹。另外，由前序序列和中序序列的定義可知，前序序列中第一個(gè)結(jié)點(diǎn)必為根結(jié)點(diǎn)，而在中序序列中，根結(jié)點(diǎn)剛好是左、右子樹的分界點(diǎn)，因此，可按如下方法建立二叉樹：由二叉樹的先序和中序序列建立二叉樹由二叉樹的先序和中序序列建立二叉樹二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根

41、根第83頁/共188頁851.1.用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)用前序序列的第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn); ;2.2.在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序在中序序列中查找根結(jié)點(diǎn)的位置，并以此為界將中序序列劃分為左、右兩個(gè)序列列劃分為左、右兩個(gè)序列( (左、右子樹左、右子樹););3.3.根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序根據(jù)左、右子樹的中序序列中的結(jié)點(diǎn)個(gè)數(shù)，將前序序列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是列去掉根結(jié)點(diǎn)后的序列劃分為左、右兩個(gè)序列，它們分別是左、右子樹的前序序列左、右子樹的前序序列; ;4.4.對(duì)左、右子樹的前序序列和中序序列遞歸地實(shí)施同樣方對(duì)左、右

42、子樹的前序序列和中序序列遞歸地實(shí)施同樣方法，直到所得左、右子樹為空。法，直到所得左、右子樹為空。假設(shè)前序序列為假設(shè)前序序列為ABDGHCEFIABDGHCEFI，中序序列為中序序列為GDHBAECIFGDHBAECIF， 則得到的二叉樹如下頁所則得到的二叉樹如下頁所示示第84頁/共188頁861. 1. A A為根結(jié)點(diǎn)為根結(jié)點(diǎn)A BDGH CEFI GDHB A ECIF BDGHCEFIA2. 2. B B為左子樹的根結(jié)為左子樹的根結(jié)點(diǎn)點(diǎn)B DGHGDH BCEFIDHGBA3. 3. D D為左子樹的左子樹為左子樹的左子樹的根結(jié)點(diǎn)的根結(jié)點(diǎn) A B G H D C E F I 第85頁/共1

43、88頁87 A B G H D C FI E 4. 4. C C為右子樹的根結(jié)點(diǎn)為右子樹的根結(jié)點(diǎn) A B G H D C F I E 5. 5. F F為右子樹的右為右子樹的右子樹的根結(jié)點(diǎn)子樹的根結(jié)點(diǎn)C E FIE C IF第86頁/共188頁a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列第87頁/共188頁ACBEDFGABCDEFGABCFDEG第88頁/共188頁第89頁/共188頁遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序先序序列: A B C D E F G H K中序中序

44、序列: B D C A H G K F E后序后序序列: D C B H K G F E A一、一、線索二叉樹的定義線索二叉樹的定義第90頁/共188頁在這樣的線性序列中，很容易求得某個(gè)結(jié)點(diǎn)在某種在這樣的線性序列中，很容易求得某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。然而，有時(shí)我們希望不進(jìn)行遍歷下的直接前驅(qū)和后繼。然而，有時(shí)我們希望不進(jìn)行遍歷就能快速找到某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和遍歷就能快速找到某個(gè)結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼，這樣，就應(yīng)該把每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼后繼，這樣，就應(yīng)該把每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼記錄下來。為了做到這一點(diǎn)，可以在原來的二叉鏈表結(jié)記錄下來。為了做到這一點(diǎn)

45、，可以在原來的二叉鏈表結(jié)點(diǎn)中，再增加兩個(gè)指針域，一個(gè)指向前驅(qū)，一個(gè)指向后點(diǎn)中，再增加兩個(gè)指針域，一個(gè)指向前驅(qū)，一個(gè)指向后繼，但這樣做將會(huì)浪費(fèi)大量存貯單元，存貯空間的利用繼，但這樣做將會(huì)浪費(fèi)大量存貯單元，存貯空間的利用率相當(dāng)?shù)吐氏喈?dāng)?shù)? (一個(gè)結(jié)點(diǎn)中有一個(gè)結(jié)點(diǎn)中有4 4個(gè)指針，個(gè)指針，1 1個(gè)指左孩子，個(gè)指左孩子，1 1個(gè)指個(gè)指右孩子，右孩子，1 1個(gè)指前驅(qū)，個(gè)指前驅(qū)，1 1個(gè)指后繼個(gè)指后繼) )，而原來的左、右孩子，而原來的左、右孩子域有許多空指針又沒有利用起來。為了不浪費(fèi)存貯空間，域有許多空指針又沒有利用起來。為了不浪費(fèi)存貯空間，我們利用原有的孩子指針為空時(shí)來存放直接前驅(qū)和后繼，我們利用原有

46、的孩子指針為空時(shí)來存放直接前驅(qū)和后繼，這樣的指針稱為這樣的指針稱為“線索線索”，加線索的過程稱為，加線索的過程稱為線索化線索化，加了線索的二叉樹，稱為加了線索的二叉樹，稱為線索二叉樹線索二叉樹，對(duì)應(yīng)的二叉鏈表，對(duì)應(yīng)的二叉鏈表稱為稱為線索二叉鏈表線索二叉鏈表。一、一、線索二叉樹的定義線索二叉樹的定義第91頁/共188頁指向該線性序列中的“前驅(qū)”和 “后繼” 的指針指針，稱作“線索線索”加了線索的二叉樹，稱作 “線索二叉樹線索二叉樹”包含 “線索” 的二叉鏈表，稱作 “線線索鏈表索鏈表”A B C D E F G H K D C B E 第92頁/共188頁在線索二叉樹中，由于有了線索，無需遍歷二

47、叉在線索二叉樹中，由于有了線索，無需遍歷二叉樹就可以得到任一結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后樹就可以得到任一結(jié)點(diǎn)在某種遍歷下的直接前驅(qū)和后繼。但是，我們怎樣來區(qū)分孩子指針域中存放的是左、繼。但是，我們怎樣來區(qū)分孩子指針域中存放的是左、右孩子信息還是直接前驅(qū)或直接后繼信息呢右孩子信息還是直接前驅(qū)或直接后繼信息呢? ?為此，為此，在二叉鏈表結(jié)點(diǎn)中，還必須增加兩個(gè)標(biāo)志域在二叉鏈表結(jié)點(diǎn)中，還必須增加兩個(gè)標(biāo)志域ltagltag、rtagrtag。 ltag和rtag定義如下： 0 lchild域指向結(jié)點(diǎn)的左孩子域指向結(jié)點(diǎn)的左孩子 ltag= 1 lchild域指向結(jié)點(diǎn)在某種遍歷下的直接前域指向結(jié)點(diǎn)在某種遍

48、歷下的直接前驅(qū)驅(qū) 0 rchild域指向結(jié)點(diǎn)的右孩子域指向結(jié)點(diǎn)的右孩子 rtag= 1 rchild域指向結(jié)點(diǎn)在某種遍歷下的直接后域指向結(jié)點(diǎn)在某種遍歷下的直接后繼繼 第93頁/共188頁這樣，二叉鏈表中每個(gè)結(jié)點(diǎn)還是有這樣，二叉鏈表中每個(gè)結(jié)點(diǎn)還是有5個(gè)個(gè)域，但其中只有域，但其中只有2個(gè)指針，較原來的個(gè)指針，較原來的4個(gè)指個(gè)指針要方便。增加線索后的二叉鏈表結(jié)點(diǎn)結(jié)針要方便。增加線索后的二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)可描述如下：構(gòu)可描述如下： lchild ltag data rtag rchild 第94頁/共188頁typedef struct BiThrNod TElemType data; struct B

49、iThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;二、線索的描述：1、類型定義：、類型定義： typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索第95頁/共188頁2線索的畫法線索的畫法在二叉樹或二叉鏈表中，若左孩子為空，則在二叉樹或二叉鏈表中，若左孩子為空，則畫出它的直接前驅(qū)，右孩子為空時(shí)，則畫出它的畫出它的直接前驅(qū)，右孩子為空時(shí)，則畫出它的直接后繼，左右孩子不為空時(shí)，不需畫前驅(qū)和后直接后繼，左右孩子

50、不為空時(shí)，不需畫前驅(qū)和后繼。這樣就得到了線索二叉樹或線索二叉鏈表。繼。這樣就得到了線索二叉樹或線索二叉鏈表。第96頁/共188頁 A D C B 0 A 0 1 B 1 0 C 1 root 1 D 1 A D C B NULL (a) 二叉樹 (b)先序線索二叉樹 (c)先序線索二叉鏈表 圖 先序線索示意圖 先序序列為：ABCD第97頁/共188頁 A D C B NULL NULL （a）中序二叉樹 （b） 中序線索二叉鏈表 圖 中序線索示意圖 0 A 0 root 1 D 1 0 C 1 1 B 1 中序序列為：BADC第98頁/共188頁 C 0 A 0 1 B 1 0 C 1 1 D

51、 1 root D B A NULL (a)后序線索二叉樹 (b)后序線索二叉鏈表 圖 后序線索示意圖 后序序列為：BDCA第99頁/共188頁ABCDE第100頁/共188頁ABCDE A B D C ET先序序列：ABCDE先序線索二叉鏈表00001111 11第101頁/共188頁ABCDE A B D C ET中序序列：BCAED中序線索二叉鏈表0000111111第102頁/共188頁ABCDE A B D C ET后序序列：CBEDA后序線索二叉鏈表0000111111第103頁/共188頁ABCDE 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAE

52、D帶頭結(jié)點(diǎn)的中序線索二叉鏈表 0 1頭結(jié)點(diǎn)：ltag=0, lchild指向根結(jié)點(diǎn)rtag=1, rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lchild域和最后一個(gè)結(jié)點(diǎn)的rchild域都指向頭結(jié)點(diǎn) A B D C ET中序序列：BCAED中序線索二叉鏈表0000111111第104頁/共188頁 建立線索二叉樹，或者說對(duì)二叉樹線索化，實(shí)質(zhì)上就建立線索二叉樹，或者說對(duì)二叉樹線索化，實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，訪問結(jié)點(diǎn)的操作是是遍歷一棵二叉樹。在遍歷過程中，訪問結(jié)點(diǎn)的操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將

53、它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過程，設(shè)指針過程，設(shè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，即若指針始終指向剛剛訪問過的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增設(shè)線索。指向它的前驅(qū)，以便增設(shè)線索。 此外，在對(duì)一棵二叉樹加線索時(shí)，必須首先申請一個(gè)此外，在對(duì)一棵二叉樹加線索時(shí)，必須首先申請一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹的根結(jié)點(diǎn)的指向關(guān)系，對(duì)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹的根結(jié)點(diǎn)的指向關(guān)系，對(duì)二叉樹線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間二叉樹線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。的線索。 三、建

54、立線索二叉樹三、建立線索二叉樹第105頁/共188頁void InThreading(BiThrTree p) if (p) / 對(duì)以p為根的非空二叉樹進(jìn)行線索化 InThreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅(qū)線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驅(qū) InThreading(p-rchild); / 右子樹線索化 / if / InTh

55、reading第106頁/共188頁Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 構(gòu)建中序線索鏈表 if (!(Thrt = (BiThrTree)malloc( sizeof( BiThrNode) exit (OVERFLOW); Thrt-LTag = Link; Thrt-RTag =Thread; Thrt-rchild = Thrt; / 添加頭結(jié)點(diǎn) return OK; / InOrderThreading 第107頁/共188頁if (!T) Thrt-lchild = Thrt; else Thrt-lchil

56、d = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 處理最后一個(gè)結(jié)點(diǎn) pre-RTag = Thread; Thrt-rchild = pre; 第108頁/共188頁四、四、 線索二叉樹上的運(yùn)算線索二叉樹上的運(yùn)算1線索二叉樹上的查找線索二叉樹上的查找 （1）查找指定結(jié)點(diǎn)在中序線索二叉樹中的的直接后繼）查找指定結(jié)點(diǎn)在中序線索二叉樹中的的直接后繼若所找結(jié)點(diǎn)右標(biāo)志若所找結(jié)點(diǎn)右標(biāo)志rtag=1，則右孩子域指向中序后繼，則右孩子域指向中序后繼，否則，中序后繼應(yīng)為否則，中序后繼應(yīng)為遍歷右子樹時(shí)的第一個(gè)訪問結(jié)點(diǎn)遍歷右子樹時(shí)的第一個(gè)訪問結(jié)點(diǎn),即右即

57、右子樹中最左下的結(jié)點(diǎn)子樹中最左下的結(jié)點(diǎn)（參見下圖）。從下圖中可知，（參見下圖）。從下圖中可知，x的后的后繼為繼為xk 。 X X1 X2 XK P X 0 P 0 x1 0 x2 1 xk 圖 求中序后繼示意圖 第109頁/共188頁（2）查找指定結(jié)點(diǎn)在中序線索二叉樹中的的直接）查找指定結(jié)點(diǎn)在中序線索二叉樹中的的直接前驅(qū)前驅(qū)若所找結(jié)點(diǎn)左標(biāo)志若所找結(jié)點(diǎn)左標(biāo)志ltag=1，則左孩子域指向中序前驅(qū)，則左孩子域指向中序前驅(qū)，否則，中序前驅(qū)應(yīng)為否則，中序前驅(qū)應(yīng)為遍歷左子樹時(shí)的最后一個(gè)訪問結(jié)點(diǎn)，即遍歷左子樹時(shí)的最后一個(gè)訪問結(jié)點(diǎn)，即左子樹中最右下的結(jié)點(diǎn)左子樹中最右下的結(jié)點(diǎn)（參見下圖）。從下圖中可知，（參見下

58、圖）。從下圖中可知，x的的前驅(qū)為前驅(qū)為xk 。 X X1 X2 xk P 0 X P x1 0 x2 0 xk 1 圖 求中序前驅(qū)示意圖 第110頁/共188頁(3) 查找指定點(diǎn)在先序線索二叉樹中的直接后繼查找指定點(diǎn)在先序線索二叉樹中的直接后繼先序后繼的查找比較方便，若無左孩子，右先序后繼的查找比較方便，若無左孩子，右孩子為后繼，否則左孩子為后繼。孩子為后繼，否則左孩子為后繼。 (4) 查找指定結(jié)點(diǎn)在后序線索二叉樹中的直接前查找指定結(jié)點(diǎn)在后序線索二叉樹中的直接前驅(qū)驅(qū)后序前驅(qū)的查找也比較方便，若左孩子為空，后序前驅(qū)的查找也比較方便，若左孩子為空，左鏈指前驅(qū)，否則，若右子樹為空，左孩子為前驅(qū)，左鏈

59、指前驅(qū)，否則，若右子樹為空，左孩子為前驅(qū)，否則右孩子為前驅(qū)。否則右孩子為前驅(qū)。 求后序后繼和先序前驅(qū)都比較麻煩，在此不再求后序后繼和先序前驅(qū)都比較麻煩，在此不再作進(jìn)一步介紹。作進(jìn)一步介紹。第111頁/共188頁2線索二叉樹上的遍歷線索二叉樹上的遍歷 遍歷某種次序的線索二叉樹，只要從該次序下遍歷某種次序的線索二叉樹，只要從該次序下的開始結(jié)點(diǎn)出發(fā)，反復(fù)找到結(jié)點(diǎn)在該次序下的后繼，的開始結(jié)點(diǎn)出發(fā)，反復(fù)找到結(jié)點(diǎn)在該次序下的后繼，直到后繼為空。這對(duì)于中序線索和前序線索二叉樹直到后繼為空。這對(duì)于中序線索和前序線索二叉樹很方便，但對(duì)于后序線索二叉樹較麻煩很方便，但對(duì)于后序線索二叉樹較麻煩(因求后序因求后序后繼

60、較麻煩后繼較麻煩)。故后序線索對(duì)于遍歷沒有什么意義。故后序線索對(duì)于遍歷沒有什么意義。第112頁/共188頁中序線索鏈表的遍歷算法中序線索鏈表的遍歷算法 中序遍歷的第一個(gè)結(jié)點(diǎn)中序遍歷的第一個(gè)結(jié)點(diǎn) ？ 在中序線索化鏈表中結(jié)點(diǎn)的后繼在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？左子樹上處于“最左下最左下”（沒有左子樹）的結(jié)點(diǎn)。若若無右子樹，則為則為后繼線索后繼線索所指結(jié)點(diǎn)；否則為否則為對(duì)其右子樹右子樹進(jìn)行中序遍歷遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。第一個(gè)結(jié)點(diǎn)。第113頁/共188頁void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lc