4-5二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)v第四章樹(shù)和二叉樹(shù)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉鏈表三叉鏈表學(xué)什么？4-5-1二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)v第四章樹(shù)和二叉樹(shù)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的要求是什么？用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，由存儲(chǔ)位置表示元素之間的邏輯關(guān)系如何利用數(shù)組下標(biāo)來(lái)反映結(jié)點(diǎn)之間的邏輯關(guān)系?完全二叉樹(shù)中結(jié)點(diǎn)的編號(hào)可以唯一地反映結(jié)點(diǎn)之間的邏輯關(guān)系二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)是用一維數(shù)組存儲(chǔ)二叉樹(shù)的結(jié)點(diǎn)，結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）應(yīng)能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系——父子關(guān)系A(chǔ)BCDEFHIJ編號(hào)為下標(biāo)

A12345678910

B

C

D

E

F

G

H

I

JconstMaxSize=100;template<typenameDataType>structSeqBiTree{

DataTypedata[MaxSize];intbiTreeNum;};如何定義二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)呢？二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如果從下標(biāo)0開(kāi)始存儲(chǔ)，如何表示邏輯關(guān)系？ABCDFEG152361310以編號(hào)為下標(biāo)

A12345678910111213

B

C∧

D

F∧

∧

∧

E

∧

∧

G將二叉樹(shù)按完全二叉樹(shù)編號(hào)：（1）根結(jié)點(diǎn)的編號(hào)為1（2）若某結(jié)點(diǎn)

i有左孩子，則其左孩子的編號(hào)為2i（3）若某結(jié)點(diǎn)

i有右孩子，則其右孩子的編號(hào)為2i+1對(duì)于普通的二叉樹(shù)，如何順序存儲(chǔ)呢？二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)一般僅存儲(chǔ)完全二叉樹(shù)順序存儲(chǔ)一棵右斜樹(shù)會(huì)發(fā)生什么情況？ACOG缺點(diǎn)：浪費(fèi)存儲(chǔ)空間二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)4-5-2二叉鏈表v第四章樹(shù)和二叉樹(shù)如何用鏈接存儲(chǔ)方式存儲(chǔ)二叉樹(shù)呢？firsta1a2an∧二叉鏈表：二叉樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)鏈表結(jié)點(diǎn)，存放結(jié)點(diǎn)的數(shù)據(jù)信息和指示左右孩子的指針二叉鏈表的存儲(chǔ)方法lchild

datarchildACBDEFGACBDEFGGFEDB∧∧∧∧∧∧∧∧CAroot二叉鏈表的存儲(chǔ)方法葉子結(jié)點(diǎn)的標(biāo)志？左右孩子指針均為空二叉鏈表的存儲(chǔ)結(jié)構(gòu)定義GFEDBA∧∧∧∧∧∧∧∧Ctemplate<typenameDataType>structBiNode{

DataTypedata;BiNode<DataType>*lchild,*rchild;};root如何定義二叉鏈表的結(jié)點(diǎn)呢？n個(gè)結(jié)點(diǎn)的二叉鏈表有多少個(gè)空指針？2n-(n-1)=n+1個(gè)空指針三叉鏈表的存儲(chǔ)方法GFEDBA∧∧∧∧∧∧∧∧C如何查找雙親？時(shí)間性能？O(n)在二叉鏈表中增加一個(gè)指向雙親的指針域

lchild

dataparentrchildrootA∧B∧D∧E∧F∧CG∧∧∧∧ACBDEFGroot三叉鏈表的存儲(chǔ)方法二叉鏈表的類定義二叉樹(shù)的抽象數(shù)據(jù)類型定義？template<typenameDataType>classBiTree{public:

BiTree(){root=CreateBiTree(root);}

~BiTree(){ReleaseBiTree(root);}

voidPreOrder(){PreOrder(root);}

voidInOrder(){InOrder(root);}

voidPostOrder(){PostOrder(root);}

voidLevelOrder();private:

BiNode<DataType>*CreateBiTree(BiNode<DataType>*bt);

voidReleaseBiTree(BiNode<DataType>*bt);

voidPreOrder(BiNode<DataType>*bt);

voidInOrder(BiNode<DataType>*bt);

voidPostOrder(BiNode<DataType>*bt);

BiNode<DataType>*root;};InitBiTree：初始化一棵空的二叉樹(shù)

CreateBiTree：建立一棵二叉樹(shù)

