數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1/1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計說明書

二叉平衡數(shù)算法實現(xiàn)

班級：計科1703組別：十七

指導(dǎo)老師：彭代文完成時間：2023.6.20組長：學(xué)號：

組員1：學(xué)號：

組員2：學(xué)號：

成果：

名目

1.課題設(shè)計任務(wù)(1)

2.任務(wù)分析(1)

3.概要設(shè)計(2)

3.1功能模塊的劃分(2)

3.1.1主功能模塊(2)

3.1.2創(chuàng)建樹模塊(2)

3.1.3遍歷樹模塊(2)

3.2功能函數(shù)調(diào)用圖(2)

4.具體設(shè)計(3)

4.1數(shù)據(jù)存儲結(jié)構(gòu)：(3)

4.2各模塊流程圖及算法：(4)

4.2.1主函數(shù)(4)

4.2.2輸入二叉樹(5)

4.2.3非遞歸遍歷(5)

4.2.4遞歸遍歷(7)

4.3算法的效率分析：(8)

5.測試(9)

6．課程設(shè)計心得(10)

6.1改進(jìn)方案(10)

6.2設(shè)計心得(10)

7．

1.課題設(shè)計任務(wù)

現(xiàn)實世界層次化的數(shù)據(jù)模型中，數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系紛繁簡單。其中許多關(guān)系無法使用簡潔的線性結(jié)構(gòu)表示清晰，比如祖先與后代的關(guān)系、整體與部分的關(guān)系等。于是人們借鑒自然界中樹的形象制造了一種強大的非線性結(jié)構(gòu)——樹。樹形結(jié)構(gòu)的詳細(xì)形式有許多種，其中最常用的就是二叉樹。

針對這樣的問題,我選擇了二叉樹的操作作為我的課程設(shè)計主題,編寫程序,實現(xiàn)對二叉樹的遍歷.在本次課程設(shè)計中,二叉樹的建立使用了遞歸算法；在前序、中序和后續(xù)遍歷的算法中則同時使用了遞歸與非遞歸的算法,即在這些遍歷算法的實現(xiàn)中使用了棧結(jié)構(gòu)與隊列結(jié)構(gòu),供應(yīng)了6種不同的遍歷方式,供使用者選擇.同時,該程序具有輸出層序遍歷的功能,層序遍歷模塊使用了非遞歸算法.該程序基本實現(xiàn)了對二叉樹的遍歷,對于遞歸與非遞歸算法,我們應(yīng)從實際應(yīng)用中體驗這些算法的優(yōu)越性。

編程實現(xiàn)二叉樹的建立，先序、中序、后序（遞歸和非遞歸方法）、層序遍歷，二叉樹的高度、統(tǒng)計葉子節(jié)點的數(shù)目、統(tǒng)計結(jié)點總數(shù)、輸出結(jié)點的最大值、輸出結(jié)點所在的層數(shù)、打印輸出二叉樹的單鏈表形式。

2.任務(wù)分析

數(shù)據(jù)存儲：采納二叉鏈表存儲

功能設(shè)計：首先，創(chuàng)建二叉樹；其次打印二叉樹：若二叉樹為空，則空操作；否則依次打印右子樹、打印根結(jié)點、打印左子樹；最終，要實現(xiàn)二叉樹的一些基本運算，包括先序遍歷、中序遍歷、后序遍歷、計算結(jié)點數(shù)、葉子節(jié)點數(shù)、計算結(jié)點所在層等操作。詳細(xì)分別是先序遍歷二叉樹：利用二叉鏈表作為存儲結(jié)構(gòu)的先序遍歷，先訪問根結(jié)點，在依次訪問左右子樹；中序遍歷二叉樹：利用二叉鏈表作為存儲結(jié)構(gòu)的中序遍歷，先訪問左子樹，再訪問根結(jié)點，最終訪問右子樹；后序遍歷二叉樹：利用二叉鏈表作為存儲結(jié)構(gòu)的后序遍歷，先訪問左子樹，再訪問右子樹，最終訪問根結(jié)點；計算二叉樹葉子數(shù)：若二叉樹為空，返回0；若只有根結(jié)點，返回1；否則，返回左子樹+右子樹；計算二叉樹結(jié)點數(shù)：若二叉樹為空，返回0；若只有根結(jié)點，返回1；否則，返回左子樹+右子樹+1。

