用C語言實(shí)現(xiàn)二叉樹的遍歷極其應(yīng)用

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

[關(guān)鍵詞]： 數(shù)據(jù)結(jié)構(gòu); 樹; 二叉樹; 二叉樹的遍歷; C語言

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

在《數(shù)據(jù)結(jié)構(gòu)》中，樹型結(jié)構(gòu)是結(jié)點(diǎn)之間有分支的、層次的關(guān)系的結(jié)構(gòu)。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類的族譜、動植物的分類、圖書情報(bào)資料的編目等，都可以按照層次表示成樹的形式。在計(jì)算機(jī)程序設(shè)計(jì)方面，樹也是很重要的，如在編譯程序中，可以用樹來表示源程序的語法結(jié)構(gòu)。又如在數(shù)據(jù)庫系統(tǒng)中，樹形結(jié)構(gòu)也是信息的重要組織形式之一。

樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。其中以樹和二叉樹最為常用。

1、 樹 (Tree)

樹是n(n>=0)

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

2、 二叉樹 (Binary tree)

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

，則n0=n2+1。

對于使用C語言去實(shí)現(xiàn)二叉樹，首先需要抽象其二叉樹的數(shù)據(jù)類型。也就是需要構(gòu)造一個(gè)基本二叉樹的基礎(chǔ)操作的類和一個(gè)二叉樹結(jié)點(diǎn)數(shù)據(jù)類型。

第一步分析結(jié)點(diǎn)數(shù)據(jù)類型；

二叉樹的結(jié)點(diǎn)包括有本身的數(shù)據(jù)和左右子女的位置。

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

二叉樹的基本功能包括：

InitBiTree(&T);

操作結(jié)果:構(gòu)造空二叉樹T.

DestroyBiTree(&T);

初始條件:二叉樹T已經(jīng)存在.

操作結(jié)果:銷毀二叉樹T.

CreateBiTree(&T,description);

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

操作結(jié)果:根據(jù)description構(gòu)造二叉樹T.

ClearBiTree(&T);

初始條件:二叉樹T已經(jīng)存在.

操作結(jié)果:清空二叉樹.

IsEmptyBiTree(T);

初始條件:二叉樹T已經(jīng)存在.

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

GetBiTreeDepth(T);

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

操作結(jié)果:返回T的深度.

GetBiTreeRoot(T,&&root);

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

操作結(jié)果:返回二叉樹T的root根結(jié)點(diǎn).

GetBiTNodeValue(e,&value);

初始條件:結(jié)點(diǎn)e存在.

操作結(jié)果:返回結(jié)點(diǎn)e的data值字段.

AssignBitNode(&e,value);

初始條件:結(jié)點(diǎn)e存在.

操作結(jié)果:把value的值賦給結(jié)點(diǎn)e的data字段.

GetBiTNodeParent(T,e,&parent);

初始條件:二叉樹T,結(jié)點(diǎn)e存在.

操作結(jié)果:若e是T的非根結(jié)點(diǎn),則返回它的雙親,否則返回NULL.

GetBiTNodeLeftChild(e,&lChild);

初始條件:e存在,e是T的某個(gè)結(jié)點(diǎn).

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

GetBiTNodeRightChild(e,&rChild);

初始條件:e存在,e是T的某個(gè)結(jié)點(diǎn).

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

GetBiTNodeLeftSibling(T,e,&lSibling);

初始條件:二叉樹T存在,結(jié)點(diǎn)e存在,e是T的結(jié)點(diǎn).

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

GetBiTNodeRightSibling(T,e,&rSibling);

初始條件:二叉樹T存在,結(jié)點(diǎn)e存在,e是T的結(jié)點(diǎn).

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

InsertBiTNode(T,p,LR,c);

初始條件:二叉樹T,p是指向要插入的結(jié)點(diǎn),LR是左右枚舉,c是要插入的結(jié)點(diǎn).

操作結(jié)果:根據(jù)枚舉LR的內(nèi)容,插入結(jié)點(diǎn)e到p所指向的結(jié)點(diǎn)下.

DeleteBiTNode(T,p,LR);

初始條件:二叉樹T存在,p是指向要?jiǎng)h除的結(jié)點(diǎn),LR是左右枚舉.

