第5章樹和二叉樹

i/2；結(jié)點(diǎn)i的左孩子為2i；結(jié)點(diǎn)i的右孩子為2i＋1。

5.3二叉樹的邏輯結(jié)構(gòu)性質(zhì)5表明，在完全二叉樹中，結(jié)點(diǎn)的層序編號(hào)反映了結(jié)點(diǎn)之間的邏輯關(guān)系。完全二叉樹的基本性質(zhì)

二叉樹的抽象數(shù)據(jù)類型定義ADTBiTreeData

由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左右子樹構(gòu)成，結(jié)點(diǎn)具有相同數(shù)據(jù)類型及層次關(guān)系Operation

5.3二叉樹的邏輯結(jié)構(gòu)同樹類似，在不同的應(yīng)用中，二叉樹的基本操作不盡相同。下面給出一個(gè)二叉樹抽象數(shù)據(jù)類型定義的例子，簡單起見，基本操作只包含二叉樹的遍歷，在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體需要重新定義其基本操作。

InitBiTree

前置條件：無輸入：無功能：初始化一棵二叉樹輸出：無后置條件：構(gòu)造一個(gè)空的二叉樹DestroyBiTree

前置條件：二叉樹已存在輸入：無功能：銷毀一棵二叉樹輸出：無后置條件：釋放二叉樹占用的存儲(chǔ)空間

二叉樹的抽象數(shù)據(jù)類型定義5.3二叉樹的邏輯結(jié)構(gòu)

PreOrder前置條件：二叉樹已存在輸入：無功能：前序遍歷二叉樹輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列后置條件：二叉樹不變

InOrder

前置條件：二叉樹已存在輸入：無功能：中序遍歷二叉樹輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列后置條件：二叉樹不變二叉樹的抽象數(shù)據(jù)類型定義5.3二叉樹的邏輯結(jié)構(gòu)

PostOrder

前置條件：二叉樹已存在輸入：無功能：后序遍歷二叉樹輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列后置條件：二叉樹不變

LeverOrder

前置條件：二叉樹已存在輸入：無功能：層序遍歷二叉樹輸出：二叉樹中結(jié)點(diǎn)的一個(gè)線性排列后置條件：二叉樹不變endADT二叉樹的抽象數(shù)據(jù)類型定義5.3二叉樹的邏輯結(jié)構(gòu)二叉樹的遍歷操作

二叉樹的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。二叉樹遍歷操作的結(jié)果？非線性結(jié)構(gòu)線性化5.3二叉樹的邏輯結(jié)構(gòu)抽象操作，可以是對(duì)結(jié)點(diǎn)進(jìn)行的各種處理，這里簡化為輸出結(jié)點(diǎn)的數(shù)據(jù)。前序遍歷中序遍歷后序遍歷層序遍歷

二叉樹的遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD

如果限定先左后右，則二叉樹遍歷方式有三種：前序：DLR中序：LDR后序：LRD層序遍歷：按二叉樹的層序編號(hào)的次序訪問各結(jié)點(diǎn)。

5.3二叉樹的邏輯結(jié)構(gòu)考慮二叉樹的組成：根結(jié)點(diǎn)D左子樹L右子樹R二叉樹前序（根）遍歷若二叉樹為空，則空操作返回；否則：①訪問根結(jié)點(diǎn)；②前序遍歷根結(jié)點(diǎn)的左子樹；③前序遍歷根結(jié)點(diǎn)的右子樹。5.3二叉樹的邏輯結(jié)構(gòu)前序遍歷序列：ABDGCEFABCDEFG二叉樹的遍歷操作

中序（根）遍歷若二叉樹為空，則空操作返回；否則：①中序遍歷根結(jié)點(diǎn)的左子樹；②訪問根結(jié)點(diǎn)；③中序遍歷根結(jié)點(diǎn)的右子樹。

5.3二叉樹的邏輯結(jié)構(gòu)中序遍歷序列：DGBAECFABCDEFG二叉樹的遍歷操作

后序（根）遍歷若二叉樹為空，則空操作返回；否則：①后序遍歷根結(jié)點(diǎn)的左子樹；②后序遍歷根結(jié)點(diǎn)的右子樹。③訪問根結(jié)點(diǎn)；5.3二叉樹的邏輯結(jié)構(gòu)后序遍歷序列：GDBEFCAABCDEFG二叉樹的遍歷操作

