二叉樹遍歷的通用遞歸算法研究與實現

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

關鍵詞：二叉樹；遍歷；遞歸；棧；結構數組

中圖分類號：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 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(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 二叉樹遍歷的通用遞歸算法實現

4.1 二叉樹與結構數組

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

struct BTreeNode //二叉樹結點的結構類型

{

ElemType Data；//值域

BTreeNode *Left；//左指針域

BTreeNode *Right；//右指針域

};

struct Sequence //二叉樹遍歷序列結構數組

{

struct

{

ElemType Data；//值域

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

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

int Count；//二叉樹遍歷序列結構數組實際元素個數

}SeqList；

4.2 通用遞歸算法

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

void BTreeTraverse（BTreeNode *BT）

{

If (BT!=NULL)

{

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

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

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

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

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

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

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

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

SeqList.Count++；//序列數組元素個數增加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)))”，則結構數組List各元素的值如表1所示。

表1 List結構數組

■

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

5 結束語

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

參考文獻：

[1] 嚴蔚敏，吳偉民.數據結構[M].北京:清華大學出版社，2002.

[2] 許卓群.數據結構[M].中央廣播電視大學出版社，2002.

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

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

[5] 歐陽俊林.遍歷二叉樹的非遞歸實現[J].自貢師范高等專科學校學報，2003，18(4):126-129.

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

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