運用手動鍵盤輸入，將二叉樹序列按先序的挨次，從鍵盤輸入到字符數(shù)組中，實現(xiàn)二叉樹的創(chuàng)建。運用遞歸的方式，計算出二叉樹的節(jié)點的個數(shù)以及二叉樹的深度，并且在屏幕輸出顯示等等操作比較基礎(chǔ)。遍歷二叉樹分為四種方式，先序遍歷、中序遍歷、后序遍歷、層次遍歷。其中先序遍歷、中序遍歷和后序遍歷都用遞歸與非遞歸的方法實現(xiàn)，采納鏈表存儲的方式，并在屏幕輸出結(jié)果。層次遍歷運用循環(huán)隊列的方法實現(xiàn)，需要重新定義隊頭和隊尾，以及隊列的最大長度，并且在屏幕上實現(xiàn)輸出顯示。第一次勝利創(chuàng)建二叉樹之后，假如想要重新創(chuàng)建，必需將已經(jīng)創(chuàng)建的二叉樹實現(xiàn)刪除，并且釋放內(nèi)存空間，實現(xiàn)其次次重新創(chuàng)建。

用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)對二叉排序樹的的創(chuàng)建，各種遍歷，樹高、節(jié)點數(shù)量等基本操作，

在整個程序中可以將程序分為四大代碼塊，首先菜單代碼塊；其次是基礎(chǔ)代碼塊，分別包括棧操作代碼塊和隊列操作代碼塊；再其次是主體代碼塊即各種樹操作的函數(shù)代碼塊，最終是輸出操作代碼塊。VisualStudio2023編寫，可以實現(xiàn)對二叉樹的多種方式的創(chuàng)建、采納遞歸和非遞歸等兩種方式先序、中序、后序進(jìn)行遍歷下面是詳細(xì)介紹。

3.概要設(shè)計

3.1功能模塊的劃分

3.1.1主功能模塊

通過合理的界面設(shè)計，依據(jù)提示信息，使用者可以便利快捷地運行本程序來完成創(chuàng)建、遍歷二叉樹、查找結(jié)點等操作。界面美觀，人性化，程序智能，平安性高。

3.1.2創(chuàng)建樹模塊

當(dāng)進(jìn)入程序運行界面后，依據(jù)提示輸入需要建立的二叉樹，建立完二叉樹后自動進(jìn)入下一個功能模塊。

3.1.3遍歷樹模塊

實現(xiàn)對該二叉樹的先序遞歸遍歷、先序非遞歸遍歷、中序遞歸遍歷、中序非遞歸遍歷、后序遞歸遍歷、后序非遞歸遍歷、層序非遞歸遍歷等方式的遍歷操作，并輸出各遍歷序列。

3.2功能函數(shù)調(diào)用圖

圖4-1調(diào)用關(guān)系圖

其他功能均為單個函數(shù)實現(xiàn)，不做流程描述

4.具體設(shè)計

4.1數(shù)據(jù)存儲結(jié)構(gòu)：

BTNode*LchildNode(BTNode*p)//返回*p結(jié)點的左孩子結(jié)點指針BTNode*RchildNode(BTNode*p)//返回*p結(jié)點的右孩子結(jié)點指針voidCreateBTree(BTNode*&b,char*str//創(chuàng)建樹

intFindNode(BTNode*b,ElemTypex)//查找結(jié)點是否存在

voidInitQueue(Sueue*&q)//創(chuàng)建隊列

boolQueueEmpty(Sueue*q)//推斷隊列是否為空

boolenQueue(Sueue*q,BTNode*e)//進(jìn)隊列

booldeQueue(Sueue*&q,BTNode*&e)//出隊列

voidDestoryBTree(BTNode*&b)//銷毀釋放二叉樹

voidDispBTree(BTNode*b)//輸出二叉樹

intBTHeight(BTNode*b)//計算二叉樹高度

voidPreOrder(BTNode*b)//先序遞歸遍歷算法

voidInOrder(BTNode*b)//中序遞歸遍歷算法

voidPostOrder(BTNode*b)//后序遞歸遍歷算法

