用C語言實現二叉樹的遍歷極其應用

[1]〔摘要〕：《數據結構》是計算機系學生的一門專業技術基礎課程，計算機科學各領域及有關的應用軟件都要用到各種數據結構。C語言有較豐富的數據類型、運算符以及函數，能直接與內存打交道，使修改、編輯其他程序與文檔變得簡單，因此用C語言實現的《數據結構》程序越來越得到廣泛應用。樹型結構是一類重要的非線性數據結構,其中以樹和二叉樹最為常用。二叉樹的遍歷算法是樹形結構中其他運算的基礎，在二叉樹遍歷的各種算法中包括了一些精致的，并且在其他應用范圍內也有用的技巧，所以本文主要討論用C語言去實現二叉樹遍歷的幾種不同算法。

[關鍵詞]： 數據結構; 樹; 二叉樹; 二叉樹的遍歷; C語言

《數據結構》在計算機科學中是一門綜合性的專業基礎課。《數據結構》的研究不僅涉及到計算機硬件(特別是編碼理論、存儲裝置和存取方法等)的研究范圍，而且和計算機軟件的研究有著更密切的關系，無論是編譯程序，還是操作系統，都涉及到數據元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數據，以便查找和存取數據元素更為方便。可以認為《數據結構》是介于數學、計算機硬件和計算機軟件三者之間的一門核心課程，是從事計算機科學及其應用的科技工作者必須掌握的重要課程。

在《數據結構》中，樹型結構是結點之間有分支的、層次的關系的結構。樹結構在客觀世界中廣泛存在，如人類的族譜、動植物的分類、圖書情報資料的編目等，都可以按照層次表示成樹的形式。在計算機程序設計方面，樹也是很重要的，如在編譯程序中，可以用樹來表示源程序的語法結構。又如在數據庫系統中，樹形結構也是信息的重要組織形式之一。

樹型結構是一類重要的非線性數據結構。其中以樹和二叉樹最為常用。

1、 樹 (Tree)

樹是n(n>=0)