層序遍歷二叉樹的層次遍歷是指從二叉樹的第一層（即根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。

5.3二叉樹的邏輯結(jié)構(gòu)層序遍歷序列：ABCDEFGABCDEFG二叉樹的遍歷操作

5.3二叉樹的邏輯結(jié)構(gòu)-%/+*abcdef二叉樹遍歷操作練習(xí)前序遍歷結(jié)果：-+a*b

%cd/ef中序遍歷結(jié)果：a+b*c%

d-e/f后序遍歷結(jié)果：abcd%*+ef/-5.3二叉樹的邏輯結(jié)構(gòu)若已知一棵二叉樹的前序（或中序，或后序，或?qū)有颍┬蛄校芊裎ㄒ淮_定這棵二叉樹呢？ABC例：已知前序序列為ABC，則可能的二叉樹有5種。ABC二叉樹的遍歷操作

5.3二叉樹的邏輯結(jié)構(gòu)例：已知前序遍歷序列為ABC，后序遍歷序列為CBA，則下列二叉樹都滿足條件。ABCABC若已知一棵二叉樹的前序序列和后序序列，能否唯一確定這棵二叉樹呢？二叉樹的遍歷操作

若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？

例如：已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構(gòu)造該二叉樹呢?

5.3二叉樹的邏輯結(jié)構(gòu)二叉樹的遍歷操作

前序：ABCDEFG

HI中序：BCAEDGHFI前序：BC中序：BC5.3二叉樹的邏輯結(jié)構(gòu)

BCDEFGHIA前序：DEFGHI中序：EDGHFIABCDEFGHI前序：FG

HI中序：GHFI5.3二叉樹的邏輯結(jié)構(gòu)前序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH1.根據(jù)前序序列的第一個(gè)元素建立根結(jié)點(diǎn)；2.在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹的中序序列；3.在前序序列中確定左右子樹的前序序列；4.由左子樹的前序序列和中序序列建立左子樹；5.由右子樹的前序序列和中序序列建立右子樹。5.3二叉樹的邏輯結(jié)構(gòu)已知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下：

二叉樹的遍歷操作

順序存儲(chǔ)結(jié)構(gòu)二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹中的結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系——父子關(guān)系。

如何利用數(shù)組下標(biāo)來反映結(jié)點(diǎn)之間的邏輯關(guān)系?完全二叉樹和滿二叉樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系。5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)

A

B

C

D

E

F

G

H

I

J數(shù)組下標(biāo)12345678910完全二叉樹的順序存儲(chǔ)5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)CDEFGHIJ以編號(hào)為下標(biāo)二叉樹的順序存儲(chǔ)ABC∧DE∧∧∧F∧∧G數(shù)組下標(biāo)123456789101112135.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEGF以編號(hào)為下標(biāo)ABCDEGF123561013按照完全二叉樹編號(hào)二叉樹的順序存儲(chǔ)ABC∧DE∧∧∧F∧∧G數(shù)組下標(biāo)01234567891011125.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEGFABCDEGF123561013按照完全二叉樹編號(hào)注意到C++語言的數(shù)組下標(biāo)從0開始，也可以將編號(hào)為i的結(jié)點(diǎn)存儲(chǔ)到下標(biāo)為i-1的位置。

一棵斜樹的順序存儲(chǔ)會(huì)怎樣呢？深度為k的右斜樹，k個(gè)結(jié)點(diǎn)需分配2k－1個(gè)存儲(chǔ)單元。

一棵二叉樹改造后，變成完全二叉樹形態(tài)，需增加很多空結(jié)點(diǎn)，造成存儲(chǔ)空間的浪費(fèi)。5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹!ABC137D15二叉鏈表基本思想：令二叉樹的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，鏈表結(jié)點(diǎn)除了存放與二叉樹結(jié)點(diǎn)有關(guān)的數(shù)據(jù)信息外，還要設(shè)置指示左右孩子的指針。

結(jié)點(diǎn)結(jié)構(gòu)：

lchild

data

rchild其中，data：數(shù)據(jù)域，存放該結(jié)點(diǎn)的數(shù)據(jù)信息；lchild：左指針域，存放指向左孩子的指針；rchild：右指針域，存放指向右孩子的指針。

5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)template<classDataType>structBiNode{DataTypedata;BiNode<T>*lchild,*rchild;};5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)lchild