voidDispLeaf(BTNode*b)//輸出葉子結(jié)點

intlistleaf(BTNode*b)//輸出葉子結(jié)點個數(shù)

intlistnode(BTNode*b)//輸出結(jié)點個數(shù)

intmaxnode(BTNode*b)//輸出結(jié)點的最大值

intlistfloor(BTNode*b,charx)//輸出結(jié)點在第幾層

voidInitStack(SqStack*&s)//初始化棧

voidDestroyStack(SqStack*&s)//銷毀棧

boolStackEmpty(SqStack*s)//推斷棧是否為空

boolPush(SqStack*

system("color00a");

BTNode*b;

inti,n;

charx;

cout>i;

while(i!=0)

{

cout>請輸入你的操作>i;

//以下為功能選擇相應(yīng)的函數(shù)，比較繁雜，在此不做展現(xiàn)

}

}

4.2.2輸入二叉樹

voidCreateBTree(BTNode*

BTNode*St[MaxSize],*p=NULL;

inttop=-1,k=0,j=0;charch=str[j];

b=NULL;

while(ch!='\0'){//str未掃描完時循環(huán)

switch(ch){

case'(':top++;St[top]=p;k=1;break;//可能有左孩子結(jié)點，進(jìn)棧

case')':top--;break;

case',':k=2;break;//后面為右孩子

default:

p=(BTNode*)malloc(sizeof(BTNode));

p->data=ch;

p->lchild=p->rchild=NULL;

if(b==NULL)

b=p;

else{

switch(k){

case1:St[top]->lchild=p;break;

case2:St[top]->rchild=p;break;

}

}

}

j++;

ch=str[j];//連續(xù)掃描str

}

}

4.2.3非遞歸遍歷

voidPreOrder1(BTNode*b)//先序非遞歸遍歷算法

{

BTNode*p;

SqStack*st;//定義一個挨次棧指針st

InitStack(st);//初始化棧st

Push(st,b);//根節(jié)點進(jìn)棧

while(!StackEmpty(st))//棧不為空時循環(huán)

{

Pop(st,p);//退棧節(jié)點p并訪問它

printf("%c",p->data);//訪問節(jié)點p

if(p->rchild!=NULL)//有右孩子時將其進(jìn)棧

Push(st,p->rchild);

if(p->lchild!=NULL)//有左孩子時將其進(jìn)棧

Push(st,p->lchild);

}

printf("\n");

DestroyStack(st);//銷毀棧

}

//中序非遞歸遍歷

voidInOrder1(BTNode*b)//中序非遞歸遍歷算法

{

BTNode*p;

SqStack*st;//定義一個挨次棧指針st

InitStack(st);//初始化棧st

if(b!=NULL)

{

p=b;

while(!StackEmpty(st)||p!=NULL)

{

while(p!=NULL)//掃描節(jié)點p的全部左下節(jié)點并進(jìn)棧

{

Push(st,p);//節(jié)點p進(jìn)棧

p=p->lchild;//移動到左孩子

}

if(!StackEmpty(st))//若棧不空

{

Pop(st,p);//出棧節(jié)點p

printf("%c",p->data);//訪問節(jié)點p

p=p->rchild;//轉(zhuǎn)向處理其右子樹

}

}

printf("\n");

}

DestroyStack(st);//銷毀棧

}

voidPostOrder1(BTNode*b)//后序非遞歸遍歷算法

{

BTNode*p,*r;

boolflag;

SqStack*st;//定義一個挨次棧指針st

InitStack(st);//初始化棧st

p=b;

do

{

while(p!=NULL)//掃描節(jié)點p的全部左下節(jié)點并進(jìn)棧

{

Push(st,p);//節(jié)點p進(jìn)棧

p=p->lchild;//移動到左孩子

}

r=NULL;//r指向剛剛訪問的節(jié)點，初始時為空

flag=true;//flag為真表示正在處理棧頂節(jié)點

while(!StackEmpty(st)//取出當(dāng)前的棧頂節(jié)點p

if(p->rchild==r)//若節(jié)點p的右孩子為空或者為剛剛訪問過的節(jié)點

{

printf("%c",p->data);//訪問節(jié)點p

Pop(st,p);

r=p;//r指向剛訪問過的節(jié)點

}

else

{

p=p->rchild;//轉(zhuǎn)向處理其右子樹

flag=false;//表示當(dāng)前不是處理棧頂節(jié)點

}

}

}while(!StackEmpty(st));//棧不空循環(huán)

printf("\n");

DestroyStack(st);//銷毀棧

}

