c语言利用遍历求树高的程序,用C语言实现二叉树的遍历极其应用
用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)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 地税局是做什么的 研究制订地方各税
- 下一篇: 华为回应取消充电器 国产厂商千万别跟苹