操作結(jié)果:根據(jù)枚舉LR的內(nèi)容,刪除結(jié)點(diǎn)e的左/右結(jié)點(diǎn).

PreOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結(jié)點(diǎn)操作的函數(shù).

操作結(jié)果:先序遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù).

InOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結(jié)點(diǎn)操作的函數(shù).

操作結(jié)果:中序遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù).

PostOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結(jié)點(diǎn)操作的函數(shù).

操作結(jié)果:后序遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù).

LevelOrderBiTreeTraverse(&T,visit());

初始條件:二叉樹T存在,visit是對結(jié)點(diǎn)操作的函數(shù).

操作結(jié)果:層序遍歷T,對每個(gè)結(jié)點(diǎn)調(diào)用visit函數(shù).

DisplayBiTree(BiTree T);

初始條件:二叉樹存在.

操作結(jié)果:顯示二叉樹的內(nèi)容.

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

在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某些特征的結(jié)點(diǎn)，或者對樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。遍歷二叉樹是二叉樹的一種重要的運(yùn)算。

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

設(shè)訪問根結(jié)點(diǎn)記作 V

遍歷根的左子樹記作 L

遍歷根的右子樹記作 R

則可能的遍歷次序有

前序?VLR

中序?LVR

后序?LRV

3.1中序遍歷(Inorder Traversal)

二叉樹算法的定義：

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

否則

中序遍歷左子樹 (L)；

訪問根結(jié)點(diǎn) (V)；

中序遍歷右子樹 (R)。

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

void InOrder ( BinTreeNode *T ) {

if ( T !=

NULL ) {

InOrder ( T->leftChild );

Visit( T->data);

InOrder ( T->rightChild );

}

}

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

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

否則

訪問根結(jié)點(diǎn) (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)；

訪問根結(jié)點(diǎn) (V)。

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

void PostOrder ( BinTreeNode * T ) {

if ( T !=

NULL ) {

PostOrder ( T->leftChild );

PostOrder ( T->rightChild );

Visit( T->data);

}

}

4、 二叉樹遍歷算法的應(yīng)用舉例

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

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

Status CreateBiTree ( BiTree& T ) {

scanf(&ch);

if (

ch==‘’ ) T=NULL; //讀入根結(jié)點(diǎn)的值

else{

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

//建立根結(jié)點(diǎn)

T->data = ch;

CreateBiTree ( T->leftChild );

CreateBiTree ( T->rightChild );

}

return OK;

}//CreateBiTree

4.2?計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù)(遞歸算法)

int Count ( BinTreeNode *T ) {

if ( T ==

NULL ) return 0;

else

return 1 + Count ( T->leftChild )

+ Count ( T->rightChild );

}

4.3求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)

int Leaf_Count(Bitree T)

{//求二叉樹中葉子結(jié)點(diǎn)的數(shù)目

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

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

return 1; //葉子結(jié)點(diǎn)

else return

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

}

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?復(fù)制二叉樹(遞歸算法)

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?判斷二叉樹等價(jià)(遞歸算法)

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的子樹不等同，則函數(shù)返回0

}

二叉樹的遍歷也為后面的數(shù)據(jù)結(jié)構(gòu)：線索二叉樹以及線索化后的查找算法,

最優(yōu)二叉樹(哈夫曼樹)的概念、構(gòu)成和應(yīng)用，樹與森林的遍歷算法及其與二叉樹遍歷算法的聯(lián)系，?樹與森林和二叉樹的轉(zhuǎn)換做好鋪墊。

參考文獻(xiàn)：

1 嚴(yán)蔚敏，吳偉民編著《數(shù)據(jù)結(jié)構(gòu)》。清華大學(xué)出版社

2 唐策善，黃劉生編著《數(shù)據(jù)結(jié)構(gòu)》。中國科學(xué)技術(shù)大學(xué)出版社

谷立東 1967年出生于牡丹江 大學(xué)本科

講師一直從事計(jì)算機(jī)教學(xué)電話：3946366356，gld99@sina.com

總結(jié)

以上是生活随笔為你收集整理的c语言利用遍历求树高的程序,用C语言实现二叉树的遍历极其应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。