4.2.4遞歸遍歷

oidPreOrder(BTNode*b)

{

//先序遍歷

if(b!=NULL)

{

coutdata;

PreOrder(b->lchild);

PreOrder(b->rchild);

}

}

voidInOrder(BTNode*b)

{

//中序遍歷

if(b!=NULL)

{

InOrder(b->lchild);

coutdata;

InOrder(b->rchild);

}

}

voidPostOrder(BTNode*b)

{

//后序遍歷

if(b!=NULL)

{

PostOrder(b->lchild);

PostOrder(b->rchild);

coutdata;

}

}

4.3算法的效率分析：

主函數(shù)：函數(shù)中并不包含for循環(huán)、遞歸等簡單的算法，時間簡單度為O（1）；

輸入二叉樹：函數(shù)需要掃描輸入的二叉樹，所以該算法的時間簡單度為O（n）；

非遞歸類遍歷：由于不管是先序遍歷還是中序遍歷以及后序遍歷，我們都需要利用一個幫助棧來進(jìn)行每個節(jié)點的存儲打印，所以每個節(jié)點都要進(jìn)棧和出棧，不過是依據(jù)那種遍歷方式轉(zhuǎn)變的是每個節(jié)點的進(jìn)棧挨次，所以時間簡單度為O(n)，同樣空間簡單度也為O(n)，n為結(jié)點數(shù)；

遞歸類遍歷：空間簡單度與系統(tǒng)堆棧有關(guān)，系統(tǒng)棧需要記住每個節(jié)點的值，所以空間簡單度為O(n)。時間簡單度應(yīng)當(dāng)為O(nlogn)，每個節(jié)點都要遍歷到，需要n次，而且需要將二叉樹劃分logn次，所以遞歸版的遍歷的空間簡單度為O(nlogn)；

層序遍歷：層序遍歷是通過隊列來進(jìn)行每個節(jié)點的存儲打印的，所以時間簡單度和空間簡單度都為O(n)，n為結(jié)點數(shù)。

5.測試

圖5-1初始化菜單

圖5-2輸出二叉樹

圖5-3輸出樹的高度

圖5-4輸出葉子結(jié)點

圖5-5輸出后序遞歸遍歷

圖5-6查找結(jié)點所在層

圖5-7輸出后續(xù)非遞歸遍歷

圖5-8層次遍歷輸出結(jié)構(gòu)

經(jīng)過多次測試與更改，但是無法打破原有的界面格式，使得界面輸出不夠美觀，程序的遞歸與非遞歸先序、中序、后序遍歷、層次遍歷、計算結(jié)點個數(shù)，計算結(jié)點所在層數(shù)等功能基本能夠流暢地實現(xiàn)，達(dá)到了應(yīng)有的要求；不過在輸出二叉樹的時候，不知道為什么后面會多出一個括號，經(jīng)過多次的更改與試驗也沒有將其更改勝利，通過查看相關(guān)書籍以及網(wǎng)上搜尋算法原理，最終明白了錯誤所在，并完成了排錯。

6．課程設(shè)計心得

6.1改進(jìn)方案

對自己的設(shè)計進(jìn)行評價，指出合理和不足之處，提出改進(jìn)方案；

1）菜單設(shè)置方面：運用了if語句，這樣看著沒有條理，不適合用在二叉樹的遍歷上，由于遍歷結(jié)果顯而易見并不非常簡單，沒有必要使程序簡單化，故采納的是程序運行輸出模式。

2）二叉樹的創(chuàng)建：采納二叉鏈表存儲的方式，利用擴(kuò)展先序遍歷實現(xiàn)二叉樹的創(chuàng)建，這樣做相對簡潔，但是對有些狀況下不太有用，所以應(yīng)當(dāng)增加一項依據(jù)后序中序?qū)崿F(xiàn)創(chuàng)建的算法，是程序更加完善。

