數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉樹的基本操作

1、.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目：二叉樹的基本操作專業(yè)：計(jì)算機(jī)科技院系：計(jì)算機(jī)學(xué)院姓名： xx xx學(xué)號(hào)： xxxxxxxx時(shí)間：2013年9月22日目錄一、 設(shè)計(jì)要求-31. 問題描述-32. 需求分析-3二、 詳細(xì)設(shè)計(jì)-31. 概要設(shè)計(jì)-32. 各模塊源代碼-3三、 用戶手冊(cè)-9四、 總結(jié)-10一、 設(shè)計(jì)要求1. 問題描述設(shè)計(jì)一個(gè)與二叉樹基本操作相關(guān)的演示程序。2. 需求分析（1） 創(chuàng)建二叉樹。按照用戶需要構(gòu)建二叉樹（2） 分別以先序、中序、后序遍歷二叉樹（3） 查找子節(jié)點(diǎn)元素二、 詳細(xì)設(shè)計(jì)（附源代碼）1. 概要設(shè)計(jì)/定義二叉樹數(shù)據(jù)結(jié)構(gòu)typedef struct TNodeint num

2、;struct TNode *lchild, *rchild;TNode;2各模塊源代碼（包含main( )函數(shù)）#include<stdio.h>#include<stdlib.h>#define MaxLength 100/定義二叉樹數(shù)據(jù)結(jié)構(gòu)typedef struct TNodeint num;struct TNode *lchild, *rchild;TNode;/聲明全局變量rootstatic TNode *root=NULL;/聲明插入新結(jié)點(diǎn)的函數(shù)(根非空)int myInsert_Node(TNode *p, int n);/定義插入新節(jié)點(diǎn)的初始函數(shù)，拆

