數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-二叉樹的遍歷

1、. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 課程名稱：二叉樹的遍歷 學(xué)院：*學(xué)院 專業(yè)： 班級： 姓名： 學(xué)號： 指導(dǎo)教師： 實驗時間：二叉樹及其遍歷方法【問題描述】用遞歸和非遞歸兩種方法創(chuàng)建一棵二叉樹，并對它們進(jìn)行先序遍歷、中序遍歷、后序遍歷及層次遍歷，并求出該二叉樹的深度和葉子結(jié)點(diǎn)數(shù)、輸入一個結(jié)點(diǎn)查找該結(jié)點(diǎn)的雙親、祖先及左右孩子結(jié)點(diǎn)?！净疽蟆浚?） 用遞歸和非遞歸兩種方法創(chuàng)建一棵二叉樹。（2） 用遞歸和非遞歸兩種方法，對二叉樹進(jìn)行先序遍歷、中序遍歷、后序遍歷及層次遍歷。（3） 求出該二叉樹的深度和葉子結(jié)點(diǎn)數(shù)。（4） 輸入一個結(jié)點(diǎn)查找該結(jié)點(diǎn)的雙親、祖先及左右孩子結(jié)點(diǎn)。（5） 寫出課程設(shè)計報告【測試數(shù)據(jù)】選

2、定兩組測試數(shù)據(jù)進(jìn)行測試，驗證程序的正確性。程序的調(diào)試分析 主菜單 遞歸創(chuàng)建二叉樹 遍歷二叉樹 查找功能 非遞歸創(chuàng)建非遞歸遍歷心得體會：通過設(shè)計遍歷二叉樹，讓我懂得了遞歸創(chuàng)建和非遞歸創(chuàng)建二叉樹等有關(guān)二叉樹的基本知識，通過這次編程實現(xiàn)二叉樹的遍歷等問題，讓我的動手能力增加了，以及在變成的過程中讓我懂得了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)需要動手，不能光看書就能知道各種存儲結(jié)構(gòu)。 在這次編程中，我通過查閱書本以及請教別人，讓我受益匪淺，讓我對數(shù)據(jù)結(jié)構(gòu)有了新的認(rèn)知。.;#include <stdio.h>#include<malloc.h>#include<stdlib.h>typede

3、f int Data;typedef struct SNodeData nData;struct SNode *LChild,*RChild;SNode,*bitree,bitnode ;typedef structbitree link;int flag; stacktype;SNode *pTree;int Menu();int Search_Menu();int Sub_Recu_Menu();int Sub_Unrecu_Menu();void InitTree(SNode *p);int Depth_Tree(SNode *p);int Leaf_Tree(SNode *p);Dat

4、a Parent_Tree(SNode* p,Data data);Data LChild_Tree(SNode* p,Data data);Data RChild_Tree(SNode* p,Data data);bool Ancest_Tree(SNode* p, int data);SNode * ReCu_Create(SNode *&p);void PreOrder(SNode *p);void InOrder(SNode *p);void LaterOrder(SNode *p);bitnode * create(bitnode *T);void preorder(bitn

5、ode *T);void inorder(bitnode *T);void lateorder(bitnode *T);void levelorder(bitree T);int main(int argc, char* argv)InitTree(pTree);while( Menu() );return 0;void InitTree(SNode *p)p = NULL;int Menu()Data i;char c = 0;puts(" ");puts(" ");puts(" ");puts(" ");put

