數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)的遍歷及其他操作

1、第六章 二叉樹(shù)的遍歷及應(yīng)用本講內(nèi)容6.3 遍歷二叉樹(shù)遍歷二叉樹(shù)1.遍歷二叉樹(shù)的概念遍歷二叉樹(shù)的概念2.遍歷算法實(shí)現(xiàn)（遞歸算法和非遞歸算法）遍歷算法實(shí)現(xiàn)（遞歸算法和非遞歸算法）先序、中序、后序和層次遍歷3.遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例遍歷二叉樹(shù)遍歷二叉樹(shù)的概念遍歷二叉樹(shù)的概念遍歷二叉樹(shù)就是如何按某條搜索路徑巡訪二叉樹(shù)中遍歷二叉樹(shù)就是如何按某條搜索路徑巡訪二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。被訪問(wèn)一次。 如何確定搜索路徑如何確定搜索路徑？先上后下先上后下搜索先左后右先左后右搜索先先（根）序的遍歷算法中中（根）序的遍歷算

2、法后后（根）序的遍歷算法先左后右的遍歷算法先序遍歷二叉樹(shù)遍歷策略遍歷策略若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪問(wèn)根訪問(wèn)根結(jié)點(diǎn)；結(jié)點(diǎn)；（2）先序遍歷先序遍歷左子樹(shù)；左子樹(shù)；（3）先序遍歷先序遍歷右子樹(shù)。右子樹(shù)。ABCDEGHFABDEGCFH 遞歸算遞歸算法法先序遍歷二叉樹(shù)的遞歸算法實(shí)現(xiàn)void PreOrder ( BiTree T ) if ( T ) /如果樹(shù)不為空 visit( T-data ) ; /輸出根結(jié)點(diǎn) PreOrder ( T - lchild ) ; /先序遍歷左子樹(shù)PreOrder ( T - rchild ) ; /先序遍歷右子樹(shù) 中序遍歷二叉樹(shù)遍歷策略遍歷策略若二叉

3、樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷中序遍歷左子樹(shù)；左子樹(shù)；（2）訪問(wèn)根訪問(wèn)根結(jié)點(diǎn)；結(jié)點(diǎn)；（3）中序遍歷中序遍歷右子樹(shù)。右子樹(shù)。ABCDEGHFDBGEAFHC 遞歸算遞歸算法法中序遍歷二叉樹(shù)的遞歸算法實(shí)現(xiàn)void InOrder ( BiTree T ) if ( T ) /如果樹(shù)不為空 InOrder ( T - lchild ) ; /中序遍歷左子樹(shù)visit( T-data ) ; /輸出根結(jié)點(diǎn)InOrder ( T - rchild ) ; /中序遍歷右子樹(shù) 后序遍歷二叉樹(shù)遍歷策略遍歷策略若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序遍歷后序遍歷左子樹(shù)；左子樹(shù)；（2）后序遍歷后序遍歷

4、右子樹(shù)；右子樹(shù)；（3）訪問(wèn)根訪問(wèn)根結(jié)點(diǎn)。結(jié)點(diǎn)。ABCDEGHFDGEBHFCA 遞歸算遞歸算法法后序遍歷二叉樹(shù)的遞歸算法實(shí)現(xiàn)void PastOrder ( BiTree T ) if ( T ) /如果樹(shù)不為空 PastOrder ( T - lchild ) ; /后序遍歷左子樹(shù)PastOrder ( T - rchild ) ; /后序遍歷右子樹(shù)visit( T-data ) ; /輸出根結(jié)點(diǎn) 層次遍歷二叉樹(shù)遍歷策略遍歷策略采用“自上而下，自左而右自上而下，自左而右”的方法訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，即從第一層開(kāi)始，依次訪問(wèn)二叉樹(shù)中每一層的結(jié)點(diǎn)，同一層中按照先訪問(wèn)左孩子再訪問(wèn)右孩子的順序訪問(wèn)

5、結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)均被訪問(wèn)，此種遍歷需要借助于隊(duì)列隊(duì)列來(lái)完。 ABCDEGHFABCDEFGH 層次遍歷二叉樹(shù)的非遞歸算法實(shí)現(xiàn)void LevelOrder ( BinTree T) InitQueue ( Q ); / 隊(duì)列初始化為空 EnQueue ( Q, T ); / 根入隊(duì)列 while ( ! QueueEmpty(Q) ) / 隊(duì)列不空則繼續(xù)遍歷 DeQueue ( Q, p ); if ( p!=NULL ) visit ( p-data ); EnQueue (Q, p-lchild); / 左孩子入隊(duì)列 EnQueue (Q, p-rchild); /右孩子入隊(duì)列 首先將