datarchild左孩子結(jié)點(diǎn)右孩子結(jié)點(diǎn)二叉鏈表GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有多少個(gè)空指針？GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針。template<classDataType>classBiTree{public:BiTree(){root=Creat(root);}//構(gòu)造函數(shù)，建立一棵二叉樹

~BiTree(){Release(root);}//析構(gòu)函數(shù)

voidPreOrder(){PreOrder(root);}//前序遍歷二叉樹

voidInOrder(){InOrder(root);}//中序遍歷二叉樹

voidPostOrder(){PostOrder(root);}//后序遍歷二叉樹

voidLeverOrder();//層序遍歷二叉樹private:BiNode<DataType>*root;//指向根結(jié)點(diǎn)的頭指針

BiNode<DataType>*Creat(BiNode<DataType>*bt);//構(gòu)造函數(shù)調(diào)用

voidRelease(BiNode<DataType>*bt);//析構(gòu)函數(shù)調(diào)用voidPreOrder(BiNode<DataType>*bt);//前序遍歷函數(shù)調(diào)用

voidInOrder(BiNode<DataType>*bt);//中序遍歷函數(shù)調(diào)用

voidPostOrder(BiNode<DataType>*bt);//后序遍歷函數(shù)調(diào)用};5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷——遞歸算法template<classDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){if(bt==NULL)return;//遞歸調(diào)用的結(jié)束條件else{cout<<bt->data;//訪問根結(jié)點(diǎn)bt的數(shù)據(jù)域

PreOrder(bt->lchild);//前序遞歸遍歷bt的左子樹PreOrder(bt->rchild);//前序遞歸遍歷bt的右子樹}}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)前序遍歷——遞歸算法template<classDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){if(bt==NULL)return;else{cout<<bt->data;

PreOrder(bt->lchild);PreOrder(bt->rchild);

}}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG中序遍歷——遞歸算法

