二叉樹(shù)中序遍歷

1、課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名： 陳楠 專業(yè)班級(jí)： 軟件zy1202班 指導(dǎo)教師： 夏紅霞 工作單位： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 題 目: 二叉樹(shù)的建立和中序遍歷的演示課程設(shè)計(jì)要求:1、熟練掌握基本的數(shù)據(jù)結(jié)構(gòu)；2、熟練掌握各種算法；3、運(yùn)用高級(jí)語(yǔ)言編寫(xiě)質(zhì)量高、風(fēng)格好的應(yīng)用程序。課程設(shè)計(jì)任務(wù): 1、系統(tǒng)應(yīng)具備的功能：（1）以二叉鏈為存儲(chǔ)結(jié)構(gòu),建立二叉樹(shù)（2）用遞歸算法和非遞歸算法實(shí)現(xiàn)二叉樹(shù)的中序遍歷（3）二叉樹(shù)中序遍歷的演示2、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；3、主要算法設(shè)計(jì)；4、編程及上機(jī)實(shí)現(xiàn)；5、撰寫(xiě)課程設(shè)計(jì)報(bào)告，包括：（1）設(shè)計(jì)題目；（2）摘要和關(guān)鍵字；（3）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)、程序?qū)崿F(xiàn)及

2、測(cè)試、不足之處、設(shè)計(jì)體會(huì)等；（4）結(jié)束語(yǔ)；（5）參考文獻(xiàn)。時(shí)間安排： 2010年7月5日9日 （第19周）7月5日 查閱資料7月6日 系統(tǒng)設(shè)計(jì)，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)7月7日 -8日 編程并上機(jī)調(diào)試7月9日 撰寫(xiě)報(bào)告7月10日 驗(yàn)收程序，提交設(shè)計(jì)報(bào)告書(shū)。 指導(dǎo)教師簽名： 2010年7月4日 系主任（或責(zé)任教師）簽名： 2010年7月4日 二叉樹(shù)的建立和中序遍歷的演示摘要： 該程序用先序遞歸的方式建立二叉樹(shù)，然后采用遞歸和非遞歸的方法中序遍歷二叉樹(shù)關(guān)鍵字： 二叉樹(shù) 中序遍歷 遞歸 非遞歸一 需求分析： 優(yōu)化復(fù)雜遞歸，提高程序效率，快速查找，插入刪除，實(shí)現(xiàn)簡(jiǎn)單而相當(dāng)有效的數(shù)據(jù)壓縮算法 ，編譯器設(shè)計(jì)

3、的核心數(shù)據(jù)結(jié)構(gòu) 。二 算法設(shè)計(jì)：#include#include#define MAX_STACK 20 /*初始化棧的最大長(zhǎng)度*/#define INCREMENT 10 /*每次棧的增量*/typedef int ElemType;#define INT/*-定義數(shù)據(jù)結(jié)構(gòu)-*/*-定義樹(shù)的節(jié)點(diǎn)-*/typedef struct BiNode ElemType data; struct BiNode *lchild,*rchild; BiNode,*BTNode;/*-定義棧-*/typedef struct Stack int stacksize;/*棧的總長(zhǎng)度*/ BTNode base

4、,top;Stack,*BiStack;/*-棧的一些基本操作-*/*-初始化棧*/void InitStack(BiStack stack) stack-base=(BTNode)malloc(sizeof(BiNode)*MAX_STACK); if(!stack-base) printf(1.Memory allocation failed!n); exit(0); stack-top=stack-base; stack-stacksize=MAX_STACK; /*-插入數(shù)據(jù)元素*/void Push(BiStack stack,BTNode TreeNode) if(stack-to

5、p-stack-base)=stack-stacksize)/*當(dāng)棧滿時(shí)重新增加內(nèi)存*/ stack-stacksize+=INCREMENT; stack-base=(BTNode)realloc(stack-base,sizeof(BiNode)*stack-stacksize); if(!stack-base) printf(2.Memory allocation failed!n); exit(0); stack-top-data=TreeNode-data; stack-top-lchild=TreeNode-lchild; stack-top-rchild=TreeNode-rch

