第6講 樹和二叉樹(二叉樹的遍歷)(完成)

數(shù)據(jù)結(jié)構(gòu)與算法設計任課教師：劉晉萍Email：785297343@QQ:

785297343第六講樹和二叉樹樹的基本概念樹的定義樹的基本術(shù)語二叉樹二叉樹的定義二叉樹的性質(zhì)二叉樹的基本操作二叉樹的存儲結(jié)構(gòu)二叉樹的遍歷樹與二叉樹樹與二叉樹的轉(zhuǎn)換樹的遍歷二叉樹的遍歷二叉樹的遍歷二叉樹遍歷的概念二叉樹的遍歷二叉樹遍歷的概念二叉樹遍歷的方法二叉樹的遍歷二叉樹遍歷的概念二叉樹遍歷的方法二叉樹遍歷的應用二叉樹的遍歷二叉樹遍歷的概念二叉樹遍歷的方法二叉樹遍歷的應用二叉樹遍歷的實現(xiàn)算法結(jié)束二叉樹遍歷的概念遍歷的含義訪問結(jié)構(gòu)中的所有元素且只訪問一次二叉樹遍歷的定義按一定規(guī)律對二叉樹中每個結(jié)點訪問且僅訪問一次二叉樹遍歷的目的在對二叉樹的很多處理中，需要二叉樹結(jié)點的一個線性序列實質(zhì)而言，遍歷的目的就是對二叉樹進行線性化處理，以得到一個結(jié)點的線性序列對二叉樹處理而言，遍歷的目的是為二叉樹的其他運算奠定基礎非線性結(jié)構(gòu)遍歷結(jié)點的訪問序列線性化回去二叉樹遍歷的方法有哪些方法二叉樹由三個基本部分組成：根結(jié)點

左子樹

右子樹遍歷二叉樹實質(zhì)就是完成如下三項工作：訪問根結(jié)點D遍歷左子樹L遍歷右子樹R這三項工作按順序組合可以得到6種遍歷方案：DLRDRLLDRRDLLRDRLD對這6種方案加上“先左后右”的限定，則得到如下3種遍歷方案：DLR稱為先（根）序遍歷LDR稱為中（根）序遍歷LRD稱為后（根）序遍歷遍歷方法的描述根左子樹右子樹看圖路徑DLRDRLLDRRDLLRDRLDDLRDRLLDRRDLLRDRLDDLR

DRLLDRRDLLRDRLDDLR

DRL

LDR

RDL

LRD

RLD訪問根結(jié)點、遍歷左子樹、遍歷右子樹訪問根結(jié)點、遍歷右子樹、遍歷左子樹遍歷左子樹、訪問根結(jié)點、遍歷右子樹遍歷右子樹、訪問根結(jié)點、遍歷左子樹遍歷左子樹、遍歷右子樹、訪問根結(jié)點遍歷右子樹、遍歷左子樹、訪問根結(jié)點回去二叉樹遍歷的方法有哪些方法二叉樹由三個基本部分組成：根結(jié)點

左子樹

右子樹遍歷二叉樹實質(zhì)就是完成如下三項工作：訪問根結(jié)點D遍歷左子樹L遍歷右子樹R這三項工作按順序組合可以得到6種遍歷方案：DLRDRLLDRRDLLRDRLD對這6種方案加上“先左后右”的限定，則得到如下3種遍歷方案：DLR稱為先（根）序遍歷LDR稱為中（根）序遍歷LRD稱為后（根）序遍歷遍歷方法的描述根左子樹右子樹看圖三種遍歷方案的遍歷路徑一樣，只是訪問根結(jié)點的時機不同二叉樹遍歷的方法有哪些方法遍歷方法的描述先序遍歷二叉樹若二叉樹為空，則空操作；否則

(1)訪問根結(jié)點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。中序遍歷二叉樹若二叉樹為空，則空操作；否則

(1)中序遍歷左子樹；

(2)訪問根結(jié)點；

(3)中序遍歷右子樹。后序遍歷二叉樹若二叉樹為空，則空操作；否則

(1)后序遍歷左子樹；

(2)后序遍歷右子樹;(3)訪問根結(jié)點。根左子樹右子樹看例先序序列中序序列后序序列（根、左、右）（左、根、右）（左、右、根）二叉樹遍歷方法例1先序序列中序序列后序序列ABCDEFGHK待遍歷的二叉樹根右子樹左子樹ABCEFGDHK回去CDBAEHGKFDCBHKGFEA二叉樹遍歷的應用輸出二叉樹中的所有結(jié)點輸出二叉樹中的葉子結(jié)點求二叉樹的深度對每一個應用問題：確定“訪問”的具體操作是什么分析對遍歷順序的要求，確定用先序遍歷、中序遍歷還是后序遍歷給出解決問題的算法描述思考練習：用何種遍歷實現(xiàn)對二叉樹左右子樹的交換？在交換二叉樹左右子樹的遍歷中，“訪問”操作是什么？寫出一個實現(xiàn)二叉樹左右子樹交換的算法描述?；厝ハ刃虮闅v二叉樹若二叉樹為空，則空操作；

