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

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

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

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

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

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

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

7、數(shù)，然后相加。根據(jù)二叉樹的五種基本形態(tài)五種基本形態(tài)知： 空空二叉樹，葉子結(jié)點數(shù)為0； 只有根只有根的二叉樹，葉子結(jié)點數(shù)為1； 只有左左子樹的二叉樹，葉子結(jié)點數(shù)為左左子樹中葉子結(jié)點數(shù)； 只有右右子樹的二叉樹，葉子結(jié)點數(shù)為右右子樹中葉子結(jié)點數(shù)； 具有左右左右子樹的二叉樹，葉子結(jié)點數(shù)等于左左子樹中葉子結(jié)點數(shù)、右右子樹中的葉子結(jié)點數(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空樹空樹只有根只有根左子樹左子樹右子樹右子樹統(tǒng)計二叉樹中總結(jié)點的個數(shù)算法思想算法思想 分別求出左子樹、右子樹的總結(jié)點數(shù)，然后與根求和。根據(jù)二叉樹的五種基本形態(tài)五種基本形態(tài)知： 空空二叉樹，結(jié)點數(shù)為0； 只有根只有根的二叉樹，結(jié)點數(shù)為1； 只有左左子樹的二叉樹，結(jié)點數(shù)為左左子樹中結(jié)點數(shù)加上根； 只有右右子樹的二叉樹，結(jié)點數(shù)為右右子樹中結(jié)點數(shù)加上根； 具有左右左右子樹的二叉樹，結(jié)點數(shù)等于左左子樹中結(jié)點數(shù)、右右子樹中的結(jié)點數(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空樹空樹左子樹左子樹右子樹右子樹求二叉樹的深度算法思想算法思想 二叉樹的深度應為其左、右子樹深度的最大值加1。根據(jù)二叉樹的五種基本形態(tài)五種基本形態(tài)知： 空空二叉樹，深度為0； 只有根只有根的二叉樹，深度為1； 只有左左子樹的二叉樹，深度為左左子樹的深度加1； 只有右右子樹的二叉樹，深度為右右子樹的深度加1； 具有左右左右子樹的二叉樹，深度等于左左子樹的深度與右右子樹的深度的最大值加1。遞

10、歸算法實現(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;空樹空樹左子樹左子樹右子樹右子樹建立二叉樹的存儲結(jié)構二叉樹針對不同的定義形式對應不同的二叉樹針對不同的定義形式對應不同的建立存儲結(jié)構的方法。建立存儲結(jié)構的方法。 以字符串的形式，按照先序遍歷思想，建立一棵二叉樹的二叉鏈表。以字符串的形式，按照先序遍歷思想，建立一棵二叉樹的二叉鏈表。以空白字符“ ”表示1.空樹空

11、樹2.只含一個根結(jié)點的二叉樹只含一個根結(jié)點的二叉樹 A以字符串“A ”表示ABCDA(B( ,C( , ),D( , )以下列字符串表示遞歸算法實現(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é)點 CreateBiTree( T-lchild ); / 構造左子樹 CreateBiTree( T-rchild ); / 構造右子樹 / Creat

12、eBiTreeA B C D A BCD算法執(zhí)行過程舉例如下：算法執(zhí)行過程舉例如下：ATBCD交換二叉樹的左右子樹空樹不需要進行任何交換操作；只有根的二叉樹交換后仍然只有根；只有左子樹的二叉樹，交換后變成只有右子樹的二叉樹；只有右子樹的二叉樹，交換后變成只有左子樹的二叉樹；具有左右子樹的二叉樹交換后，原左子樹變成右子樹，原右子樹變成左子樹。分別對于交換后的左子樹或右子樹重復進行上述操作直到操作完成。 算法思想算法思想 遞歸算法實現(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 ); 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，1.由先序和中序遍歷序列建立二叉樹 如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？ 二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根主要思想主要思想： 先序序列中第一個為“根”，標出之； 在中序序列中標出“根”，并分出左、右子樹； 在先序序列中標出左、右子樹；1. 分別對左、右子樹重復以上步驟。a b c d e f gc b d a e g f例如例如:aab bccddeeffgga

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

15、棧棧實現(xiàn)。仿照遞歸算法執(zhí)行過程中遞歸工作棧的狀態(tài)變化狀況可直接寫出相應的非遞歸算法。先序遍歷非遞歸算法先序遍歷非遞歸算法 中序遍歷非遞歸算法中序遍歷非遞歸算法 后序遍歷非遞歸算法后序遍歷非遞歸算法 先序遍歷的非遞歸算法實現(xiàn)思想實現(xiàn)思想 首先，根結(jié)點先入棧。在棧不空棧不空的情況下出棧出棧，若結(jié)點存在則訪問結(jié)點，對于訪問過的結(jié)點便對于訪問過的結(jié)點便可以棄之不用可以棄之不用，只要先將其右孩子入棧保存先將其右孩子入棧保存，再將其左孩子入棧保存再將其左孩子入棧保存即可。 先序遍歷非遞歸算法舉例 ABCDEGHF A AC B BE D D E G G C F FH H 遍歷結(jié)果遍歷結(jié)果 非遞歸算法實現(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 ); 中序遍歷的非遞歸算法實現(xiàn)思想實現(xiàn)思想 實現(xiàn)中序遍歷二叉樹的非遞歸算法時，需要設設一指針沿二叉樹中序順序移動一指針沿二叉樹中序順序移動，每當向上層移動時就要出棧出棧。指針p從根開始從根開始，首先沿著左子沿著左子樹向下移動樹向下

17、移動，同時入棧入棧保存；當?shù)竭_空子樹后需要退棧訪問結(jié)點退棧訪問結(jié)點，然后移動到右子樹移動到右子樹上去。 非遞歸算法實現(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; 非空進棧保存非空進棧保存沿左子樹向下移動沿左子樹向下移動為空向上移動，出棧，為空向上移動，出棧，訪問結(jié)點

18、訪問結(jié)點移動到右子樹上移動到右子樹上先序遍歷的非遞歸算法方法二實現(xiàn)思想實現(xiàn)思想 修改修改前面介紹的中序遍歷中序遍歷二叉樹的非遞歸算法也可得到先序遍歷得到先序遍歷二叉樹的另一種非遞歸算法實現(xiàn)，即將訪問結(jié)點的位置放在即將訪問結(jié)點的位置放在第一次指向該結(jié)點第一次指向該結(jié)點時時。 非遞歸算法先序遍歷實現(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; 非空進棧保存前，先訪問非空進棧保存前，先訪問沿左子樹向下移動沿左子樹向