template<classDataType>voidBiTree<DataType>::InOrder(BiNode<DataType>*bt){if(bt==NULL)return;//遞歸調(diào)用的結(jié)束條件else{InOrder(bt->lchild);//中序遞歸遍歷bt的左子樹

cout<<bt->data;//訪問根結(jié)點(diǎn)bt的數(shù)據(jù)域InOrder(bt->rchild);//中序遞歸遍歷bt的右子樹}}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷——遞歸算法

template<classDataType>voidBiTree<DataType>::InOrder(BiNode<DataType>*bt){if(bt==NULL)return;else{InOrder(bt->lchild);

cout<<bt->data;InOrder(bt->rchild);}}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG后序遍歷——遞歸算法template<classDataType>voidBiTree<DataType>::PostOrder(BiNode<DataType>*bt){if(bt==NULL)return;//遞歸調(diào)用的結(jié)束條件else{PostOrder(bt->lchild);//后序遞歸遍歷bt的左子樹PostOrder(bt->rchild);//后序遞歸遍歷bt的右子樹cout<<bt->data;//訪問根結(jié)點(diǎn)bt的數(shù)據(jù)域}}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)后序遍歷——遞歸算法template<classDataType>voidBiTree<DataType>::PostOrder(BiNode<DataType>*bt){if(bt==NULL)return;else{PostOrder(bt->lchild);PostOrder(bt->rchild);cout<<bt->data;}}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG層序遍歷5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG遍歷序列：AABCBDCEFGDEFG層序遍歷隊(duì)列Q初始化；2.如果二叉樹非空，將根指針入隊(duì)；3.循環(huán)直到隊(duì)列Q為空3.1q=隊(duì)列Q的隊(duì)頭元素出隊(duì)；3.2訪問結(jié)點(diǎn)q的數(shù)據(jù)域；3.3若結(jié)點(diǎn)q存在左孩子，則將左孩子指針入隊(duì)；3.4若結(jié)點(diǎn)q存在右孩子，則將右孩子指針入隊(duì)；5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)層序遍歷template<classDataType>voidBiTree<DataType>::LeverOrder(){front=rear=-1;//采用順序隊(duì)列，并假定不會(huì)發(fā)生上溢if(root==NULL)return;//二叉樹為空，算法結(jié)束Q[++rear]=root;//根指針入隊(duì)while(front!=rear)//當(dāng)隊(duì)列非空時(shí){q=Q[++front];//出隊(duì)cout<<q->data;if(q->lchild!=NULL)Q[++rear]=q->lchild;if(q->rchild!=NULL)Q[++rear]=q->rchild;}}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)構(gòu)造函數(shù)——建立二叉樹為了建立一棵二叉樹，將二叉樹中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一特定值如“#”，以標(biāo)識(shí)其為空，把這樣處理后的二叉樹稱為原二叉樹的擴(kuò)展二叉樹。

為什么如此處理?5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何由一種遍歷序列生成該二叉樹？遍歷是二叉樹各種操作的基礎(chǔ)，可以在遍歷的過程中進(jìn)行各種操作，例如建立一棵二叉樹。擴(kuò)展二叉樹的前序遍歷序列:AB#D##C##5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)DBAC#DBAC####構(gòu)造函數(shù)——建立二叉樹設(shè)二叉樹中的結(jié)點(diǎn)均為一個(gè)字符。假設(shè)擴(kuò)展二叉樹的前序遍歷序列由鍵盤輸入，root為指向根結(jié)點(diǎn)的指針，二叉鏈表的建立過程是：首先輸入根結(jié)點(diǎn)，若輸入的是一個(gè)“#”字符，則表明該二叉樹為空樹，即root=NULL；否則輸入的字符應(yīng)該賦給root->data,，之后依次遞歸建立它的左子樹和右子樹。5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)構(gòu)造函數(shù)——建立二叉樹template<classDataType>BiTree::BiTree(){

root=Creat(root);

}template<classDataType>BiNode<DataType>*BiTree<DataType>::Creat(BiNode<DataType>*bt){cin>>ch;//輸入結(jié)點(diǎn)的數(shù)據(jù)信息，假設(shè)為字符if(ch=='#')bt=NULL;//建立一棵空樹else{bt=newBiNode;bt->data=ch;//生成一個(gè)結(jié)點(diǎn)，數(shù)據(jù)域?yàn)閏hbt->lchild=Creat(bt->lchild);//遞歸建立左子樹

bt->rchild=Creat(bt->rchild);//遞歸建立右子樹}returnbt;}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉樹算法設(shè)計(jì)練習(xí)

遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法中對(duì)每個(gè)結(jié)點(diǎn)的訪問操作可以是多種形式及多個(gè)操作，根據(jù)遍歷算法的框架，適當(dāng)修改訪問操作的內(nèi)容，可以派生出很多關(guān)于二叉樹的應(yīng)用算法。voidInOrder

(BiNode<T>*root){if(root==NULL)return;else{

InOrder(root->lchild);

cout<<root->data;

InOrder(root->rchild);}}二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹的結(jié)點(diǎn)個(gè)數(shù)。voidCount(BiNode*root)//count為全局量并已初始化為0{if(root==NULL)return;else{

Count(root->lchild);count++;

Count(root->rchild);}}二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法按前序次序打印二叉樹中的葉子結(jié)點(diǎn)。voidPreOrder(BiNode*root){if(root==NULL)return;else{

if(!root->lchild&&!root->rchild)cout<<root->data;PreOrder(root->lchild);PreOrder(root->rchild);}}二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求二叉樹的深度。

intDepth(BiNode*root){if(root==NULL)return0;else{hl=Depth(root->lchild);hr=Depth(root->rchild);returnmax(hl,hr)+1;}}二叉樹算法設(shè)計(jì)練習(xí)設(shè)計(jì)算法求樹中結(jié)點(diǎn)x的第i個(gè)孩子。

TNode*Search(TNode*root,DataTypex,inti){if(root->data==x){j=1;p=root->firstchild;while(p!=NULL&&j<i){j++;p=p->rightsib;}if(p!=NULL)returnp;elsereturnNULL;}

Search(root->firstchild,x,i);Search(root->rightsib,x,i);}AEBCFDGABCDEFG三叉鏈表5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)GFEDBAABCDEFG∧∧∧∧∧∧∧∧C在二叉鏈表中，如何求某結(jié)點(diǎn)的雙親？三叉鏈表

lchild

dataparentrchild在二叉鏈表的基礎(chǔ)上增加了一個(gè)指向雙親的指針域。結(jié)點(diǎn)結(jié)構(gòu)其中：data、lchild和rchild三個(gè)域的含義同二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)的雙親結(jié)點(diǎn)的指針。