否則，依次做如下操作：

(1)訪問根結(jié)點；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。輸出二叉樹中的所有結(jié)點分析：該問題需要對二叉樹進行遍歷，即：對所有結(jié)點進行“訪問”，且只訪問一次這里的“訪問”就是“結(jié)點的輸出”“訪問”順序的確定只要能對所有結(jié)點進行輸出，沒有結(jié)點輸出順序的要求，因此，按先序、中序和后序都可以這里以先序為例算法描述（基于先序遍歷）若二叉樹為空，則空操作；否則，依次做如下操作：

(1)輸出根結(jié)點；

(2)輸出左子樹中的所有結(jié)點；

(3)輸出右子樹中的所有結(jié)點。思考：若基于中序遍歷或基于后序遍歷，則該問題的算法應該是怎樣的？看例子回去基于中序遍歷基于后序遍歷輸出二叉樹中的所有結(jié)點算法描述（基于中序遍歷）若二叉樹為空，則空操作；否則，依次做如下操作：

(1)輸出左子樹中的所有結(jié)點；

(2)輸出根結(jié)點；

(3)輸出右子樹中的所有結(jié)點。中序遍歷二叉樹若二叉樹為空，則空操作；

否則，依次做如下操作：

(1)中序遍歷左子樹；

(2)訪問根結(jié)點；

(3)中序遍歷右子樹?；厝ポ敵龆鏄渲械乃薪Y(jié)點算法描述（基于后序遍歷）若二叉樹為空，則空操作；否則，依次做如下操作：

(1)輸出左子樹中的所有結(jié)點；

(2)輸出右子樹中的所有結(jié)點；

(3)輸出根結(jié)點。后序遍歷二叉樹若二叉樹為空，則空操作；

否則，依次做如下操作：

(1)后序遍歷左子樹；

(2)后序遍歷右子樹；