個結點的有限集。在一棵非空樹中：(1)有且僅有一個特定的稱為根(Root)的結點;(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,……，Tm,其中每一個集合本身又是一棵樹，并且稱為子樹(Subtree)。結點擁有的子樹數稱為結點的度(degree)。樹的度是樹內各結點的度的最大值。

2、 二叉樹 (Binary tree)

二叉樹是另一種樹型結構，它的特點是每個結點至多只有二棵子樹(即二叉樹中不存在度大于2的結點)，二叉樹的子樹有左右之分，其次不能任意顛倒。二叉樹第i層上的結點數目最多為2i-1(i>=1)；深度為k的二叉樹至多有2k-1個結點,(k≥1)；對任何一棵二叉樹T，如果其終端結點數n0,度為2的結點數為n2

，則n0=n2+1。

對于使用C語言去實現二叉樹，首先需要抽象其二叉樹的數據類型。也就是需要構造一個基本二叉樹的基礎操作的類和一個二叉樹結點數據類型。

第一步分析結點數據類型；

二叉樹的結點包括有本身的數據和左右子女的位置。

第二步是去設計二叉樹的基本操作，這里需要通過分析該二叉樹基本功能，然后去構造一個類來完成，這部需要使用到上一步中的自定義類型。

二叉樹的基本功能包括：

InitBiTree(&T);

操作結果:構造空二叉樹T.

DestroyBiTree(&T);

初始條件:二叉樹T已經存在.

操作結果:銷毀二叉樹T.

CreateBiTree(&T,description);

初始條件:給出二叉樹的定義.

操作結果:根據description構造二叉樹T.

ClearBiTree(&T);

初始條件:二叉樹T已經存在.

操作結果:清空二叉樹.

IsEmptyBiTree(T);

初始條件:二叉樹T已經存在.

操作結果:若T為空二叉樹,則返回TRUE;否則返回FALSE.

GetBiTreeDepth(T);

初始條件:二叉樹T存在.

操作結果:返回T的深度.

GetBiTreeRoot(T,&&root);

初始條件:二叉樹T存在且不為空.

操作結果:返回二叉樹T的root根結點.

GetBiTNodeValue(e,&value);

初始條件:結點e存在.

操作結果:返回結點e的data值字段.

AssignBitNode(&e,value);

初始條件:結點e存在.

操作結果:把value的值賦給結點e的data字段.

GetBiTNodeParent(T,e,&parent);

初始條件:二叉樹T,結點e存在.

操作結果:若e是T的非根結點,則返回它的雙親,否則返回NULL.

GetBiTNodeLeftChild(e,&lChild);

初始條件:e存在,e是T的某個結點.

操作結果:若e有左孩子,則返回它的左孩子,否則返回NULL.

GetBiTNodeRightChild(e,&rChild);

初始條件:e存在,e是T的某個結點.

操作結果:若e有右孩子,則返回它的右孩子,否則返回NULL.

GetBiTNodeLeftSibling(T,e,&lSibling);

初始條件:二叉樹T存在,結點e存在,e是T的結點.

操作結果:返回e的左兄弟,若e無左兄弟,返回NULL.

GetBiTNodeRightSibling(T,e,&rSibling);

初始條件:二叉樹T存在,結點e存在,e是T的結點.

操作結果:返回e的右兄弟,若e無右兄弟,返回NULL.

InsertBiTNode(T,p,LR,c);

初始條件:二叉樹T,p是指向要插入的結點,LR是左右枚舉,c是要插入的結點.

操作結果:根據枚舉LR的內容,插入結點e到p所指向的結點下.

DeleteBiTNode(T,p,LR);

初始條件:二叉樹T存在,p是指向要刪除的結點,LR是左右枚舉.

操作結果:根據枚舉LR的內容,刪除結點e的左/右結點.

PreOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結點操作的函數.

操作結果:先序遍歷T,對每個結點調用visit函數.

InOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結點操作的函數.

操作結果:中序遍歷T,對每個結點調用visit函數.

PostOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結點操作的函數.

操作結果:后序遍歷T,對每個結點調用visit函數.

LevelOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結點操作的函數.

操作結果:層序遍歷T,對每個結點調用visit函數.

DisplayBiTree(BiTree T);

初始條件:二叉樹存在.

操作結果:顯示二叉樹的內容.

3、 二叉樹的遍歷(Traversing binary tree)

在二叉樹的一些應用中，常常要求在樹中查找具有某些特征的結點，或者對樹中全部結點逐一進行某種處理。遍歷二叉樹是二叉樹的一種重要的運算。

所謂遍歷(Traversal)是指按某條搜索路徑巡訪樹中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。“訪問”的含義很廣，可以是對結點作可種處理，如輸出結點的信息等。

設訪問根結點記作 V

遍歷根的左子樹記作 L

遍歷根的右子樹記作 R

則可能的遍歷次序有

前序?VLR

中序?LVR

后序?LRV

3.1中序遍歷(Inorder Traversal)

二叉樹算法的定義：

若二叉樹為空，則空操作；

否則

中序遍歷左子樹 (L)；

訪問根結點 (V)；

中序遍歷右子樹 (R)。

中序遍歷二叉樹的遞歸算法

void InOrder ( BinTreeNode *T ) {

if ( T !=

NULL ) {

InOrder ( T->leftChild );

Visit( T->data);

InOrder ( T->rightChild );

}

}

3.2前序遍歷(Preorder Traversal)二叉樹算法的定義：

若二叉樹為空，則空操作；

否則

訪問根結點 (V)；

前序遍歷左子樹 (L)；

前序遍歷右子樹 (R)。

前序遍歷二叉樹的遞歸算法

void PreOrder ( BinTreeNode *T ) {

if ( T !=

NULL ) {

Visit( T->data);

PreOrder

( T->leftChild );

PreOrder ( T->rightChild );

}

}

3.3后序遍歷(Postorder Traversal)二叉樹算法的定義：

若二叉樹為空，則空操作；

否則

后序遍歷左子樹 (L)；

后序遍歷右子樹 (R)；

訪問根結點 (V)。

后序遍歷二叉樹的遞歸算法：

void PostOrder ( BinTreeNode * T ) {

if ( T !=

NULL ) {

PostOrder ( T->leftChild );

PostOrder ( T->rightChild );

Visit( T->data);

}

}

4、 二叉樹遍歷算法的應用舉例

我們可以在三種遍歷算法的基礎上改造完成的其它二叉樹算法,如：?求葉子個數，求二叉樹結點總數，求度為1或度為2的結點總數，復制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結點，刪除值為n的某個指定結點，等等。

4.1按前序建立二叉樹(遞歸算法)

Status CreateBiTree ( BiTree& T ) {

scanf(&ch);

if (

ch==‘’ ) T=NULL; //讀入根結點的值

else{

if ( !(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);

//建立根結點

T->data = ch;

CreateBiTree ( T->leftChild );

CreateBiTree ( T->rightChild );

}

return OK;

}//CreateBiTree

4.2?計算二叉樹結點個數(遞歸算法)

int Count ( BinTreeNode *T ) {

if ( T ==

NULL ) return 0;

else

return 1 + Count ( T->leftChild )

+ Count ( T->rightChild );

}

4.3求二叉樹中葉子結點的個數

int Leaf_Count(Bitree T)

{//求二叉樹中葉子結點的數目

if(!T) return 0; //空樹沒有葉子

elseif(!T->lchild&&!T->rchild)

return 1; //葉子結點

else return

Leaf_Count(T-lchild)+Leaf_Count(T-rchild); //左子樹的葉子數加上右子樹的葉子數

}

4.4?求二叉樹高度(遞歸算法)

int Height ( BinTreeNode * T )

{

if ( T ==

NULL ) return 0;

else?{

int m = Height ( T->leftChild );

int n = Height ( T->rightChild ) );

return (m > n) ? m+1 :

n+1;

}

}

4.5?復制二叉樹(遞歸算法)

BiTNode* Copy( BinTreeNode * T )

{

if ( T == NULL ) return NULL;

if(!(Temp=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);

Temp->data=T->data;

Temp-> leftChild = Copy( T->leftChild

);

Temp-> rightChild =

Copy(T->rightChild );

return Temp;

}

4.6?判斷二叉樹等價(遞歸算法)

int Equal( BinTreeNode *a, BinTreeNode *b) {

if ( a == NULL && b == NULL )

return 1;

if ( a !== NULL && b !== NULL

&&

a->data==b->data

&& equal(

a->leftChild, b->leftChild)

&& equal(

a->rightChild, b->rightChild) )

return 1;

return

0;//如果a和b的子樹不等同，則函數返回0

}

二叉樹的遍歷也為后面的數據結構：線索二叉樹以及線索化后的查找算法,

最優二叉樹(哈夫曼樹)的概念、構成和應用，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯系，?樹與森林和二叉樹的轉換做好鋪墊。

參考文獻：

1 嚴蔚敏，吳偉民編著《數據結構》。清華大學出版社

2 唐策善，黃劉生編著《數據結構》。中國科學技術大學出版社

谷立東 1967年出生于牡丹江 大學本科

講師一直從事計算機教學電話：3946366356，gld99@sina.com