5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFGA∧B∧D∧E∧F∧CG∧∧∧∧三叉鏈表5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)ABCDEFG三叉鏈表的靜態(tài)鏈表形式5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)0123456dataparentlchildrchildABCDEFG-1001223134-1-1-1-12-156-1-1-1線索鏈表5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：DGBAFCF如果二叉樹不改變，如何保存？順序存儲(chǔ)DGBAFCF線索鏈表5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：DGBAFCF如果二叉樹改變，如何保存？鏈接存儲(chǔ)DF

線索鏈表5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？ABCDEFG中序遍歷序列：DGBAFCF如何將二叉鏈表與中序鏈表結(jié)合？鏈接存儲(chǔ)DF

線索鏈表線索：將二叉鏈表中的空指針域指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針被稱為線索；線索化：使二叉鏈表中結(jié)點(diǎn)的空鏈域存放其前驅(qū)或后繼信息的過程稱為線索化；線索鏈表：加上線索的二叉鏈表稱為線索鏈表。5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)如何保存二叉樹的某種遍歷序列？將二叉鏈表中的空指針域指向其前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)

ltag

lchild

data

child

rtag0:lchild指向該結(jié)點(diǎn)的左孩子1:lchild指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)0:rchild指向該結(jié)點(diǎn)的右孩子1:rchild指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)ltag=rtag=5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)結(jié)點(diǎn)結(jié)構(gòu)線索鏈表enumflag{Child,Thread};template<classDataType>structThrNode{DataTypedata;ThrNode<DataType>*lchild,*rchild;

flagltag,rtag;};5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索鏈表

ltag

lchild

data

child

rtag結(jié)點(diǎn)結(jié)構(gòu)二叉樹的遍歷方式有4種，故有4種意義下的前驅(qū)和后繼，相應(yīng)的有4種線索二叉樹：⑴前序線索二叉樹⑵中序線索二叉樹⑶后序線索二叉樹⑷層序線索二叉樹5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索二叉樹FABDCEG中序線索二叉樹5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)線索二叉樹中序序列：DGBAECFtemplate<classDataType>classInThrBiTree{public:InThrBiTree();//構(gòu)造函數(shù)，建立中序線索鏈表

~InThrBiTree();//析構(gòu)函數(shù)，釋放各結(jié)點(diǎn)的存儲(chǔ)空間

ThrNode*Next(ThrNode<DataType>*p);//查找p的后繼

voidInOrder();//中序遍歷線索鏈表private:ThrNode*root;//指向線索鏈表的頭指針

ThrNode<DataType>*Creat(ThrNode<DataType>*bt);

voidThrBiTree(ThrNode<DataType>*bt,ThrNode<DataType>*pre);//構(gòu)造函數(shù)調(diào)用};5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序線索鏈表類的聲明分析：建立線索鏈表，實(shí)質(zhì)上就是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)或后繼的信息只有在遍歷該二叉樹時(shí)才能得到。5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)建立二叉鏈表遍歷二叉樹，將空指針改為線索中序線索鏈表的建立——構(gòu)造函數(shù)A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)已經(jīng)建立起二叉鏈表A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)p1A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧∧中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre1p1A頭指針BCDEFG∧∧∧∧∧∧00000000000000∧中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p1A頭指針BCDEFG∧∧∧∧∧∧00000000000000中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p11A頭指針BCDEFG∧∧∧∧∧00000000000000中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p111A頭指針BCDEFG∧∧∧∧00000000000000中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p1111A頭指針BCDEFG∧∧∧00000000000000中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre11p11111A頭指針BCDEFG∧∧00000000000000中序線索鏈表的建立過程5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序遍歷二叉鏈表p為正在訪問的結(jié)點(diǎn)pre為剛訪問的結(jié)點(diǎn)pre111111115.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序線索鏈表查找后繼FABDCEG⑴如果結(jié)點(diǎn)p的右標(biāo)志為1，則表明該結(jié)點(diǎn)的右指針是線索；⑵如果結(jié)點(diǎn)p的右標(biāo)志為0，則表明該結(jié)點(diǎn)有右孩子。根據(jù)中序遍歷的操作定義，它的后繼結(jié)點(diǎn)應(yīng)該是遍歷其右子樹時(shí)第一個(gè)訪問的結(jié)點(diǎn)，即右子樹中的最左下結(jié)點(diǎn)。template<classDataType>ThrNode<DataType>*InThrBiTree<DataType>::Next(ThrNode<DataType>*p){if(p->rtag==1)q=p->rchild;//右標(biāo)志為1，可直接得到后繼結(jié)點(diǎn)

else{q=p->rchild;//工作指針q指向結(jié)點(diǎn)p的右孩子

while(q->ltag==0)//查找最左下結(jié)點(diǎn)

q=q->lchild;}returnq;}5.4二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)中序線索鏈表查找后繼二叉樹前序遍歷的非遞歸算法的關(guān)鍵：在前序遍歷過某結(jié)點(diǎn)的整個(gè)左子樹后，如何找到該結(jié)點(diǎn)的右子樹的根指針。解決辦法：在訪問完該結(jié)點(diǎn)后，將該結(jié)點(diǎn)的指針保存在棧中，以便以后能通過它找到該結(jié)點(diǎn)的右子樹。