(3)訪問根結(jié)點?；厝ポ敵龆鏄渲械乃薪Y(jié)點例ABCEFGDHK待輸出的二叉樹基于先序遍歷結(jié)點的輸出序列：ABCDEFGHK基于中序遍歷結(jié)點的輸出序列：基于后序遍歷結(jié)點的輸出序列：CDBAEHGKFDCBHKGFEA回去輸出二叉樹中的葉子結(jié)點分析：該問題需要對二叉樹中所有結(jié)點進行“訪問”，且只訪問一次這里的“訪問”是“帶判斷的輸出”，也就是：“是葉子結(jié)點就輸出”“訪問”順序的確定只要能對所有葉子結(jié)點進行輸出，沒有結(jié)點輸出順序的要求，因此，按先序、中序和后序都可以算法描述若二叉樹為空，則空操作；否則，依次做如下操作：（1）如果根結(jié)點既沒有左孩子也沒有右孩子，則輸出根結(jié)點（2）輸出左子樹中的葉子結(jié)點（3）輸出右子樹中的葉子結(jié)點算法描述（基于中序遍歷）算法描述（基于后序遍歷）（基于先序遍歷）思考：該算法是基于先序的？中序的？還是后序的？看例子（1）如果根結(jié)點是葉子結(jié)點，則輸出根結(jié)點?；厝ポ敵龆鏄渲械娜~子結(jié)點分析：該問題需要對二叉樹中所有結(jié)點進行“訪問”，且只訪問一次這里的“訪問”是“判斷+輸出”，也就是：“是葉子結(jié)點就輸出”需要按某種順序進行“訪問”只要能對所有葉子結(jié)點進行輸出，沒有結(jié)點輸出順序的要求，因此，按先序、中序和后序都可以算法描述若二叉樹為空，則空操作；否則，依次做如下操作：（1）如果當前二叉樹的根既沒有左孩子也沒有右孩子，則輸出根結(jié)點（2）輸出左子樹中的葉子結(jié)點（3）輸出右子樹中的葉子結(jié)點算法描述（基于中序遍歷）算法描述（基于后序遍歷）（基于先序遍歷）看例子輸出二叉樹中的葉子結(jié)點分析：該問題需要對二叉樹中所有結(jié)點進行“訪問”，且只訪問一次這里的“訪問”是“判斷+輸出”，也就是：“是葉子結(jié)點就輸出”需要按某種順序進行“訪問”只要能對所有葉子結(jié)點進行輸出，沒有結(jié)點輸出順序的要求，因此，按先序、中序和后序都可以算法描述算法描述（基于中序遍歷）若二叉樹為空，則空操作；否則，依次做如下操作：（1）輸出左子樹中的葉子結(jié)點（2）如果當前二叉樹的根既沒有左孩子也沒有右孩子，則輸出根結(jié)點（3）輸出右子樹中的葉子結(jié)點算法描述（基于后序遍歷）（基于先序遍歷）看例子輸出二叉樹中的葉子結(jié)點分析：該問題需要對二叉樹中所有結(jié)點進行“訪問”，且只訪問一次這里的“訪問”是“判斷+輸出”，也就是：“是葉子結(jié)點就輸出”需要按某種順序進行“訪問”只要能對所有葉子結(jié)點進行輸出，沒有結(jié)點輸出順序的要求，因此，按先序、中序和后序都可以算法描述算法描述（基于中序遍歷）算法描述（基于后序遍歷）若二叉樹為空，則空操作；否則，依次做如下操作：（1）輸出左子樹中的葉子結(jié)點（2）輸出右子樹中的葉子結(jié)點（3）如果當前二叉樹的根既沒有左孩子也沒有右孩子，則輸出根結(jié)點（基于先序遍歷）看例子輸出二叉樹中的葉子結(jié)點例ABCEFGDHK待輸出的二叉樹基于先序遍歷葉子結(jié)點的輸出序列：DHKDHKDHK基于后序遍歷葉子結(jié)點的輸出序列：基于中序遍歷葉子結(jié)點的輸出序列：思考：輸出二叉樹葉子結(jié)點的算法，不論基于先序、中序和后序，葉子結(jié)點的輸出順序都一樣嗎？為什么？回去求二叉樹的深度二叉樹深度的定義：結(jié)點的最大層次數(shù)MAX{左子樹的深度，右子樹的深度}+1求二叉樹深度的算法描述：若二叉樹為空，則返回0；否則，依次做如下操作：求左子樹的深度lh求右子樹的深度rh返回max{lh，rh}+1思考：基于什么遍歷順序后序遍歷這里，對結(jié)點訪問的操作是什么求以該結(jié)點為根的二叉樹的深度根左子樹右子樹lhrh二叉樹的深度？二叉樹的深度=MAX{lh，rh}+1看例子回去思考：根據(jù)”二叉樹的深度=MAX{lh，rh}+1“這個定義，求二叉樹深度能否按先序或中序進行？為什么？求二叉樹的深度例求二叉樹深度的算法描述：若二叉樹為空，則返回0；否則，依次做如下操作：求左子樹的深度lh求右子樹的深度rh返回max{lh，rh}+1ABCEFGDHK0120003000000112345回去思考與練習交換二叉樹的左右子樹用何種遍歷實現(xiàn)對二叉樹左右子樹的交換？在交換二叉樹左右子樹的遍歷中，”訪問“操作是什么？寫出一個實現(xiàn)二叉樹左右子樹交換的算法描述根據(jù)：二叉樹的深度=MAX{lh，rh}+1

這個定義，求二叉樹深度能否按先序或中序進行？為什么？輸出二叉樹葉子結(jié)點的算法，不論基于先序、中序和后序，葉子結(jié)點的輸出順序都一樣嗎？為什么？二叉樹遍歷的實現(xiàn)算法先序遍歷的遞歸實現(xiàn)算法中序遍歷的遞歸實現(xiàn)算法后序遍歷的遞歸實現(xiàn)算法解決應用問題的實現(xiàn)算法返回P7先序遍歷的遞歸實現(xiàn)算法先序遍歷以root為根的二叉樹void

PreOrder(BiTree

root){

if(root!=NULL)

{

Visit(root->data);

/*訪問根結(jié)點*/

PreOrder(root->lchild);

/*先序遍歷左子樹*/

PreOrder(root->rchild);

/*先序遍歷右子樹*/

}}返回P26中序遍歷的遞歸實現(xiàn)算法中序遍歷以root為根的二叉樹void

InOrder(BiTree

root)

{

if(root!=NULL)

{

InOrder(root->lchild);

/*中序遍歷左子樹*/

Visit(root->data);

/*訪問根結(jié)點*/

InOrder(root->rchild);

/*中序遍歷右子樹*/

}}返回P26后序遍歷的遞歸實現(xiàn)算法后序遍歷以root為根的二叉樹void

PostOrder(BiTree

root)

{

if(root!=NULL)

{

PostOrder(root->lchild);/*后序遍歷左子樹*/

PostOrder(root->rchild);/*后序遍歷右子樹*

Visit(root->data);

/*訪問根結(jié)點*/

}}返回P26解決應用問題的實現(xiàn)算法輸出二叉樹中結(jié)點的實現(xiàn)算法輸出二叉樹中葉子結(jié)點的實現(xiàn)算法求二叉樹深度的實現(xiàn)算法二叉樹的創(chuàng)建算法算法閱讀返回P26輸出二叉樹中結(jié)點的實現(xiàn)算法輸出以root為根的二叉樹中的結(jié)點?；谙刃虮闅v的實現(xiàn)算法void