6、ild; +stack-top;/*-刪除數(shù)據(jù)元素*/void Pop(BiStack stack,BTNode *TreeNode) if(stack-top=stack-base) printf(The Stack is Empty!n); return ; *TreeNode=stack-top; -stack-top;/*-判斷棧是否為空*/int IsEmpty(Stack stack)/*當(dāng)棧是空時(shí)，返回1，否則返回0*/ if(stack.top=stack.base) return 1; else return 0;/*-創(chuàng)建二叉樹(shù)-*/void InitTree(BTNode

7、 *bitree) /*初始化二叉樹(shù)根節(jié)點(diǎn)*/ *bitree=NULL; void CreateTree(BTNode *bitree) /*創(chuàng)建二叉樹(shù)*/*采用先序遞歸遍歷的方式建立二叉樹(shù)*/ ElemType data; #ifdef INT scanf(%d,&data); if(data=0) #endif #ifdef FLOAT scanf(%f,&data); if(data=0.0) #endif #ifdef CHAR scanf(%c,&data); if(data= )/*當(dāng)為空格時(shí)認(rèn)為無(wú)左或右孩子*/ #endif *bitree=NULL; else *bitree

8、=(BTNode)malloc(sizeof(BiNode); if(!*bitree) printf(4.Memory allocation failed!n); exit(1); (*bitree)-data=data; CreateTree(&(*bitree)-lchild); CreateTree(&(*bitree)-rchild); /*-訪問(wèn)樹(shù)的節(jié)點(diǎn)-*/int print(ElemType data)/*輸出樹(shù)的每個(gè)節(jié)點(diǎn)的詳細(xì)信息*/ #ifdef INT printf(%d ,data); /printf(The tree nodes details is :%dn,dat

9、a); #endif #ifdef FLOAT printf(The tree nodes details is :%fn,data); #endif #ifdef CHAR printf(The tree nodes details is :%cn,data); #endif return 1;/*-中序遍歷二叉樹(shù)-*/*遞歸中序遍歷二叉樹(shù)*/void InorderTraverse(BTNode bitree,int (*Visit)(ElemType data) if(bitree) InorderTraverse(bitree-lchild,Visit); Visit(bitree-d

10、ata); InorderTraverse(bitree-rchild,Visit); /*非遞歸中序遍歷二叉樹(shù)*/void InorderTraverse1(BTNode bitree,int (*Visit)(ElemType data) BTNode p; Stack stack; InitStack(&stack);/*初始化棧*/ while(p|!IsEmpty(stack) if(p) /*若當(dāng)前子樹(shù)非空，則將其根保存并訪問(wèn)左子樹(shù)*/ Push(&stack,p); p=p-lchild;/*一直找到樹(shù)的最左邊*/ else Pop(&stack,&p); Visit(p-dat

11、a); p=p-rchild; /*-主函數(shù)-*/int main(void) BTNode bitree; InitTree(&bitree);/*初始化根節(jié)點(diǎn)*/ printf(-整型和浮點(diǎn)型以0表示空，字符以空格表示空-n); printf(Input the tree node data:n); CreateTree(&bitree);/*創(chuàng)建二叉樹(shù)*/ printf(中序遍歷（遞歸） :n); InorderTraverse(bitree,print);/*遞歸中序遍歷二叉樹(shù)*/ printf(n); printf(中序遍歷（非遞歸） :n); InorderTraverse(bit

12、ree,print);/*非遞歸中序遍歷二叉樹(shù)*/ printf(n); return 1;三 程序運(yùn)行結(jié)果：四 不足之處： 雖然程序能正確的運(yùn)行和輸出結(jié)果了，但由于時(shí)間緊迫，程序設(shè)計(jì)的時(shí)候考慮的不太全面，導(dǎo)致程序設(shè)計(jì)時(shí)較為冗長(zhǎng)和繁雜，代碼不夠優(yōu)化。而且，手動(dòng)輸入數(shù)據(jù)比較麻煩，可以改為更為簡(jiǎn)單的讀取文本或數(shù)據(jù)庫(kù)的方法來(lái)取代手動(dòng)輸入。五 設(shè)計(jì)體會(huì)：經(jīng)過(guò)這些時(shí)日的設(shè)計(jì)，調(diào)試與運(yùn)行，很好的鍛煉了我的編程能力，主要是經(jīng)過(guò)對(duì)實(shí)際問(wèn)題的編程訓(xùn)練，大大拓寬了我的思路，不再拘泥于書(shū)上的一些算法，可以自己總結(jié)比較一些其他的算法，對(duì)自己編程思想的鍛煉起了很大的作用。亦提升了自己對(duì)計(jì)算機(jī)的興趣，對(duì)將來(lái)的更深遠(yuǎn)的學(xué)習(xí)無(wú)疑是有利的。六 結(jié)束語(yǔ)： 充分利用前序遍歷的特點(diǎn)，就可以生成二叉樹(shù)。如果把前序換成層序，算法不用改動(dòng)，若換成后序，只需將