在前序遍歷中，設(shè)要遍歷二叉樹的根指針為root，則有兩種可能：⑴若root!=NULL，則表明？如何處理？⑵若root=NULL，則表明？如何處理？前序遍歷——非遞歸算法5.5二叉樹遍歷的非遞歸算法訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD

A

B前序遍歷的非遞歸實(shí)現(xiàn)

ADBC5.5二叉樹遍歷的非遞歸算法訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD

A前序遍歷的非遞歸實(shí)現(xiàn)

ADBC

D5.5二叉樹遍歷的非遞歸算法訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD

C前序遍歷的非遞歸實(shí)現(xiàn)

ADBCC5.5二叉樹遍歷的非遞歸算法1.棧s初始化；2.循環(huán)直到root為空且棧s為空

2.1當(dāng)root不空時(shí)循環(huán)

2.1.1輸出root->data;2.1.2將指針root的值保存到棧中；

2.1.3繼續(xù)遍歷root的左子樹

2.2如果棧s不空，則

2.2.1將棧頂元素彈出至root；

2.2.2準(zhǔn)備遍歷root的右子樹；前序遍歷——非遞歸算法（偽代碼）5.5二叉樹遍歷的非遞歸算法前序遍歷——非遞歸算法（偽代碼）template<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){top=-1;//采用順序棧，并假定不會(huì)發(fā)生上溢

while(root!=NULL||top!=-1){while(root!=NULL){cout<<root->data;//先訪問s[++top]=root;//再壓棧root=root->lchild;}if(top!=-1){root=s[top--];root=root->rchild;}

}}5.5二叉樹遍歷的非遞歸算法ADBC中序遍歷——非遞歸算法

在二叉樹的中序遍歷中，訪問結(jié)點(diǎn)的操作發(fā)生在該結(jié)點(diǎn)的左子樹遍歷完畢并準(zhǔn)備遍歷右子樹時(shí)，所以，在遍歷過程中遇到某結(jié)點(diǎn)時(shí)并不能立即訪問它，而是將它壓棧，等到它的左子樹遍歷完畢后，再從棧中彈出并訪問之。中序遍歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語句cout<<bt->data移到bt=s[top--]之后即可。

5.5二叉樹遍歷的非遞歸算法中序遍歷——非遞歸算法template<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){top=-1;//采用順序棧，并假定不會(huì)發(fā)生上溢

while(root!=NULL||top!=-1){while(root!=NULL){s[++top]=root;root=root->lchild;}if(top!=-1){

root=s[top--];

cout<<root->data;root=root->rchild;}}}5.5二叉樹遍歷的非遞歸算法ABCDEFG后序遍歷——非遞歸算法在后序遍歷過程中，結(jié)點(diǎn)要入兩次棧，出兩次棧：⑴第一次出棧：只遍歷完左子樹，該結(jié)點(diǎn)不出棧，利用棧頂結(jié)點(diǎn)找到它的右子樹，準(zhǔn)備遍歷它的右子樹；⑵第二次出棧：遍歷完右子樹，將該結(jié)點(diǎn)出棧，并訪問它。因此，為了區(qū)別同一個(gè)結(jié)點(diǎn)的兩次出棧，設(shè)置標(biāo)志flag。5.5二叉樹遍歷的非遞歸算法棧元素類型定義如下：template<classDataType>structelement{BiNode<DataType>*ptr;intflag;//1表示第1次出棧，2表示第2次出棧};后序遍歷——非遞歸算法設(shè)根指針為bt，則可能有以下兩種情況：⑴若bt不等于NULL