OutBiTree(BiTree

root){

if(root!=NULL)

{

printf(root->data);

/*輸出根結(jié)點*/

OutBiTree(root->lchild);

/*輸出左子樹中的結(jié)點*/

OutBiTree(root->rchild);

/*輸出右子樹中的結(jié)點*/

}}返回P30輸出二叉樹中葉子結(jié)點的實現(xiàn)算法輸出以root為根的二叉樹中葉子結(jié)點基于先序遍歷的實現(xiàn)算法void

OutLeaf(BiTree

root){

if(root!=NULL)

{

if(root->lchild==NULL&&root->rchild==NULL)

printf(root->data);

/*輸出葉子結(jié)點*/

OutLeaf(root->lchild);

/*輸出左子樹中的葉子結(jié)點*/

OutLeaf(root->rchild);

/*輸出右子樹中的葉子結(jié)點*/

}}返回P30求二叉樹深度的實現(xiàn)算法求以root為根的二叉樹的深度int

BiTreeDepth(BiTree

root)

{

if(root!=NULL)

{

hl=BiTreeDepth(root->lchild);

/*求左子樹的深度*/

hr=BiTreeDepth(root->rchild);

/*求右子樹的深度*/max=hl>hr?hl:hr;

/*得到左、右子樹深度較大者*/return(max+1);

/*返回樹的深度*/

}

elsereturn(0);

/*如果是空樹，則返回0*/}返回P30關(guān)于二叉樹的創(chuàng)建給定一棵二叉樹，可以得到它的遍歷序列反之，給定一棵二叉樹的遍歷序列，也可以畫出該二叉樹能畫出就意味著能創(chuàng)建二叉樹已知二叉樹的“擴展的遍歷序列，畫出該二叉樹在二叉樹的遍歷序列中，用特定的元素表示空子樹，就得到相應的擴展遍歷序列例如，下圖

中二叉樹的“擴展先序遍歷序列”為：AB.DF..G..C.E.H..（這里以‘.’表示空子樹）繼續(xù)關(guān)于二叉樹的創(chuàng)建畫出擴展先序序列為：ACF.GK..H…B.FE…

的二叉樹將此過程作為創(chuàng)建二叉樹的過程,即:創(chuàng)建二叉鏈表的過程則對應此過程的實現(xiàn)算法見：“利用‘擴展先序遍歷序列‘創(chuàng)建二叉鏈表的算法”ACFBFGEKH繼續(xù)利用“擴展先序遍歷序列”創(chuàng)建二叉鏈表的算法voidCreateBiTree(BiTree

&root){

ch=getchar();

if(ch=='.')root=NULL;

else{root=(BiTree)malloc(sizeof(BiTNode));

root->data=ch;

CreateBiTree(root->lchild);

CreateBiTree(root->rchild);

}}繼續(xù)ABFECFGKHrootACF.GK..H…B.FE…關(guān)于二叉樹的創(chuàng)建已知某二叉樹的先序序列和中序序列如下：先序序列：ABDGCEHF

中序序列：BGDAEHCF

畫出該二叉樹，并寫出其后序序列。ABDGCEFH后序序列：GDBHEFCA由先序序列確定根是A由中序序列確定：（1）A有左、右子樹；（2）左子樹中的結(jié)點有BDG；右子樹中的結(jié)點有CEFH再由先序序列確定左子樹的結(jié)點BDG中B是根由中序序列確定B沒有左子樹，但有右子樹，其中右子樹中的結(jié)點有DG依此類推，直到A的左子樹的結(jié)構(gòu)確定。用同樣的方法分析右子樹的結(jié)構(gòu)。繼續(xù)關(guān)于二叉樹的創(chuàng)建已知某二叉樹的中序序列和后序序列如下：中序序列：EGHCFAD

后序序列：EGCADFH

畫出該二叉樹，并寫出其先序序列。由后序序列確定根是H由中序序列確定：（1）H有左、右子樹；（2）左子樹中的結(jié)點有GE；右子樹中的結(jié)點有FDCA再由后序序列確定左子樹的結(jié)點GE中G是根，由中序序列確定G有左子樹，但沒有右子樹，其中左子樹中的結(jié)點有E。用同樣的方法分析右子樹的結(jié)構(gòu)：根：F且F有左子樹，也有右子樹。左子樹有結(jié)點：C右子樹有結(jié)點：DA……先序序列：HGEFCDAHGFEDCA繼續(xù)關(guān)于二叉樹的創(chuàng)建思考：利用二叉樹的先序和中序或者中序和后序，創(chuàng)建該二叉樹對應的二叉鏈表的過程，給出算法