摘要：對二叉樹先序遍歷、中序遍歷和后序遍歷遞歸算法進行了分析，給出了三種遍歷方法的通用遞歸算法。該算法只需對二叉樹遍歷一次，對每個結(jié)點的值域（Data）訪問三次即可求出三種遍歷序列。

關(guān)鍵詞：二叉樹；遍歷；遞歸；棧；結(jié)構(gòu)數(shù)組

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)19-30132-03

Research and Realization of the General Recursive Algorithm of Traversing Binary Tree

YIN Bang-zhi

(Heyuan Radio TV University， Heyuan 517000， China)

Abstract: The paper analyses the recursion algorithm of preorder， inorder and postorder traverse of a binary tree， and defines a general recursion algorithm for the three kinds of traversing methods.this algorithm only need traverse the binary tree once， visit each node's data field three times， then three kinds of traversing sequences can be acquired.

Key words: Binary Tree; Traverse; Recursive; Stack; Structure Array

1 引言

二叉樹遍歷是指按照一定次序訪問一棵二叉樹中所有結(jié)點，并且每個結(jié)點的值域（Data）僅被訪問一次的過程。遍歷二叉樹最常用的方案有先序遍歷、中序遍歷和后序遍歷，在目前見到的資料中，大多將這三種遍歷方案分別討論[1-2][4-6]，文獻[3]提出了二叉樹遍歷的通用非遞歸算法。本文側(cè)重從二叉樹三種遍歷方案的遞歸算法展開分析，給出了三種遍歷方案的通用遞歸算法，只需對二叉樹遍歷一次，對每個結(jié)點的值域訪問三次即可求出三種遍歷序列。

2 二叉樹遍歷的通用遞歸算法的主要思想

根據(jù)二叉樹的遞歸定義，一棵非空二叉樹由根結(jié)點、左子樹和右子樹組成，遍歷一棵非空二叉樹的問題可分解為三個子問題：訪問根結(jié)點、遍歷左子樹和遍歷右子樹。按照先左子樹后右子樹的遍歷順序，可以得到以下三種遍歷方案的遞歸算法的主要思想：

先序遍歷遞歸算法的主要思想：若二叉樹為空，則空操作；否則，(1)訪問根結(jié)點；(2)遞歸遍歷左子樹；(3)遞歸遍歷右子樹。

中序遍歷遞歸算法的主要思想：若二叉樹為空，則空操作；否則，(1)遞歸遍歷左子樹；(2)訪問根結(jié)點；(3)遞歸遍歷右子樹。

后序遍歷遞歸算法的主要思想：若二叉樹為空，則空操作；否則，(1)遞歸遍歷左子樹；(2)遞歸遍歷右子樹；(3)訪問根結(jié)點。

從以上三種遍歷方案的遞歸算法中，不難發(fā)現(xiàn)，其本質(zhì)區(qū)別在于訪問根結(jié)點和遍歷左、右子樹的先后順序不同。由此我們可以得出二叉樹遍歷的通用遞歸算法的主要思想：(1)訪問根結(jié)點；(2)遞歸遍歷左子樹；(3)訪問根結(jié)點；(4)遞歸遍歷右子樹；(5)訪問根結(jié)點。在整個遞歸調(diào)用過程中，每個結(jié)點的值域（Data）均被訪問三次，可設(shè)一個結(jié)構(gòu)數(shù)組按順序存儲每次被訪問的結(jié)點的值，結(jié)構(gòu)數(shù)組包含兩個域：元素值域（Data）和遍歷類型域（Type），在遞歸遍歷左、右子樹之前訪問根結(jié)點（先序遍歷），將Type域置1；在遞歸遍歷左、右子樹之間訪問根結(jié)點（中序遍歷），將Type域置2；在遞歸遍歷左、右子樹之后訪問根結(jié)點（后序遍歷），將Type域置3。對二叉樹遞歸遍歷一次之后即可得到三種遍歷序列。

3 二叉樹遍歷的通用遞歸算法描述

二叉樹遍歷的通用遞歸算法如下（用C++語言描述）：

算法1：二叉樹遍歷的通用遞歸算法

輸入：二叉樹廣義表表示的字符串；

輸出：包含帶類型（1表示先序遍歷元素、2表示中序遍歷元素、3表示后序遍歷元素）的二叉樹先序、中序和后序遍歷序列。

(1)BTreeNode *BT；//定義指向二叉樹結(jié)點的指針，并用它作為樹根指針。

(2)InitBTree(BT)；//初始化二叉樹，即置樹根指針BT為空（NULL）。