3）整體布局：由于存在某兩個函數(shù)的制約關(guān)系，要求必需先執(zhí)行A在執(zhí)行B，一旦執(zhí)行挨次錯誤就會導(dǎo)致輸出結(jié)果錯誤。這樣降低了程序的冗錯性，不利于用戶操作，可以通過添加函數(shù)間強制裝換關(guān)系，強制執(zhí)行，或者是在后者運行的函數(shù)中添加必要語句，使其脫離制約函數(shù)的制約。

6.2設(shè)計心得

其實在本程序的設(shè)計過程當(dāng)中，沒有很吸引人的關(guān)鍵技術(shù)，由于本人的C語言或C++語言都不是學(xué)的很好，所以當(dāng)時設(shè)計的時候就只是想把功能都實現(xiàn)就好了，盡可能的把所要求的功能都編進(jìn)程序，這樣就覺得很滿意了。所以都是設(shè)計的比較簡潔易懂的語言，這樣自己能夠更明白一些，所以就沒有時間去細(xì)細(xì)地去設(shè)計自己的程序。本程序要說有什么值得說的，那就只有人性化這點了，在設(shè)計成學(xué)的時候，由于自己怕弄混了，所以添加了很詳盡的提示，這樣在編程的過程中或調(diào)試的時候都能夠比較快的運行。還有就是盡可能的應(yīng)用了do-while語句和switch-case語句，這兩個語句在之前不是很常用，所以在這個程序中試

煉了一下，雖然在編寫的過程中總是出錯，但還是勝利的用好了，也是程序有條理一些。我也知道這些東西別人可能比我弄得還要好，但是我在我所學(xué)的學(xué)問中勝利的應(yīng)用了這些，我覺得就是好事，就是進(jìn)步。唯一的亮點可能就是進(jìn)入系統(tǒng)是的密碼設(shè)計了，就這一點小小的設(shè)計就花了我好幾個小時去調(diào)試，由于總能在后面程序的加入及運行時發(fā)覺一些新的小問題。

一周多的課程設(shè)計，最終勝利的驗收了，雖然有些疲乏，但還是有許多的收獲的，像計算機(jī)組成原理的課設(shè)一樣，我又一次鞏固了所學(xué)到的學(xué)問，之前的學(xué)習(xí)只是停留在理論基礎(chǔ)上，現(xiàn)在自己動手操作試驗后，才是真正的理解及體會。C也學(xué)了近一年，有許多學(xué)問都是似懂非懂，通過平常上機(jī)操作，自己也了解了一些，但讓我有了更深的理解和更好的熟悉，則是在這次的課設(shè)上，之前的困惑也通過這次的課設(shè)解決了一些，雖然還是不能夠全面的理解，但是有進(jìn)步就很興奮。

在課程設(shè)計之前，由于有了綜合試驗的閱歷與教訓(xùn)，明白了寫代碼這一步是特別重要的，由于當(dāng)你把代碼輸進(jìn)去之后，并編譯讓其運行，發(fā)覺通過不了，再來檢查出問題，是很費費勁的事情，因此分析和規(guī)劃代碼是很重要的，最重要的是要把規(guī)律結(jié)構(gòu)寫好，這樣就不會消失大問題，寫代碼就要先找出核心的內(nèi)容，用多種方法來實現(xiàn)核心部分，這樣可以盡可能的避開發(fā)覺規(guī)律或編譯不支持的錯誤。

通過本次論文設(shè)計，我初步學(xué)會了論文設(shè)計的基本方法，學(xué)會了怎樣去借鑒別人的方法和閱歷，知道了如何整合資料和處理這些資料的力量，這為以后做畢設(shè)的論文打下了基礎(chǔ)，使我感覺比較好的是有一種勝利的喜悅，雖然在編譯的時候會常常由于一些小的錯誤而心煩意亂，但是也不失為一件好事，失敗的越多積累的閱歷越豐富，對人的考驗也比較多，那么在最終編譯勝利時的喜悅就越濃烈，也是自己的力量有了進(jìn)一步的提高。由于學(xué)問和閱歷的不足，這個程序編寫的不是很盡如人意，但是融合了自己的心血，就覺得是最好的，所以在以后還是需要較多的努力的，還是會在以后的學(xué)習(xí)過程中不斷地提高和改進(jìn)的。

