第5章樹和二叉樹

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

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

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

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

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

InitBiTree

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

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

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

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

InOrder

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

PostOrder

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

LeverOrder

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

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

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

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

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

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

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

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

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

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ù)前序序列的第一個元素建立根結(jié)點；2.在中序序列中找到該元素，確定根結(jié)點的左右子樹的中序序列；3.在前序序列中確定左右子樹的前序序列；4.由左子樹的前序序列和中序序列建立左子樹；5.由右子樹的前序序列和中序序列建立右子樹。5.3二叉樹的邏輯結(jié)構(gòu)已知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下：

二叉樹的遍歷操作

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

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

A

B

C

D

E

F

G

H

I

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

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

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

結(jié)點結(jié)構(gòu)：

lchild

data

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

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

datarchild左孩子結(jié)點右孩子結(jié)點二叉鏈表GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表5.4二叉樹的存儲結(jié)構(gòu)及實現(xiàn)具有n個結(jié)點的二叉鏈表中，有多少個空指針？GFEDBAABCDEFG∧∧∧∧∧∧∧∧C二叉鏈表5.4二叉樹的存儲結(jié)構(gòu)及實現(xiàn)具有n個結(jié)點的二叉鏈表中，有n+1個空指針。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é)點的頭指針

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

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

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

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

遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，遍歷算法中對每個結(jié)點的訪問操作可以是多種形式及多個操作，根據(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è)計練習(xí)設(shè)計算法求二叉樹的結(jié)點個數(shù)。voidCount(BiNode*root)//count為全局量并已初始化為0{if(root==NULL)return;else{

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

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

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

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

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二叉樹的存儲結(jié)構(gòu)及實現(xiàn)GFEDBAABCDEFG∧∧∧∧∧∧∧∧C在二叉鏈表中，如何求某結(jié)點的雙親？三叉鏈表

lchild

dataparentrchild在二叉鏈表的基礎(chǔ)上增加了一個指向雙親的指針域。結(jié)點結(jié)構(gòu)其中：data、lchild和rchild三個域的含義同二叉鏈表的結(jié)點結(jié)構(gòu)；parent域為指向該結(jié)點的雙親結(jié)點的指針。

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

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

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

ltag

lchild

data

child

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

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

ltag

lchild

data

child

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

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

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

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

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

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

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

A

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

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

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

ADBC

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

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

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

2.1當(dāng)root不空時循環(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準備遍歷root的右子樹；前序遍歷——非遞歸算法（偽代碼）5.5二叉樹遍歷的非遞歸算法前序遍歷——非遞歸算法（偽代碼）template<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){top=-1;//采用順序棧，并假定不會發(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é)點的操作發(fā)生在該結(jié)點的左子樹遍歷完畢并準備遍歷右子樹時，所以，在遍歷過程中遇到某結(jié)點時并不能立即訪問它，而是將它壓棧，等到它的左子樹遍歷完畢后，再從棧中彈出并訪問之。中序遍歷的非遞歸算法只需將前序遍歷的非遞歸算法中的輸出語句cout<<bt->data移到bt=s[top--]之后即可。

5.5二叉樹遍歷的非遞歸算法中序遍歷——非遞歸算法template<classDataType>voidBiTree::PreOrder(BiNode<DataType>*root){top=-1;//采用順序棧，并假定不會發(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é)點要入兩次棧，出兩次棧：⑴第一次出棧：只遍歷完左子樹，該結(jié)點不出棧，利用棧頂結(jié)點找到它的右子樹，準備遍歷它的右子樹；⑵第二次出棧：遍歷完右子樹，將該結(jié)點出棧，并訪問它。因此，為了區(qū)別同一個結(jié)點的兩次出棧，設(shè)置標志flag。5.5二叉樹遍歷的非遞歸算法棧元素類型定義如下：template<classDataType>structelement{BiNode<DataType>*ptr;intflag;//1表示第1次出棧，2表示第2次出棧};后序遍歷——非遞歸算法設(shè)根指針為bt，則可能有以下兩種情況：⑴若bt不等于NULL