6、根入隊(duì)列，以后若隊(duì)列不空則出隊(duì)頭元素首先將根入隊(duì)列，以后若隊(duì)列不空則出隊(duì)頭元素p，如果，如果p不空，則訪問(wèn)之。然后將其左右孩子入隊(duì)列，如此循環(huán)直到不空，則訪問(wèn)之。然后將其左右孩子入隊(duì)列，如此循環(huán)直到隊(duì)列為空。隊(duì)列為空。 遍歷算法的應(yīng)用舉例1.統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) 2.統(tǒng)計(jì)二叉樹(shù)中總結(jié)點(diǎn)的個(gè)數(shù)統(tǒng)計(jì)二叉樹(shù)中總結(jié)點(diǎn)的個(gè)數(shù) 3.求二叉樹(shù)的深度求二叉樹(shù)的深度 4.建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5.交換二叉樹(shù)的左右子樹(shù)交換二叉樹(shù)的左右子樹(shù) 6.根據(jù)遍歷序列畫(huà)對(duì)應(yīng)二叉樹(shù)根據(jù)遍歷序列畫(huà)對(duì)應(yīng)二叉樹(shù) 統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)算法思想算法思想 分別求出左子樹(shù)、右子樹(shù)的葉子

7、數(shù)，然后相加。根據(jù)二叉樹(shù)的五種基本形態(tài)五種基本形態(tài)知： 空空二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為0； 只有根只有根的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為1； 只有左左子樹(shù)的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為左左子樹(shù)中葉子結(jié)點(diǎn)數(shù)； 只有右右子樹(shù)的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為右右子樹(shù)中葉子結(jié)點(diǎn)數(shù)； 具有左右左右子樹(shù)的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)等于左左子樹(shù)中葉子結(jié)點(diǎn)數(shù)、右右子樹(shù)中的葉子結(jié)點(diǎn)數(shù)之和之和。遞歸算法實(shí)現(xiàn)int CountLeaf (BiTree T)if ( !T ) return 0; else if ( (!T-lchild)& (!T-rchild) ) return 1; else nl=CountLeaf( T-lchild); nr=Co

8、untLeaf( T-rchild); return nl+nr; / if / CountLeaf空樹(shù)空樹(shù)只有根只有根左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)統(tǒng)計(jì)二叉樹(shù)中總結(jié)點(diǎn)的個(gè)數(shù)算法思想算法思想 分別求出左子樹(shù)、右子樹(shù)的總結(jié)點(diǎn)數(shù)，然后與根求和。根據(jù)二叉樹(shù)的五種基本形態(tài)五種基本形態(tài)知： 空空二叉樹(shù)，結(jié)點(diǎn)數(shù)為0； 只有根只有根的二叉樹(shù)，結(jié)點(diǎn)數(shù)為1； 只有左左子樹(shù)的二叉樹(shù)，結(jié)點(diǎn)數(shù)為左左子樹(shù)中結(jié)點(diǎn)數(shù)加上根； 只有右右子樹(shù)的二叉樹(shù)，結(jié)點(diǎn)數(shù)為右右子樹(shù)中結(jié)點(diǎn)數(shù)加上根； 具有左右左右子樹(shù)的二叉樹(shù)，結(jié)點(diǎn)數(shù)等于左左子樹(shù)中結(jié)點(diǎn)數(shù)、右右子樹(shù)中的結(jié)點(diǎn)數(shù)加上根之和之和。遞歸算法實(shí)現(xiàn)int NodeCount ( BinTree T

9、) if ( !T) return 0; else nl = NodeCount( T-lchild ) ;nr = NodeCount( T-rchild );return 1 + nl + nr ; /if空樹(shù)空樹(shù)左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)求二叉樹(shù)的深度算法思想算法思想 二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。根據(jù)二叉樹(shù)的五種基本形態(tài)五種基本形態(tài)知： 空空二叉樹(shù)，深度為0； 只有根只有根的二叉樹(shù)，深度為1； 只有左左子樹(shù)的二叉樹(shù)，深度為左左子樹(shù)的深度加1； 只有右右子樹(shù)的二叉樹(shù)，深度為右右子樹(shù)的深度加1； 具有左右左右子樹(shù)的二叉樹(shù)，深度等于左左子樹(shù)的深度與右右子樹(shù)的深度的最大值加1。遞