7．

8．附錄

#include

#include

#include

#include

#include

#include"work.h"

usingnamespacestd;

#defineMaxSize100

usingnamespacestd;

typedefcharElemType;

typedefstructb{

ElemTypedata;

structb*lchild,*rchild;//二叉樹結(jié)構(gòu)聲明

}BTNode;

typedefstruct

{

BTNode*data[100];//存放棧中的數(shù)據(jù)元素

inttop;//存放棧頂指針，即棧頂元素在data數(shù)組中的下標(biāo)

}SqStack;

typedefstruct

{

BTNode*data[MaxSize];//存放隊中元素

intfront,rear;//隊頭隊尾指針

}Sueue;

intwidth[10]={0};//存放各層寬度的數(shù)組

BTNode*LchildNode(BTNode*p)/*返回*p結(jié)點的左孩子結(jié)點指針*/

{

returnp->lchild;

}

BTNode*RchildNode(BTNode*p)/*返回*p結(jié)點的右孩子結(jié)點指針*/

{

returnp->rchild;

}

voidCreateBTree(BTNode*

BTNode*St[MaxSize],*p=NULL;

inttop=-1,k=0,j=0;charch=str[j];

b=NULL;

while(ch!='\0'){//str未掃描完時循環(huán)

switch(ch){

case'(':top++;St[top]=p;k=1;break;//可能有左孩子結(jié)點，進(jìn)棧

case')':top--;break;

case',':k=2;break;//后面為右孩子

default:

p=(BTNode*)malloc(sizeof(BTNode));

p->data=ch;

p->lchild=p->rchild=NULL;

if(b==NULL)

b=p;

else{

switch(k){

case1:St[top]->lchild=p;break;

case2:St[top]->rchild=p;break;

}

}

}

j++;

ch=str[j];//連續(xù)掃描str

}

}

intFindNode(BTNode*b,ElemTypex)

{

intp;

if(b==NULL)

{

returnNULL;

}

elseif(b->data==x)

{

returnx;

}

else

{

p=FindNode(b->lchild,x);

if(p!=NULL)

{

returnp;

}

else

returnFindNode(b->rchild,x);

}

}

///隊列的有關(guān)操作

voidInitQueue(Sueue*

q->front=q->rear=0;

}

//推斷隊列是否為空

boolQueueEmpty(Sueue*q)

{

return(q->front==q->rear);

}

//進(jìn)隊列

boolenQueue(Sueue*q,BTNode*e)

{

if((q->rear+1)%MaxSize==q->front)//隊滿溢出

returnfalse;

q->rear=(q->rear+1)%MaxSize;

q->data[q->rear]=e;

returntrue;

}

//出隊列

booldeQueue(Sueue*

q->front=(q->front+1)%MaxSize;

e=q->data[q->front];

returnfalse;

}

voidDestoryBTree(BTNode*

DestoryBTree(b->rchild);

free(b);

}

}

voidDispBTree(BTNode*b)

{

//輸出單鏈表

if(b!=NULL)

{

coutdatalchild!=NULL||b->rchild!=NULL)

{

coutlchild);

if(b->rchild!=NULL)

coutrchild);

coutlchild);

rchildh=BTHeight(b->rchild);

return(lchildh>rchildh)?

(lchildh+1):(rchildh+1);

}

voidPreOrder(BTNode*b)

{

//先序遍歷

if(b!=NULL)

{

coutdata;

PreOrder(b->lchild);

PreOrder(b->rchild);

}

}

voidInOrder(BTNode*b)

{

//中序遍歷

if(b!=NULL)

{

InOrder(b->lchild);

coutdata;

InOrder(b->rchild);

}

}

voidPostOrder(BTNode*b)

{

//后序遍歷

if(b!=NULL)

{

PostOrder(b->lchild);

PostOrder(b->rchild);

coutdata;

}

}

voidDispLeaf(BTNode*b)