6、s(" *歡迎構(gòu)造二叉樹* ");puts(" ");puts(" ");puts(" ");puts(" ");puts(" 1、選擇遞歸創(chuàng)建二叉樹");puts(" 2、選擇非遞歸創(chuàng)建二叉樹");puts(" 0、退出");scanf("%d",&i);doswitch(i)case 1:ReCu_Create(pTree);while( Sub_Recu_Menu();break;case 2:pTre

7、e = create(pTree);while( Sub_Unrecu_Menu();break;case 0:exit(0);default:return 0;printf(" 請選擇：n");puts(" 1、選擇遞歸創(chuàng)建二叉樹");puts(" 2、選擇非遞歸創(chuàng)建二叉樹");puts(" 0、結(jié)束系統(tǒng)");fflush(stdin);if(i = 0)exit(0);scanf("%d",&i);switch(i)case 1:c = 'y'break;case 2

8、:c = 'y'break;default:break;while(c != 'N' && c != 'n');return 0;int Sub_Recu_Menu()system("cls");Data i;puts(" ");puts(" ");puts(" ");puts(" ");puts(" 1、選擇先序遍歷二叉樹");puts(" 2、選擇中序遍歷二叉樹");puts("

9、 3、選擇后序遍歷二叉樹");puts(" 4、選擇層次遍歷二叉樹");puts(" 5、選擇對比先序、中序、后序、層次遍歷二叉樹");puts(" 6、輸出該二叉樹的深度");puts(" 7、輸出該二叉樹的葉子結(jié)點(diǎn)數(shù)");puts(" 8、進(jìn)行查找");puts(" 0、返回上一級");scanf("%d",&i);char c = 0;doswitch(i)case 0:return 0;case 1:PreOrder(pTree)

10、;puts("");system("pause");break;case 2:InOrder(pTree);puts("");system("pause");break;case 3:LaterOrder(pTree);puts("");system("pause");break;case 4:levelorder(pTree);puts("");system("pause");break;case 5:PreOrder(pTree);

11、puts("");InOrder(pTree);puts("");LaterOrder(pTree);puts("");levelorder(pTree);puts("");system("pause");break;case 6:printf("%dn",Depth_Tree(pTree);system("pause");break;case 7:printf("%dn",Leaf_Tree(pTree);system("p

12、ause");break;case 8:while( Search_Menu() );puts("");system("pause");break;default:break;system("cls");printf(" 請選擇：n");puts(" 1、選擇先序遍歷二叉樹");puts(" 2、選擇中序遍歷二叉樹");puts(" 3、選擇后序遍歷二叉樹");puts(" 4、選擇層次遍歷二叉樹");puts("

13、5、選擇對比先序、中序、后序、層次遍歷二叉樹");puts(" 6、輸出該二叉樹的深度");puts(" 7、輸出該二叉樹的葉子結(jié)點(diǎn)數(shù)");puts(" 8、進(jìn)行查找");puts(" 0、返回上一級");fflush(stdin);if(i = 0)exit(0);scanf("%d",&i);switch(i)case 1:c = 'y'break;case 2:c = 'y'break;case 3:c = 'y'break

14、;case 4:c = 'y'break;case 5:c = 'y'break;case 6:c = 'y'break;case 7:c = 'y'break;case 8:c = 'y'break;default:break;while(c != 'N' && c != 'n');return 0;int Sub_Unrecu_Menu()system("cls");Data i;puts(" ");puts("

15、");puts(" ");puts(" ");puts(" 1、選擇先序遍歷二叉樹");puts(" 2、選擇中序遍歷二叉樹");puts(" 3、選擇后序遍歷二叉樹");puts(" 4、選擇層次遍歷二叉樹");puts(" 5、選擇對比先序、中序、后序、層次遍歷二叉樹");puts(" 6、輸出該二叉樹的深度");puts(" 7、輸出該二叉樹的葉子結(jié)點(diǎn)數(shù)");puts(" 8、進(jìn)行查找&qu

16、ot;);puts(" 0、直接退出");scanf("%d",&i);char c = 0;doswitch(i)case 0:exit(0);case 1:preorder(pTree);puts("");system("pause");break;case 2:inorder(pTree);puts("");system("pause");break;case 3:lateorder(pTree);puts("");system("

17、pause");break;case 4:levelorder(pTree);puts("");system("pause");break;case 5:preorder(pTree);puts("");inorder(pTree);puts("");lateorder(pTree);puts("");levelorder(pTree);puts("");system("pause");break;case 6:printf("%dn&

18、quot;,Depth_Tree(pTree);system("pause");break;case 7:printf("%dn",Leaf_Tree(pTree);system("pause");break;case 8:while( Search_Menu() );puts("");system("pause");break;default:break;system("cls");printf(" 請選擇：n");puts(" 1、選擇先序遍

19、歷二叉樹");puts(" 2、選擇中序遍歷二叉樹");puts(" 3、選擇后序遍歷二叉樹");puts(" 4、選擇層次遍歷二叉樹");puts(" 5、選擇對比先序、中序、后序、層次遍歷二叉樹");puts(" 6、輸出該二叉樹的深度");puts(" 7、輸出該二叉樹的葉子結(jié)點(diǎn)數(shù)");puts(" 8、進(jìn)行查找");puts(" 0、返回上一級");fflush(stdin);scanf("%d",

20、&i);switch(i)case 0:exit(0);case 1:c = 'y'break;case 2:c = 'y'break;case 3:c = 'y'break;case 4:c = 'y'break;case 5:c = 'y'break;case 6:c = 'y'break;case 7:c = 'y'break;case 8:c = 'y'break;default:break;while(c != 'N' &&a

21、mp; c != 'n');return 0;/雙親或者左右孩子結(jié)點(diǎn)為空時顯示為0int Search_Menu()system("cls");char c = 0;Data i,data;doputs(" ");puts(" ");puts(" ");puts(" ");puts(" 1、查找該結(jié)點(diǎn)的雙親");puts(" 2、查找該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)");puts(" 3、查找該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)");puts(&quo

22、t; 4、查找該結(jié)點(diǎn)的祖先各節(jié)點(diǎn)");scanf("%d",&i);puts("請輸入一個結(jié)點(diǎn):t");scanf("%d",&data);switch(i)case 1:printf("雙親是：t%dn",Parent_Tree(pTree,data);system("pause");break;case 2:printf("左孩子是：t%dn",LChild_Tree(pTree,data) );system("pause")

23、;break;case 3:printf("右孩子是：t%dn",RChild_Tree(pTree,data) );system("pause");break;case 4:Ancest_Tree(pTree,data);system("pause");default:break;puts("請選擇是否繼續(xù)查找【y/n】"); puts(" 選擇0 直接退出系統(tǒng)");fflush(stdin);scanf("%c",&c);if(c = '0')ex

24、it(0);while(c != 'N' && c != 'n');return 0;/*公共操作*int Depth_Tree(SNode *p)int deep=0;if(p)int lchilddeep=Depth_Tree(p ->LChild);int rchilddeep=Depth_Tree(p ->RChild);deep=lchilddeep>=rchilddeep?lchilddeep+1:rchilddeep+1;return deep;int Leaf_Tree(SNode *p)if(!p) retur

25、n 0;else if(p ->LChild = NULL && p ->RChild = NULL) return 1;else return Leaf_Tree(p ->LChild ) + Leaf_Tree(p ->RChild );Data Parent_Tree(SNode* p,Data data)if(p)if( (p ->LChild && (p ->LChild ->nData = data) |(p ->RChild && (p ->RChild ->nData =

26、data) )return p ->nData ;elseParent_Tree(p ->LChild ,data);Parent_Tree(p ->RChild ,data);return 0;Data LChild_Tree(SNode* p,Data data)Data m;if(p)if( (p ->LChild) && (p ->nData = data) )m = p ->LChild ->nData ;elseLChild_Tree(p ->LChild ,data);LChild_Tree(p ->RChil

27、d ,data);return m;return 0;Data RChild_Tree(SNode* p,Data data)Data m;if(p)if( (p ->RChild ) && (p ->nData = data) )m = p ->RChild ->nData ;elseLChild_Tree(p ->LChild ,data);LChild_Tree(p ->RChild ,data);return m;return 0;bool Ancest_Tree(SNode* p, int data) if(p = NULL) re

28、turn false; if(p->nData = data) return true; if( Ancest_Tree(p ->LChild, data) | Ancest_Tree(p ->RChild, data) ) printf("%dt",p ->nData); return true; return false; /*以下是有關(guān)遞歸的一些操作*SNode* ReCu_Create(SNode* &p)Data nData = 0;printf("請輸入一個數(shù)據(jù): ");scanf("%d"

29、,&nData);if(nData = 0)p = 0;elsep = (SNode *)malloc(sizeof(SNode);if(!p)exit(0);p ->nData = nData;ReCu_Create(p ->LChild);ReCu_Create(p ->RChild);return p;void PreOrder(SNode *p)if(!p)return ;elseprintf("%dt",p ->nData); PreOrder(p ->LChild);PreOrder(p ->RChild);void

30、InOrder(SNode *p)if(!p)return ;elseInOrder(p ->LChild);printf("%dt",p ->nData);InOrder(p ->RChild);void LaterOrder(SNode *p)if(!p)return ;elseLaterOrder(p ->LChild);LaterOrder(p ->RChild);printf("%dt",p ->nData); /*以下是非遞歸有關(guān)的操作*bitnode * create(bitnode *T)bitree

31、s20;bitree q;int i,j,x; i=1;printf("i,x=");scanf("%d%d",&i,&x);while(i!=0)q=(bitnode *)malloc(sizeof(bitnode);q ->nData=x;q ->LChild=NULL;q ->RChild=NULL;si=q ;if(i=1) T=q;elsej=i/2;if(i%2=0) sj ->LChild = q;elsesj ->RChild = q;printf("i,x=");scanf("%d%d",&i,&x);return T;void preorder(bitnode *T)bitr