數(shù)據(jù)結(jié)構(gòu)與算法實踐指導(dǎo) 課件 5-二叉樹

第5章

二叉樹主講教師：張彬連吉首大學(xué)5.1知識簡介

二叉樹（BinaryTree）是n（n≥0）個結(jié)點所構(gòu)成的集合，它或為空樹（n

=

0）；或為非空樹，對于非空樹T：

（1）有且僅有一個稱之為根的結(jié)點；

（2）除根結(jié)點以外的其余結(jié)點分為兩個互不相交的子集T1和T2，分別稱為T的左子樹和右子樹，且T1和T2本身又都是二叉樹。

簡單講，二叉樹就是度不超過2的有序樹。由于二叉樹的結(jié)構(gòu)簡單，規(guī)律性強，且所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹。為不失一般性，一般將普通樹（多叉樹）轉(zhuǎn)化為二叉樹來實現(xiàn)。5.1.1二叉樹的結(jié)構(gòu)與基本性質(zhì)5.1知識簡介

5.1.1二叉樹的結(jié)構(gòu)與基本性質(zhì)二叉樹具有以下基本性質(zhì)：5.1知識簡介二叉樹具有以下基本性質(zhì)：5.1.1二叉樹的結(jié)構(gòu)與基本性質(zhì)

5.1知識簡介

二叉樹可以采用順序存儲和鏈?zhǔn)酱鎯煞N方式。5.1.2順序存儲

二叉樹的順序存儲使用一組地址連續(xù)的存儲單元來存儲二叉樹中的數(shù)據(jù)元素。將二叉樹的各個結(jié)點按完全二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素。利用編號之間的關(guān)系來描述雙親與左孩子、右孩子之間的關(guān)系（即二叉樹的性質(zhì)5）。如編號為i的結(jié)點，如果i不等于1，則該結(jié)點不是根結(jié)點，有雙親，雙親的編號為i/2。如果編號為2i的結(jié)點存在，則編號為2i的結(jié)點為編號為i的結(jié)點的左孩子。如果編號為2i+1的結(jié)點存在，則編號為2i+1的結(jié)點為編號為i的結(jié)點的左孩子。

5.1知識簡介二叉樹的順序存儲定義如下：5.1.2順序存儲#defineMAXTSZIE100//最大結(jié)點數(shù)typedefTElemTypeSqBiTree[MAXTSIZE];SqBiTreebt;

在順序存儲中，結(jié)點間關(guān)系蘊含在其存儲位置中，尋找結(jié)點的雙親和孩子結(jié)點都非常方便。但對于普通的二叉樹而言，順序存儲浪費空間，也不利于節(jié)點的插入和刪除。順序存儲適于存儲完全二叉樹。5.1知識簡介5.1.3鏈?zhǔn)酱鎯?/p>

二叉樹的鏈?zhǔn)酱鎯τ址譃槎骀湵砗腿骀湵淼姆绞健?/p>

二叉鏈表存儲方式是每個結(jié)點不僅要存儲數(shù)據(jù)元素的值，還需存儲該結(jié)點左右孩子的地址。因此，每個結(jié)點包括三個部分：數(shù)據(jù)域（data）、指向左孩子指針（lchild）、指向右孩子指針（rchild）。鏈表的頭指針指向二叉樹的根結(jié)點。5.1知識簡介5.1.3鏈?zhǔn)酱鎯ο聢D左邊是一棵二叉樹，該二叉樹的二叉鏈表如右圖所示。5.1知識簡介5.1.3鏈?zhǔn)酱鎯Χ鏄涞亩骀湵泶鎯Y(jié)構(gòu)描述如下：typedefstructBiTNode{TElemTypedata;//數(shù)據(jù)域structBiTNode*lchild,*rchild;//分別指向左右孩子的指針}BiTNode,*BiTree;

三叉鏈表是在二叉鏈表的基礎(chǔ)上加一個指向雙親的指針（parent）。

鏈?zhǔn)酱鎯ο鄬樞虼鎯?jié)省存儲空間，插入刪除結(jié)點時只需修改指針。但尋找指定節(jié)點時很不方便。普通的二叉樹一般用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲。5.1知識簡介5.1.4二叉樹的遍歷方式

二叉樹的遍歷方式主要有四種，包括先序遍歷、中序遍歷、后序遍歷和層序遍歷。