3、開寫的目的是遞歸時(shí)避免不必要的判斷void Insert_Node(int n)if(root=NULL) /如果根結(jié)點(diǎn)不存在則創(chuàng)建root=(TNode *)malloc(sizeof(TNode);root->num=n;root->lchild=NULL;root->rchild=NULL;elsemyInsert_Node(root, n);/非根結(jié)點(diǎn)的插入操作int myInsert_Node(TNode *p, int n)TNode *temp;if(n<p->num) /比當(dāng)前結(jié)點(diǎn)小，則訪問左子樹if(p->lchild=NULL) /左子樹

4、為空，則插入該結(jié)點(diǎn)temp=(TNode *)malloc(sizeof(TNode);temp->num=n;temp->lchild=NULL;temp->rchild=NULL;p->lchild=temp;return 0;else /左子樹不為空，則與左子樹進(jìn)行比較myInsert_Node(p->lchild,n);else /右子樹同理if(p->rchild=NULL)temp=(TNode *)malloc(sizeof(TNode);temp->num=n;temp->lchild=NULL;temp->rchild=N

5、ULL;p->rchild=temp;return 0;elsemyInsert_Node(p->rchild,n);/前序遞歸遍歷二叉樹void Pre_travel(TNode *p)if(p)printf("%d ",p->num);Pre_travel(p->lchild);Pre_travel(p->rchild);/中序遞歸遍歷二叉樹void Mid_travel(TNode *p)if(p)Mid_travel(p->lchild);printf("%d ",p->num);Mid_travel(p

6、->rchild);/后序遞歸遍歷二叉樹void Suf_travel(TNode *p)if(p)Suf_travel(p->lchild);Suf_travel(p->rchild);printf("%d ", p->num);/中序非遞歸遍歷二叉樹/*從根節(jié)點(diǎn)開始，沿左子樹一直走到?jīng)]有左孩子的節(jié)點(diǎn)為止，并將所經(jīng)過的節(jié)點(diǎn)的地址進(jìn)棧； 當(dāng)找到?jīng)]有左孩子的節(jié)點(diǎn)時(shí)，從棧頂退出該節(jié)點(diǎn)并訪問它，此時(shí)，此節(jié)點(diǎn)的左子樹已訪問完畢； 在用上述方法遍歷該節(jié)點(diǎn)的右子樹，如此重復(fù)到棧空為止。*/void NRMid_travel(TNode *bitree)TNode

7、 *stackMaxLength;TNode *p;int top=-1;p=bitree;dowhile(p!=NULL)stack+top=p;p=p->lchild;if(top!=-1)p=stacktop-;printf("%d ", p->num);p=p->rchild;while(top!=-1|p!=NULL);/釋放分配的空間，防止內(nèi)存泄露。/此處的root為靜態(tài)區(qū)root的拷貝，root需要單獨(dú)賦空值。void Free_node(TNode *p)if(p)Free_node(p->lchild);Free_node(p-&g

8、t;rchild);free(p);p=NULL;/層次遍歷二叉樹void Level_travel(TNode *bitree)int i,j;TNode *arrayMaxLength, *temp;/建立一個(gè)先入先出的隊(duì)列array,j標(biāo)識(shí)隊(duì)列增長,i控制輸出temp=bitree;if(temp!=NULL)/初始化變量i=0;arrayi=temp;j=1;while(i!=j)temp=arrayi;/控制層次遍歷順序printf("%d ", temp->num);if(temp->lchild!=NULL)arrayj=temp->lchi

9、ld;/左子樹存在，入隊(duì)列j+;if(temp->rchild!=NULL)arrayj=temp->rchild;/右子樹存在，入隊(duì)列j+;i+;/聲明核心查找函數(shù)int myNode_search(TNode *p, int key);/二叉樹的查找，拆開寫的目的是遞歸時(shí)避免不必要的判斷int Node_search(int key)if(root=NULL)return 0;elseif(key=root->num)return 1;elsereturn myNode_search(root, key);int myNode_search(TNode *p, int k

10、ey) /printf("p.num:%d key:%dn",p->num,key);if(key=p->num)return 1;elseif(key<p->num)if(p->lchild!=NULL)return myNode_search(p->lchild, key);elsereturn 0;elseif(p->rchild!=NULL)return myNode_search(p->rchild, key);elsereturn 0;int main()system("cls");system

11、("color 1f");system("mode con: cols=78 lines=35");printf("n");printf(" 必做題6：樹結(jié)構(gòu)的應(yīng)用 n");printf(" 姓名：xxxxx n");printf(" 學(xué)號(hào)：xxxxxxxxxxx n");printf("n");int sum, i, key;int dataMaxLength;printf(" 請(qǐng)輸入二叉樹結(jié)點(diǎn)總數(shù): ");scanf("%

12、d",&sum);printf(" 請(qǐng)依次輸入結(jié)點(diǎn)數(shù)值大小(以空格或者回車隔開):n");for(i=0;i<sum;i+)scanf("%d", &datai);for(i=0;i<sum;i+)Insert_Node(datai);printf(" 先序遞歸遍歷后的結(jié)果為:n");Pre_travel(root);printf("n 中序遞歸遍歷后的結(jié)果為:n");Mid_travel(root);printf("n 后序遞歸遍歷后的結(jié)果為:n");Su

13、f_travel(root);printf("n 中序非遞歸遍歷后的結(jié)果為:n");NRMid_travel(root);printf("n 層次遍歷后的結(jié)果為:n");Level_travel(root);/為便于測(cè)試，多次查找一下printf("n 請(qǐng)輸入要查找的關(guān)鍵字(數(shù)字,非數(shù)字時(shí)終止):n");while(scanf("%d", &key)/scanf("%d", &key);if(Node_search(key)printf(" 該關(guān)鍵字存在！n");elseprintf(" 該關(guān)鍵字不存在！n");/釋放內(nèi)存Free_node(root);root = NULL;return 0;三、 用戶手冊(cè)（調(diào)試演示）包含主界面顯示，當(dāng)我們輸入結(jié)點(diǎn)總