10、歸算法實(shí)現(xiàn)int Depth( BinTree T) if ( !T) return 0; else dl = Depth( T-lchild ) ;dr = Depth( T-rchild );depth = 1 + ( dldr ? dl : dr ) ; return depth;空樹(shù)空樹(shù)左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)針對(duì)不同的定義形式對(duì)應(yīng)不同的二叉樹(shù)針對(duì)不同的定義形式對(duì)應(yīng)不同的建立存儲(chǔ)結(jié)構(gòu)的方法。建立存儲(chǔ)結(jié)構(gòu)的方法。 以字符串的形式，按照先序遍歷思想，建立一棵二叉樹(shù)的二叉鏈表。以字符串的形式，按照先序遍歷思想，建立一棵二叉樹(shù)的二叉鏈表。以空白字符“ ”表示1.空樹(shù)空

11、樹(shù)2.只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù) A以字符串“A ”表示ABCDA(B( ,C( , ),D( , )以下列字符串表示遞歸算法實(shí)現(xiàn)void CreateBiTree( BiTree &T ) scanf(“%c”,&ch); if (ch= ) T = NULL; else if (!(T = (BiTree)malloc(sizeof(BiTNode) exit(overflow); T-data = ch; / 生成根結(jié)點(diǎn) CreateBiTree( T-lchild ); / 構(gòu)造左子樹(shù) CreateBiTree( T-rchild ); / 構(gòu)造右子樹(shù) / Creat

12、eBiTreeA B C D A BCD算法執(zhí)行過(guò)程舉例如下：算法執(zhí)行過(guò)程舉例如下：ATBCD交換二叉樹(shù)的左右子樹(shù)空樹(shù)不需要進(jìn)行任何交換操作；只有根的二叉樹(shù)交換后仍然只有根；只有左子樹(shù)的二叉樹(shù)，交換后變成只有右子樹(shù)的二叉樹(shù)；只有右子樹(shù)的二叉樹(shù)，交換后變成只有左子樹(shù)的二叉樹(shù)；具有左右子樹(shù)的二叉樹(shù)交換后，原左子樹(shù)變成右子樹(shù)，原右子樹(shù)變成左子樹(shù)。分別對(duì)于交換后的左子樹(shù)或右子樹(shù)重復(fù)進(jìn)行上述操作直到操作完成。 算法思想算法思想 遞歸算法實(shí)現(xiàn)void change(BinTree &T) if( !T ) return T; elset=T-lchild; T-lchild=T-rchild; T -rc

13、hild=t;change( T-lchild );change( T-rchild ); 僅知二叉樹(shù)的先序序列“abcdefg” 不能唯一確定一棵二叉樹(shù)，1.由先序和中序遍歷序列建立二叉樹(shù) 如果同時(shí)已知二叉樹(shù)的中序序列“cbdaegf”，則會(huì)如何？ 二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù)右子樹(shù)右子樹(shù)根根根根主要思想主要思想： 先序序列中第一個(gè)為“根”，標(biāo)出之； 在中序序列中標(biāo)出“根”，并分出左、右子樹(shù)； 在先序序列中標(biāo)出左、右子樹(shù)；1. 分別對(duì)左、右子樹(shù)重復(fù)以上步驟。a b c d e f gc b d a e g f例如例如:aab bccddeeffgga

14、bcdefg先序序列中序序列2.由后序和中序遍歷序列建立二叉樹(shù)二叉樹(shù)的后序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù) 根根左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根主要思想：后序序列中第一個(gè)為“根”，標(biāo)出之；在中序序列中標(biāo)出“根”，并分出左、右子樹(shù)；在后序序列中標(biāo)出左、右子樹(shù)；1. 分別對(duì)左、右子樹(shù)重復(fù)以上步驟。3.由后序和先序序列能否建立二叉樹(shù)？二叉樹(shù)的后序序列二叉樹(shù)的先序序列左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù) 根根左子樹(shù)左子樹(shù) 右子樹(shù)右子樹(shù)根根結(jié)論：結(jié)論：不能唯一確定二叉樹(shù)！不能唯一確定二叉樹(shù)！ABAB或或例如：例如：先序：先序：AB 后序：后序：BA二叉樹(shù)遍歷的非遞歸算法遍歷二叉樹(shù)的非遞歸算法，一般借助于

15、棧棧實(shí)現(xiàn)。仿照遞歸算法執(zhí)行過(guò)程中遞歸工作棧的狀態(tài)變化狀況可直接寫(xiě)出相應(yīng)的非遞歸算法。先序遍歷非遞歸算法先序遍歷非遞歸算法 中序遍歷非遞歸算法中序遍歷非遞歸算法 后序遍歷非遞歸算法后序遍歷非遞歸算法 先序遍歷的非遞歸算法實(shí)現(xiàn)思想實(shí)現(xiàn)思想 首先，根結(jié)點(diǎn)先入棧。在棧不空棧不空的情況下出棧出棧，若結(jié)點(diǎn)存在則訪問(wèn)結(jié)點(diǎn)，對(duì)于訪問(wèn)過(guò)的結(jié)點(diǎn)便對(duì)于訪問(wèn)過(guò)的結(jié)點(diǎn)便可以棄之不用可以棄之不用，只要先將其右孩子入棧保存先將其右孩子入棧保存，再將其左孩子入棧保存再將其左孩子入棧保存即可。 先序遍歷非遞歸算法舉例 ABCDEGHF A AC B BE D D E G G C F FH H 遍歷結(jié)果遍歷結(jié)果 非遞歸算法實(shí)現(xiàn)先

16、序遍歷void Preorder ( BinTree bt, VisitFunc visit ) InitStack ( S ); Push ( S, bt ); while ( ! StackEmpty(S) ) Pop ( S, p ); if ( p ) visit ( p ); Push ( S, p-rchild ); Push ( S, p-lchild ); 中序遍歷的非遞歸算法實(shí)現(xiàn)思想實(shí)現(xiàn)思想 實(shí)現(xiàn)中序遍歷二叉樹(shù)的非遞歸算法時(shí)，需要設(shè)設(shè)一指針沿二叉樹(shù)中序順序移動(dòng)一指針沿二叉樹(shù)中序順序移動(dòng)，每當(dāng)向上層移動(dòng)時(shí)就要出棧出棧。指針p從根開(kāi)始從根開(kāi)始，首先沿著左子沿著左子樹(shù)向下移動(dòng)樹(shù)向下

17、移動(dòng)，同時(shí)入棧入棧保存；當(dāng)?shù)竭_(dá)空子樹(shù)后需要退棧訪問(wèn)結(jié)點(diǎn)退棧訪問(wèn)結(jié)點(diǎn)，然后移動(dòng)到右子樹(shù)移動(dòng)到右子樹(shù)上去。 非遞歸算法實(shí)現(xiàn)中序遍歷void InOrder ( BinTree bt , VisitFunc visit ) InitStack ( S ); p = bt; while ( p | ! StackEmpty(S) ) if ( p ) Push ( S, p ); p = p-lchild; else Pop ( S, p ); visit ( p ); p = p-rchild; 非空進(jìn)棧保存非空進(jìn)棧保存沿左子樹(shù)向下移動(dòng)沿左子樹(shù)向下移動(dòng)為空向上移動(dòng)，出棧，為空向上移動(dòng)，出棧，訪問(wèn)結(jié)點(diǎn)

18、訪問(wèn)結(jié)點(diǎn)移動(dòng)到右子樹(shù)上移動(dòng)到右子樹(shù)上先序遍歷的非遞歸算法方法二實(shí)現(xiàn)思想實(shí)現(xiàn)思想 修改修改前面介紹的中序遍歷中序遍歷二叉樹(shù)的非遞歸算法也可得到先序遍歷得到先序遍歷二叉樹(shù)的另一種非遞歸算法實(shí)現(xiàn)，即將訪問(wèn)結(jié)點(diǎn)的位置放在即將訪問(wèn)結(jié)點(diǎn)的位置放在第一次指向該結(jié)點(diǎn)第一次指向該結(jié)點(diǎn)時(shí)時(shí)。 非遞歸算法先序遍歷實(shí)現(xiàn)二void PreOrder ( BinTree bt , VisitFunc visit ) InitStack ( S ); p = bt; while ( p | ! StackEmpty(S) ) if ( p ) visit ( p ); Push ( S, p ); p = p-lchild; else Pop ( S, p ); p = p-rchild; 非空進(jìn)棧保存前，先訪問(wèn)非空進(jìn)棧保存前，先訪問(wèn)沿左子樹(shù)向下移動(dòng)沿左子樹(shù)向