先序遍歷（Pre-orderTraversal）：先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹。先序遍歷結(jié)果為：ABDEFHGC5.1知識簡介5.1.4二叉樹的遍歷方式

中序遍歷（In-orderTraversal）：先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。中序遍歷結(jié)果為：DBFHEGAC5.1知識簡介5.1.4二叉樹的遍歷方式

后序遍歷（Post-orderTraversal）：先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。后序遍歷結(jié)果為：

DHFGEBCA5.1知識簡介5.1.4二叉樹的遍歷方式

層序遍歷（Level-orderTraversal）：從上到下逐層遍歷，在同一層中按照從左到右的順序遍歷。層序遍歷結(jié)果為：

ABCDEFGH5.2實驗?zāi)康?/p>

通過本章的實驗，加深對二叉樹的定義、性質(zhì)、二叉鏈表存儲方式以及遍歷操作等知識的理解，培養(yǎng)學(xué)生用樹結(jié)構(gòu)解決實際問題的能力，同時鍛煉學(xué)生實際編程和算法設(shè)計的能力。5.3實驗范例

采用二叉鏈表存儲結(jié)構(gòu)建立一棵二叉樹。要求：假設(shè)二叉樹的數(shù)據(jù)元素是字符，根據(jù)輸入的一棵二叉樹的擴展先序遍歷序列建立一棵以二叉鏈表表示的二叉樹。5.3.1范例15.3實驗范例

所謂二叉樹的擴展是指用一個特殊的符號（如用‘#’）表示空樹。如下圖所示的二叉樹對應(yīng)的擴展二叉樹如右圖所示。5.3.1范例1擴展二叉樹的先序遍歷序列為：AB#D##C##。5.3實驗范例1、問題分析5.3.1范例1

要求利用擴展二叉樹的先序遍歷序列建立二叉樹。先分析序列AB#D##C##，因為它是先序遍歷的結(jié)果，所以該序列是按根、左子樹、右子樹的順序得到的。因此，按該序列創(chuàng)建二叉樹的時候也可以先創(chuàng)建根、然后創(chuàng)建左子樹，再創(chuàng)建右子樹。標(biāo)#號的結(jié)點類似于指向NULL的指針，因此#表示的是一棵空樹。5.3實驗范例1、問題分析5.3.1范例1

根據(jù)以上分析，創(chuàng)建二叉樹的算法步驟如下：

（1）輸入的字符ch。

（2）如果ch為’#’，則返回空。

（3）如果ch不為’#’，則生成結(jié)點，將字符存入結(jié)點的數(shù)據(jù)域，然后遞歸建立左子樹，再遞歸建立右子樹。5.3實驗范例2、算法描述5.3.1范例1先定義二叉樹結(jié)構(gòu)：typedefcharTElemType;typedefstructBiTNode{TElemTypedata;//結(jié)點數(shù)據(jù)structBiTNode*lchild;//左孩子structBiTNode*rchild;//右孩子}BiTNode,*BiTree;5.3實驗范例2、算法描述5.3.1范例1