{

//遞歸輸出葉子節(jié)點

if(b!=NULL)

{

if(b->lchild==NULL

DispLeaf(b->lchild);

DispLeaf(b->rchild);

}

}

intlistleaf(BTNode*b)

{

//輸出葉子結(jié)點個數(shù)

intnum1;

if(b==NULL)

return0;

elseif(b->lchild==NULL

num1=listleaf(b->rchild)+listleaf(b->lchild);

returnnum1;

}

intlistnode(BTNode*b)

{

intnum;

if(b==NULL)

return(0);

else

{

num=listnode(b->lchild)+listnode(b->rchild)+1;

}

returnnum;

}

intmaxnode(BTNode*b)

{

if(NULL==b)

return0;

intmaxLeft=maxnode(b->lchild);

intmaxRight=maxnode(b->rchild);

intmax=maxLeft>maxRight?maxLeft:maxRight;

returnmax>b->data?max:b->data;}

intlistfloor(BTNode*b,charx)

{

intnum2,m,n;

if(b==NULL)

num2=0;

elseif(b->data==x)

num2=1;

else

{

m=listfloor(b->lchild,x);

n=listfloor(b->rchild,x);

if(m==0

else

num2=((m>n)?m:n)+1;

}

returnnum2;

}

intLevel(BTNode*b,ElemTypex,inth){

intl;

if(b==NULL)

return(0);

elseif((char)b->data==(char)x)

return(h);

else

{

l=Level(b->lchild,x,h+1);//左子樹中查找

if(l!=0)

return(l);//在左子樹中找到，返回l

else

return(Level(b->rchild,x,h+1));//在左子樹中未找到再在右子樹中查找

}

}

//棧的全部操作如下

voidInitStack(SqStack*//安排一個是挨次?？臻g，首地址存放在s中

s->top=-1;

//棧頂指針置為-1

}

voidDestroyStack(SqStack*

}

boolStackEmpty(SqStack*s)//推斷棧是否為空

{

return(s->top==-1);

}

boolPush(SqStack*

s->top++;//棧頂指針增1

s->data[s->top]=e;

//元素e放在棧頂指針處

returntrue;

}

boolPop(SqStack*

e=s->data[s->top];

//取棧頂指針元素的元素

s->top--;//棧頂指針減1

returntrue;

}

boolGetTop(SqStack*s,BTNode*

e=s->data[s->top];

//取棧頂元素

returntrue;

}

voidPreOrder1(BTNode*b)//先序非遞歸遍歷算法

{

BTNode*p;

SqStack*st;//定義一個挨次棧指針st

InitStack(st);

//初始化棧st

Push(st,b);//根節(jié)點進(jìn)棧

while(!StackEmpty(st))//棧不為空時循環(huán)

{

Pop(st,p);//退棧節(jié)點p并訪問它

printf("%c",p->data);//訪問節(jié)點p

if(p->rchild!=NULL)//有右孩子時將其進(jìn)棧

Push(st,p->rchild);

if(p->lchild!=NULL)//有左孩子時將其進(jìn)棧

Push(st,p->lchild);

}

printf("\n");

DestroyStack(st);//銷毀棧

}

//中序非遞歸遍歷

voidInOrder1(BTNode*b)

//中序非遞歸遍歷算法

{

BTNode*p;

SqStack*st;

//定義一個挨次棧指針st

InitStack(st);

//初始化棧st

if(b!=NULL)

{

p=b;

while(!StackEmpty(st)||p!=NULL)

{

while(p!=NULL)

//掃描節(jié)點p的全部左下節(jié)點并進(jìn)棧

{

Push(st,p);

//節(jié)點p進(jìn)棧

p=p->lchild;

//移動到左孩子

}

if(!StackEmpty(st))

//若棧不空

{

Pop(st,p);

//出棧節(jié)點p

printf("%c",p->data);

//訪問節(jié)點p

p=p->rchild;

//轉(zhuǎn)向處理其右子樹

}

}

printf("\n");

}

DestroyStack(st);//銷毀棧

}

voidPostOrder1(BTNode*b)

//后序非遞歸遍歷算法

{

BTNode*p,*r;

boolflag;

SqStack*st;

//定義一個挨次棧指針st

InitStack(st);

//初始化棧st

p=b;

do

{

while(p!=NULL)

//掃描節(jié)點p的全部左下節(jié)點并進(jìn)棧