DestroyBiTree：銷毀一棵二叉樹(shù)PreOrder：前序遍歷二叉樹(shù)InOrder：中序遍歷二叉樹(shù)PostOrder：后序遍歷二叉樹(shù)LevelOrder：層序遍歷二叉樹(shù)先序遍歷算法template<typenameDataType>voidBiTree<DataType>::PreOrder(BiNode<DataType>*bt){

if(bt==nullptr)return;

//遞歸調(diào)用的結(jié)束條件

else{

cout<<bt->data;

//訪問(wèn)根結(jié)點(diǎn)bt的數(shù)據(jù)域

PreOrder(bt->lchild);

//先序遞歸遍歷bt的左子樹(shù)

PreOrder(bt->rchild);

//先序遞歸遍歷bt的右子樹(shù)

}}按照先左后右的方式掃描二叉樹(shù)，區(qū)別僅在于訪問(wèn)結(jié)點(diǎn)的時(shí)機(jī)LRACBDPre(*A)

（1）APre(A->lchild);

Pre(*B)

（2）BPre(B->lchild);

Pre(∧)Pre(*D)

（3）DPre(D->lchild);

Pre(∧)Pre(∧)Pre(B->rchild);Pre(D->rchild);約定：*A表示根指針指向結(jié)點(diǎn)Aif(bt==nullptr)return;else{

①

cout<<bt->data;

②

PreOrder(bt->lchild);

③

PreOrder(bt->rchild);}先序遍歷算法ACBDPre(*A)

（1）APre(A->lchild);

Pre(*B)

（2）BPre(B->lchild);

Pre(∧)Pre(*D)

（3）DPre(D->lchild);

Pre(∧)Pre(∧)Pre(B->rchild);Pre(D->rchild);Pre(∧)Pre(∧)Pre(*C)

（4）CPre(C->lchild);

Pre(A->rchild);Pre(C->rchild);得到先序遍歷序列：ABDCif(bt==nullptr)return;else{

①

cout<<bt->data;

②

PreOrder(bt->lchild);

③

PreOrder(bt->rchild);}先序遍歷算法遍歷序列：AABCBDCEFGDEFGACBDEFG隊(duì)列Q初始化；2.如果二叉樹(shù)非空，將根指針入隊(duì)；入隊(duì)出隊(duì)3.3若結(jié)點(diǎn)q存在左孩子，則將左孩子指針入隊(duì)；3.4若結(jié)點(diǎn)q存在右孩子，則將右孩子指針入隊(duì)；3.循環(huán)直到隊(duì)列Q為空3.1q=隊(duì)列Q的隊(duì)頭元素出隊(duì)；3.2訪問(wèn)結(jié)點(diǎn)q的數(shù)據(jù)域；

層序遍歷算法template<typenameDataType>voidBiTree<DataType>::LevelOrder(){

BiNode<DataType>*Q[100],*q=nullptr;

intfront=-1,rear=-1;

if(root==nullptr)return;

Q[++rear]=root;

while(front!=rear)

{

q=Q[++front];cout<<q->data;

if(q->lchild!=nullptr)Q[++rear]=q->lchild;

if(q->rchild!=nullptr)Q[++rear]=q->rchild;

}}時(shí)間復(fù)雜度？每個(gè)結(jié)點(diǎn)進(jìn)隊(duì)一次出隊(duì)一次O(n)O(n)層序遍歷算法遍歷是二叉樹(shù)各種操作的基礎(chǔ)，可以在遍歷的過(guò)程中建立一棵二叉鏈表在內(nèi)存中建立一棵二叉鏈表，如何輸入二叉樹(shù)的信息？構(gòu)造二叉鏈表如何由一種遍歷序列生成該二叉樹(shù)？擴(kuò)展二叉樹(shù)：將每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，其值為一特定值如'#'ACBD先序：AB#D##C##ACBD#####template<typename

DataType>BiNode<DataType>*BiTree<DataType>::CreateBiTree(BiNode<DataType>*bt){

charch;

cin>>ch;

//輸入結(jié)點(diǎn)的數(shù)據(jù)信息，假設(shè)為字符

if(ch==‘#’)bt=nullptr;

//建立一棵空樹(shù)

else{

bt=newBiNode<DataType>;

bt->data=ch;

bt->lchild

=CreateBiTree(bt->lchild);//遞歸建立左子樹(shù)

bt->rchild

=CreateBiTree(bt->rchild);//遞歸建立右子樹(shù)

}

returnbt;}構(gòu)造二叉鏈表銷毀二叉鏈表為什么要銷毀內(nèi)存中的二叉鏈表？二叉鏈表是動(dòng)態(tài)存儲(chǔ)分配，二叉鏈表的結(jié)點(diǎn)是在程序運(yùn)行過(guò)程中動(dòng)態(tài)申請(qǐng)的，在二叉鏈表變量退出作用域前，要釋放二叉鏈表的存儲(chǔ)空間template<typenameDataType>voidBiTree<DataType>::ReleaseBiTree(BiNode<