(3)cin.getline(Array，sizeof(Array))；//從鍵盤輸入二叉樹廣義表表示的字符串，Array表示存放二叉樹廣義表的字符數(shù)組名。

(4)CreateBTree(BT，Array)；//建立以BT作為樹根指針的二叉樹鏈接存儲結(jié)構(gòu)。

(5)if(BT!=NULL)

(6){

(7)Visit(BT->Data)；//先序遍歷

(8)Recursion Visit(BT->Left)；//遞歸遍歷BT的左子樹

(9)Visit(BT->Data)；//中序遍歷

(10)Recursion Visit(BT->Right)；//遞歸遍歷BT的右子樹

(11)Visit(BT->Data)；//后序遍歷

(12)}//end if

(13)PrintSequence()；//輸出遍歷序列

4 二叉樹遍歷的通用遞歸算法實現(xiàn)

4.1 二叉樹與結(jié)構(gòu)數(shù)組

typedef char ElemType；//定義ElemType為Char類型

struct BTreeNode //二叉樹結(jié)點的結(jié)構(gòu)類型

{

ElemType Data；//值域

BTreeNode *Left；//左指針域

BTreeNode *Right；//右指針域

};

struct Sequence //二叉樹遍歷序列結(jié)構(gòu)數(shù)組

{

struct

{

ElemType Data；//值域

int Type；//遍歷類型：Type為1表示此時的Data為先序遍歷時的元素，Type為2表示此時Data為中序遍歷時的元素，Type為3表示此時的Data為后序遍歷時的元素。

}List[SequenceMaxSize]；//SequenceMaxSize為存儲三種遍歷序列的數(shù)組最大長度。

int Count；//二叉樹遍歷序列結(jié)構(gòu)數(shù)組實際元素個數(shù)

}SeqList；

4.2 通用遞歸算法

二叉樹通用遞歸算法如下：

void BTreeTraverse（BTreeNode *BT）

{

If (BT!=NULL)

{

SeqList.Count++；//序列數(shù)組元素個數(shù)增加1

SeqList.List[SeqList.Count-1].Data =BT->Data；//先序遍歷

SeqList.List[SeqList.Count-1].Type =1；

BTreeTraverse (BT->Left)；//遞歸遍歷BT的左子樹

SeqList.Count++；//序列數(shù)組元素個數(shù)增加1

SeqList.List[SeqList.Count-1].Data =BT->Data；//中序遍歷

SeqList.List[SeqList.Count-1].Type =2;

BTreeTraverse (BT->Right)；//遞歸遍歷BT的右子樹

SeqList.Count++；//序列數(shù)組元素個數(shù)增加1

SeqList.List[SeqList.Count-1].Data =BT->Data；//后序遍歷

SeqList.List[SeqList.Count-1].Type =3；

}//end if

}//end function

4.3 算法運行

若一棵二叉樹廣義表形式為“A(B(#，D(F，G))，C(E(#，H)))”，則結(jié)構(gòu)數(shù)組List各元素的值如表1所示。

表1 List結(jié)構(gòu)數(shù)組

■

從表1中可以看出，Type域為1的字符依次組成的序列“ABDFGCEH”即為該二叉樹遍歷的先序序列；Type域為2的字符依次組成的序列“BFDGAEHC”即為該二叉樹遍歷的中序序列；Type域為3的字符依次組成的序列“FGDBHECA”即為該二叉樹遍歷的后序序列。

5 結(jié)束語

算法1對每一個結(jié)點的數(shù)據(jù)值域（Data）都訪問了三次，每一個結(jié)點的左指針域（Left）和右子指針域（Right）都只被訪問一次，其時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)（n表示二叉樹結(jié)點個數(shù)）。該算法具有結(jié)構(gòu)簡練、清晰、可讀性強等優(yōu)點，并在Microsoft Visual C++6.0系統(tǒng)中運行通過。

參考文獻：

[1] 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，2002.

[2] 許卓群.數(shù)據(jù)結(jié)構(gòu)[M].中央廣播電視大學(xué)出版社，2002.

[3] 徐鳳生，李立群，馬夕榮.二叉樹遍歷的通用非遞歸算法[J].福建電腦，2006(6):41，121.

[4] 陳傳紅，沈武英.二叉樹遍歷研究及應(yīng)用[J].孝感學(xué)院學(xué)報，2005，25(3):72-73.

[5] 歐陽俊林.遍歷二叉樹的非遞歸實現(xiàn)[J].自貢師范高等?？茖W(xué)校學(xué)報，2003，18(4):126-129.

[6] 袁志民.二叉樹遍歷的非遞歸算法[J].電腦開發(fā)與應(yīng)用，2004，17(8):48.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文