在二叉樹被創(chuàng)建之后，應(yīng)該把根結(jié)點的地址返回給主調(diào)函數(shù)。建立二叉樹的函數(shù)CreateBiTree()可如下定義：BiTreeCreateBiTree(){

BiTreeroot;charch;//存儲結(jié)點的值scanf("%c",&ch);

if(ch=='#')root=NULL;//輸入的是‘#’else{root=(BiTNode*)malloc(sizeof(BiTNode));//生成新的結(jié)點root->data=ch;//將輸入的字符存入結(jié)點root->lchild=CreateBiTree();//遞歸建立左子樹root->rchild=CreateBiTree();//遞歸建立右子樹}returnroot;}5.3實驗范例3、算法分析5.3.1范例1

創(chuàng)建二叉樹的時間復(fù)雜度為O(n)，其中n為輸入序列的長度。5.3實驗范例

實現(xiàn)二叉樹的先序、中序、后序遍歷遞歸算法。對二叉樹進(jìn)行先序、中序和后序遍歷操作，并輸出遍歷序列，觀察輸出的序列是否與邏輯上的序列一致。5.3.2范例25.3實驗范例1、問題分析5.3.2范例2

可以用遞歸的方法對二叉樹進(jìn)行遍歷，先序、中序、后序三種遍歷方式如下。

（1）先序遍歷：若二叉樹為空樹，則空操作；否則先訪問根結(jié)點，再先序遍歷左子樹，最后先序遍歷右子樹。

（2）中序遍歷：若二叉樹為空樹，則空操作；否則先中序遍歷左子樹，再訪問根結(jié)點，最后中序遍歷右子樹。

（3）后序遍歷：若二叉樹為空樹，則空操作；否則先后序遍歷左子樹，再后序遍歷右子樹，最后訪問根結(jié)點。5.3實驗范例2、算法描述5.3.2范例2

先序遍歷二叉樹T，遞歸函數(shù)如下：voidPreOrderTraverse(BiTreeT){if(T!=NULL){printf("%c",T->data);//訪問根結(jié)點PreOrderTraverse(T->lchild);//遞歸先序遍歷左子樹PreOrderTraverse(T->rchild);//遞歸先序遍歷右子樹}}5.3實驗范例2、算法描述5.3.2范例2

中序遍歷二叉樹T，遞歸函數(shù)如下：voidInOrderTraverse(BiTreeT){if(T!=NULL){InOrderTraverse(T->lchild);//遞歸中序遍歷左子樹printf("%c",T->data);//訪問根結(jié)點InOrderTraverse(T->rchild);//遞歸中序遍歷右子樹}}5.3實驗范例2、算法描述5.3.2范例2

后序遍歷二叉樹T，遞歸函數(shù)如下：voidPostOrderTraverse(BiTreeT){if(T!=NULL){PostOrderTraverse(T->lchild);//遞歸后序遍歷左子樹PostOrderTraverse(T->rchild);//遞歸后序遍歷右子樹printf("%c",T->data);//訪問根結(jié)點}}5.3實驗范例2、算法描述5.3.2范例2

在主函數(shù)main()中，先創(chuàng)建一棵二叉樹，然后進(jìn)行先序、中序、后序三種方式的遍歷。intmain()//主函數(shù){BiTreeT;printf("輸入擴展后的二叉樹的先序遍歷序列：");T=CreateBiTree();printf("先序遍歷序列為:");PreOrderTraverse(T);printf("\n");printf("中序遍歷序列為:");InOrderTraverse(T);

printf("\n");printf("后序遍歷序列為:");PostOrderTraverse(T);printf("\n");return0;}5.3實驗范例3、算法分析5.3.2范例2

二叉樹的三種遍歷算法的時間復(fù)雜度為O(n)。

5.3實驗范例

實現(xiàn)二叉樹先序遍歷的非遞歸操作。要求：設(shè)計一個函數(shù)，用非遞歸的方法實現(xiàn)二叉樹的先序遍歷。5.3.3范例35.3實驗范例1、問題分析5.3.3范例3

二叉樹先序遍歷的非遞歸過程需要用棧來輔助實現(xiàn)。如下圖所示的二叉樹，先序遍歷時應(yīng)該從根結(jié)點A開始，然后訪問它的左子樹，再訪問它的右子樹。5.3實驗范例1、問題分析5.3.3范例3

首先訪問根結(jié)點A，并將A入棧。接著訪問A的左子樹。在訪問A的左子樹時，首先訪問左子樹的根結(jié)點B，并將B入棧，然后再訪問B的左子樹。先訪問B的左子樹的根結(jié)點D，并將結(jié)點D結(jié)點入棧。接著應(yīng)訪問D的左子樹，由于D的左子樹為空，此時棧中的數(shù)據(jù)如右圖所示。5.3實驗范例1、問題分析5.3.3范例3

棧頂為結(jié)點D，D不需要再訪問，應(yīng)該接著訪問D的右子樹。此時將棧頂?shù)慕Y(jié)點D出棧，找到D的右子樹。D的右子樹的根為E，訪問結(jié)點E，并將其入棧。接著訪問E的左子樹的根結(jié)點F，并將F入棧，由于F沒有左子樹，將F出棧，由于F沒有右子樹，以F為根結(jié)點的二叉樹訪問完。5.3實驗范例1、問題分析5.3.3范例3

將棧頂結(jié)點E出棧，找到E的右子樹，右子樹根結(jié)點為G，訪問G，同時入棧。由于G沒有左子樹，將G出棧，找到G的右子樹，G的右子樹為空，以G為根結(jié)點的二叉樹訪問完。5.3實驗范例1、問題分析5.3.3范例3

接著將棧頂元素B出棧，B的右子樹為空，則以B為根結(jié)點的二叉樹訪問完。接著將棧頂元素A出棧，找到A的右子樹。A的右子樹根結(jié)點為C，訪問C，并將C入棧。C沒有左子樹，將C出棧，然后訪問C的右子樹，C的右子樹也為空。最后棧為空，整個遍歷過程結(jié)束。5.3實驗范例1、問題分析5.3.3范例3

對上述案例的分析總結(jié)如下：

當(dāng)找到某個結(jié)點，訪問該結(jié)點并將其入棧。當(dāng)找某個結(jié)點的左子樹或者右子樹時，左子樹或右子樹為空，說明以某個結(jié)點為根結(jié)點的二叉樹訪問完，同時也就是棧頂結(jié)點的左子樹訪問完。接著將棧頂結(jié)點出棧，找到其右子樹。如果此時棧為空，說明二叉樹所有結(jié)點訪問完畢。5.3實驗范例2、算法描述5.3.3范例3根據(jù)前面的分析，先序遍歷的非遞歸過程描述如下：

①初始化一個空棧S，指針p指向根結(jié)點；

②當(dāng)p非空或者棧S非空時，循環(huán)執(zhí)行以下操作：

如果p非空，訪問p所指元素，并將p進(jìn)棧，p指向該結(jié)點的左孩子；

如果p為空，則棧頂元素出棧，將p指向該結(jié)點的右孩子。5.3實驗范例2、算法描述5.3.3范例3

先序遍歷二叉樹T的非遞歸函數(shù)定義如下：voidPreOrderTraverse_NoRecur(BiTreeT){//先序遍歷二叉樹T的非遞歸算法InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){//p非空cout<<p->data;//訪問根結(jié)點Push(S,p);//根指針進(jìn)棧p=p->lchild;//遍歷左子樹

}else{//p為空Pop(S,q);//棧頂出棧p=q->rchild;//遍歷右子樹}}}5.3實驗范例3、算法分析5.3.3范例3

由于每個結(jié)點只會被訪問一次，該算法的時間復(fù)雜度是O(n)，其中n是樹中結(jié)點的數(shù)量。

5.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)1：根據(jù)二叉樹的先序遍歷序列和中序遍歷序列建立二叉樹。要求：設(shè)計一個函數(shù)，根據(jù)兩個遍歷序列建立二叉樹。例如已知先序遍歷序列ABCDEFGH和中序遍歷序列BDCEAFHG，建立該二叉樹。任務(wù)2：實現(xiàn)二叉樹中序遍歷的非遞歸操作。要求：設(shè)計一個函數(shù)，用非遞歸方法實現(xiàn)對任務(wù)1建立的二叉樹進(jìn)行中序遍歷。5.4實驗任務(wù)完成下列任務(wù)，并分析各算法的時間復(fù)雜度。任務(wù)3：給定兩棵二叉樹，判斷兩棵二叉樹是否相等。假設(shè)T1和T2是兩棵二叉樹，如果兩棵二叉樹都是空樹；或者兩棵樹的根結(jié)點的值相等，并且根結(jié)點的左、右子樹分別也相等，則稱二叉樹T1與T2是相等的。要求設(shè)計一個函數(shù)判斷二叉樹T1和T2是否相等。任務(wù)4（選做）：編程求從二叉樹根結(jié)點到到指定結(jié)點p之間的路徑。要求：給出一棵二叉樹的根結(jié)點和任意給定的結(jié)點p，輸出從根結(jié)點到該結(jié)點p的路徑。5.5任務(wù)提示

先序遍歷是先訪問根結(jié)點，然后先序遍歷左子樹，再先序遍歷右子樹。根結(jié)點在最前面，根據(jù)先序遍歷序列可以找到根結(jié)點。中序遍歷是先中序遍歷左子樹，再訪問根結(jié)點，最后中序遍歷右子樹。利用先序遍歷序列找到根結(jié)點后，利用中序遍歷序列可以分出該棵二叉樹的左子樹和右子樹分別有哪些結(jié)點。左右子樹再用同樣的方法可以確定根結(jié)點以及根結(jié)點的左子樹和右子樹。任務(wù)1提示5.5任務(wù)提示例如：已知先序遍歷序列ABCDEFGH和中序遍歷序列BDCEAFHG，建立該二叉樹。任務(wù)1提示

由先序遍歷序列可知A是根結(jié)點，再由中序遍歷序列可知A的左子樹包括四個結(jié)點，且左子樹的中序遍歷序列為BDCE，先序遍歷序列為BCDE，A的右子樹包括3個結(jié)點，且右子樹的中序遍歷序列為FHG，先序遍歷序列為FGH。如下圖所示。5.5任務(wù)提示任務(wù)1提示

接著用同樣的方法建立A的左右子樹。A的左子樹中序遍歷序列BDCE，先序遍歷序列BCDE。先序遍歷序列中B是最前面，即B是根結(jié)點，即A的左孩子。中序遍歷序列中B是第一個，前面沒有元素，說明B沒有左子樹，右子樹由3個結(jié)點組成，分別是D、C、E，中序遍歷序列為DCE，先序遍歷序列為CDE。5.5任務(wù)提示任務(wù)1提示

接著建立B的右子樹，B的右子樹中序遍歷序列為DCE，先序遍歷序列為CDE。由先序遍歷序列可知，根結(jié)點為C，由中序遍歷序列可知，C有左子樹，左子樹一個結(jié)點D，即為C左孩子。C有右子樹，右子樹一個結(jié)點E，即為C的右孩子。此時A的左子樹建立完畢。接著建立A的右子樹。5.5任務(wù)提示任務(wù)1提示A的右子樹中序遍歷序列是FHG，先序遍歷序列是FGH。由先序遍歷序列可知F是根結(jié)點，由中序遍歷序列可知F沒有左子樹，右子樹有兩個結(jié)點，右子樹的中序遍歷序列為HG，先序遍歷序列為GH。5.5任務(wù)提示任務(wù)1提示F的右子樹中序遍歷序列為HG，先序遍歷序列為GH。由先序遍歷序列可知G是根結(jié)點，即G是F的右孩子。由中序遍歷序列可知，G有左子樹，左子樹只有結(jié)點H，H就是G左孩子，G沒有右孩子。二叉樹建立完畢。5.5任務(wù)提示任務(wù)1提示

建立過程中由先序遍歷序列可知根結(jié)點，再由中序遍歷序列可知根結(jié)點的左子樹結(jié)點和右子樹的結(jié)點。左子樹的建立和右子樹的建立可以用相同的方法建立，用遞歸來實現(xiàn)。5.5任務(wù)提示任務(wù)1提示

已知中序遍歷序列in[i1..i1+len-1]和先序遍歷序列pre[i2..i2+len-1]，有N個結(jié)點，遞歸建立二叉樹T過程如下：①如果序列長度len為0，T=NULL，否則：②生成根結(jié)點T，將pre的第一個元素存入T的數(shù)據(jù)域；③找到pre第一個元素在in中的位置m；④計算左子樹個數(shù)leftLen和右子樹的個數(shù)rightLen;⑤遞歸建立T的左子樹，中序遍歷序列為in[i1..m-1]，先序遍歷序列為pre[i2+1..i2+leftLen]，左子樹的結(jié)點個數(shù)為leftLen；⑥遞歸建立T的右子樹，中序遍歷序列為in[m+1..i1+len-1]，先序遍歷序列為pre[i2+leftLen+1..i2+len-1]，右子樹的結(jié)點個數(shù)為rigthLen。5.5任務(wù)提示算法的偽代碼描述如下：任務(wù)1提示typedefcharTElemType;typedefstructBiTNode{TElemTypedata;//數(shù)據(jù)域structBiTNode*lchild,*rchild;//分別指向左右孩子的指針}BiTNode,*BiTree;voidCreateTree(BiTree&T,char*in,inti1,char*pre,inti2,intlen){if(len<=0)T=NULL;//長度小于1，遞歸結(jié)束else{T=(BiTNode*)malloc(sizeof(BiTNode));//生成根結(jié)點T->data=pre[i2];//將先序序列中的第一個元素放入數(shù)據(jù)域5.5任務(wù)提示算法的偽代碼描述如下：任務(wù)1提示//找到先序序列第一個元素在中序序列中的位置mfor(m=i1;m<=i1+len;m++)if(pre[i2]==in[m])break;leftLen=m–i1;//計算左子樹的個數(shù)rightLen=len–(leftLen+1);//計算右子樹的個數(shù)CreateTree(T->lchild,in,i1,pre,i2+1,leftLen);//遞歸建立左子樹CreateTree(T->rchild,in,m+1,pre,i2+leftLen+1,rigthLen);//遞歸建立右子樹}}5.5任務(wù)提示

中序遍歷的非遞歸過程和先序遍歷的非遞歸類似，先序遍歷過程中找到一個結(jié)點，就訪問該結(jié)點，并將結(jié)點入棧。中序遍歷過程中，找到一個結(jié)點，由于需先訪問其左子樹，該結(jié)點先不能訪問，直接將其入棧。當(dāng)該結(jié)點的左子樹訪問完，回到該結(jié)點時再訪問該結(jié)點，并找到該結(jié)點的右子樹。所以中序遍歷的非遞歸過程中，當(dāng)p不為空時，將結(jié)點入棧，當(dāng)p為空，將棧頂元素出棧時再訪問該出棧的結(jié)點。任務(wù)2提示5.5任務(wù)提示中序遍歷的非遞歸過程如下：①初始化一個空棧S，指針p指向根結(jié)點；②當(dāng)p非空或者棧S非空時，循環(huán)執(zhí)行以下操作：

如果p非空，則將p進(jìn)棧，p指向該結(jié)點的左孩子；

如果p為空，則棧頂元素出棧并訪問出棧的元素，將p指向出棧元素的右孩子。任務(wù)2提示5.5任務(wù)提示偽代碼描述如下：任務(wù)2提示voidInOrderTraverse_NoRecur(BiTreeT){//中序遍歷二叉樹T的非遞歸算法InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){//p非空Push(S,p);//根指針進(jìn)棧p=p->lchild;//遍歷左子樹

}else{//p為空Pop(S,q);//棧頂出棧cout<<q->data;//訪問根結(jié)點p=q->rchild;//遍歷右子樹}}}5.5任務(wù)提示

可以利用先序、中序和后序遍歷方法，采用遞歸函數(shù)來判斷兩棵樹是否相等。假設(shè)兩棵樹相等，函數(shù)返回1，否則返回0。任務(wù)3提示

下面以用先序遍歷方法為例，說明其基本操作步驟為：

①如果兩棵二叉樹都為空，則函數(shù)返回1；

②如果兩棵二叉樹都不為空，則先判斷兩棵樹的根結(jié)點值是否相等，如果相等，則再采用遞歸調(diào)用的方法判斷它的左、右子樹是否相等，如果都相等則函數(shù)返回1；

③其它情況都返回0。5.5任務(wù)提示偽代碼描述如下：任務(wù)3提示intSameTree(BiTreeT1,BiTreeT2){//兩棵二叉樹都為空，則函數(shù)返回1if(T1==NULL&&T2==NULL)same=1;elseif(T1!=NULL&&T2!=NULL)//如果兩棵二叉樹都不為空{(diào)//則先判斷兩棵樹的根結(jié)點值是否相等if(T1->data==T2->data){//則再采用遞歸調(diào)用的方法判斷它的左、右子樹是否相等s1=SameTree(T1->lchild,T2->lchild);s2=SameTree(T1->rchild,T2->rchild);5.5任務(wù)提示偽代碼描述如下：任務(wù)3提示intSameTree(BiTreeT1,BiTreeT2){//如果都相等則函數(shù)返回1if(s1==1&&s2==1)same=1;elsesame=0;}else{same=0;}

}elsesame=0;returnsame;}5.5任務(wù)提示

要求出從根結(jié)點到指定結(jié)點p之間的路徑，可利用后序遍歷的非遞歸算法來實現(xiàn)。由于后序遍歷當(dāng)訪問到p所指結(jié)點時，棧中所有結(jié)點均為p所指結(jié)點的祖先，由這些祖先便構(gòu)成了一條從根結(jié)點到p結(jié)點之間的路徑。任務(wù)4提示5.5任務(wù)提示任務(wù)4提示

如下圖一棵二叉樹，求出根結(jié)點到結(jié)點G之間的路徑。