1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)</b></p><p><b>　　課程設(shè)計(jì)報告</b></p><p>　　設(shè)計(jì)題目：二叉樹的基本操作</p><p><b>　　專業(yè)：計(jì)算機(jī)科技</b></p><p><b>　　院系：計(jì)算機(jī)學(xué)院</b>&l

2、t;/p><p>　　姓名： xx xx</p><p>　　學(xué)號： xxxxxxxx</p><p>　　時間：2013年9月22日</p><p><b>　　目錄</b></p><p>　　設(shè)計(jì)要求-------------------------------------------

3、------------3</p><p>　　問題描述----------------------------------------------------3</p><p>　　需求分析----------------------------------------------------3</p><p>　　詳細(xì)設(shè)計(jì)--------------------

4、------------------------------------3</p><p>　　概要設(shè)計(jì)-----------------------------------------------------3</p><p>　　各模塊源代碼-----------------------------------------------3</p><p>　　用戶

5、手冊--------------------------------------------------------9</p><p>　　總結(jié)-------------------------------------------------------------10</p><p><b>　　設(shè)計(jì)要求</b></p><p><b&

6、gt;　　問題描述</b></p><p>　　設(shè)計(jì)一個與二叉樹基本操作相關(guān)的演示程序。</p><p><b>　　需求分析</b></p><p>　　創(chuàng)建二叉樹。按照用戶需要構(gòu)建二叉樹</p><p>　　分別以先序、中序、后序遍歷二叉樹</p><p><b>　　查

7、找子節(jié)點(diǎn)元素</b></p><p>　　詳細(xì)設(shè)計(jì)（附源代碼）</p><p><b>　　概要設(shè)計(jì)</b></p><p>　　//定義二叉樹數(shù)據(jù)結(jié)構(gòu)</p><p>　　typedef struct TNode</p><p><b>　　{</b></

8、p><p><b>　　int num;</b></p><p>　　struct TNode *lchild, *rchild;</p><p><b>　　}TNode;</b></p><p>　　2．各模塊源代碼（包含main( )函數(shù)）</p><p>　　#inclu

9、de<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define MaxLength 100</p><p>　　//定義二叉樹數(shù)據(jù)結(jié)構(gòu)</p><p>　　typedef struct TNode</p><p><b>　　{&l

10、t;/b></p><p><b>　　int num;</b></p><p>　　struct TNode *lchild, *rchild;</p><p><b>　　}TNode;</b></p><p>　　//聲明全局變量root</p><p>　　st

11、atic TNode *root=NULL;</p><p>　　//聲明插入新結(jié)點(diǎn)的函數(shù)(根非空)</p><p>　　int myInsert_Node(TNode *p, int n);</p><p>　　//定義插入新節(jié)點(diǎn)的初始函數(shù)，拆開寫的目的是遞歸時避免不必要的判斷</p><p>　　void Insert_Node(int

12、n)</p><p><b>　　{</b></p><p>　　if(root==NULL) //如果根結(jié)點(diǎn)不存在則創(chuàng)建</p><p><b>　　{</b></p><p>　　root=(TNode *)malloc(sizeof(TNode));</p><p>　

13、　root->num=n;</p><p>　　root->lchild=NULL;</p><p>　　root->rchild=NULL;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b&

14、gt;　　{</b></p><p>　　myInsert_Node(root, n);//非根結(jié)點(diǎn)的插入操作</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　int myInsert_Node(TNode *p, int n)<

15、/p><p><b>　　{</b></p><p>　　TNode *temp;</p><p>　　if(n<p->num) //比當(dāng)前結(jié)點(diǎn)小，則訪問左子樹</p><p><b>　　{</b></p><p>　　if(p->lchild==NULL)

16、//左子樹為空，則插入該結(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　temp=(TNode *)malloc(sizeof(TNode));</p><p>　　temp->num=n;</p><p>　　temp->lchild=NULL;</p><p>　

17、　temp->rchild=NULL;</p><p>　　p->lchild=temp;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　else //左子樹不為空，則與左子樹進(jìn)行比較</p><p

18、><b>　　{</b></p><p>　　myInsert_Node(p->lchild,n);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　else //右子樹同理</p><p>

19、;<b>　　{</b></p><p>　　if(p->rchild==NULL)</p><p><b>　　{</b></p><p>　　temp=(TNode *)malloc(sizeof(TNode));</p><p>　　temp->num=n;</p>

20、<p>　　temp->lchild=NULL;</p><p>　　temp->rchild=NULL;</p><p>　　p->rchild=temp;</p><p><b>　　return 0;</b></p><p><b>　　}</b></p>

21、;<p><b>　　else</b></p><p><b>　　{</b></p><p>　　myInsert_Node(p->rchild,n);</p><p><b>　　}</b></p><p><b>　　}</b>&

22、lt;/p><p><b>　　}</b></p><p>　　//前序遞歸遍歷二叉樹</p><p>　　void Pre_travel(TNode *p)</p><p><b>　　{</b></p><p><b>　　if(p)</b></p

23、><p><b>　　{</b></p><p>　　printf("%d ",p->num);</p><p>　　Pre_travel(p->lchild);</p><p>　　Pre_travel(p->rchild);</p><p><b>

24、　　}</b></p><p><b>　　}</b></p><p>　　//中序遞歸遍歷二叉樹</p><p>　　void Mid_travel(TNode *p)</p><p><b>　　{</b></p><p><b>　　if(p)&l

25、t;/b></p><p><b>　　{</b></p><p>　　Mid_travel(p->lchild);</p><p>　　printf("%d ",p->num);</p><p>　　Mid_travel(p->rchild);</p><

26、p><b>　　}</b></p><p><b>　　}</b></p><p>　　//后序遞歸遍歷二叉樹</p><p>　　void Suf_travel(TNode *p)</p><p><b>　　{</b></p><p><

27、b>　　if(p)</b></p><p><b>　　{</b></p><p>　　Suf_travel(p->lchild);</p><p>　　Suf_travel(p->rchild);</p><p>　　printf("%d ", p->num);&

28、lt;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//中序非遞歸遍歷二叉樹</p><p><b>　　/*</b></p><p>　　從根節(jié)點(diǎn)開始，沿左子樹一直走到?jīng)]有左孩子的節(jié)點(diǎn)為止，并將所經(jīng)過的節(jié)

29、點(diǎn)的地址進(jìn)棧；</p><p>　　當(dāng)找到?jīng)]有左孩子的節(jié)點(diǎn)時，從棧頂退出該節(jié)點(diǎn)并訪問它，此時，此節(jié)點(diǎn)的左子樹已訪問完畢；</p><p>　　在用上述方法遍歷該節(jié)點(diǎn)的右子樹，如此重復(fù)到?？諡橹?。</p><p><b>　　*/</b></p><p>　　void NRMid_travel(TNode *bitree)

30、</p><p><b>　　{</b></p><p>　　TNode *stack[MaxLength];</p><p><b>　　TNode *p;</b></p><p>　　int top=-1;</p><p><b>　　p=bitree;<

31、/b></p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p>　　stack[++top]=p;</p>

32、;<p>　　p=p->lchild;</p><p><b>　　}</b></p><p>　　if(top!=-1)</p><p><b>　　{</b></p><p>　　p=stack[top--];</p><p>　　printf(&qu

33、ot;%d ", p->num);</p><p>　　p=p->rchild;</p><p><b>　　}</b></p><p>　　}while(top!=-1||p!=NULL);</p><p><b>　　}</b></p><p>　　

34、//釋放分配的空間，防止內(nèi)存泄露。</p><p>　　//此處的root為靜態(tài)區(qū)root的拷貝，root需要單獨(dú)賦空值。</p><p>　　void Free_node(TNode *p)</p><p><b>　　{</b></p><p><b>　　if(p)</b></p>

35、<p><b>　　{</b></p><p>　　Free_node(p->lchild);</p><p>　　Free_node(p->rchild);</p><p><b>　　free(p);</b></p><p><b>　　p=NULL;<

36、/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//層次遍歷二叉樹</b></p><p>　　void Level_travel(TNode *bitree)</p><p>&

37、lt;b>　　{</b></p><p><b>　　int i,j;</b></p><p>　　TNode *array[MaxLength], *temp;//建立一個先入先出的隊(duì)列array,j標(biāo)識隊(duì)列增長,i控制輸出</p><p>　　temp=bitree;</p><p>　　if(te

38、mp!=NULL)//初始化變量</p><p><b>　　{</b></p><p><b>　　i=0;</b></p><p>　　array[i]=temp;</p><p><b>　　j=1;</b></p><p><b>　　

39、}</b></p><p>　　while(i!=j)</p><p><b>　　{</b></p><p>　　temp=array[i];//控制層次遍歷順序</p><p>　　printf("%d ", temp->num);</p><p>　　i

40、f(temp->lchild!=NULL)</p><p><b>　　{</b></p><p>　　array[j]=temp->lchild;//左子樹存在，入隊(duì)列</p><p><b>　　j++;</b></p><p><b>　　}</b></

41、p><p>　　if(temp->rchild!=NULL)</p><p><b>　　{</b></p><p>　　array[j]=temp->rchild;//右子樹存在，入隊(duì)列</p><p><b>　　j++;</b></p><p><b>

42、;　　}</b></p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//聲明核心查找函數(shù)</p><p>　　int myNode_search(

43、TNode *p, int key);</p><p>　　//二叉樹的查找，拆開寫的目的是遞歸時避免不必要的判斷</p><p>　　int Node_search(int key)</p><p><b>　　{</b></p><p>　　if(root==NULL)</p><p><

44、;b>　　return 0;</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(key==root->num)</p><p><b>　　return 1;</b></p>

45、;<p><b>　　else</b></p><p><b>　　{</b></p><p>　　return myNode_search(root, key);</p><p><b>　　}</b></p><p><b>　　}</b>

46、;</p><p><b>　　}</b></p><p>　　int myNode_search(TNode *p, int key)</p><p><b>　　{</b></p><p>　　//printf("p.num:%d key:%d\n",p->num,ke

47、y);</p><p>　　if(key==p->num)</p><p><b>　　return 1;</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(key<p-&

48、gt;num)</p><p><b>　　{</b></p><p>　　if(p->lchild!=NULL)</p><p>　　return myNode_search(p->lchild, key);</p><p><b>　　else</b></p><

49、p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　if(p->rchild!=NULL)</p&g

50、t;<p>　　return myNode_search(p->rchild, key);</p><p><b>　　else</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><

51、b>　　}</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p><p>　　system("cls");</p><p>　　system("

52、color 1f");</p><p>　　system("mode con: cols=78 lines=35");</p><p>　　printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");</p><p>　　printf("┃㊣ 必做題6：樹結(jié)構(gòu)

53、的應(yīng)用 ㊣┃\n");</p><p>　　printf("┃ 姓名：xxxxx ┃\n");</p><p>　　printf("┃ 學(xué)號：xxxxxxxxxxx

54、 ┃\n");</p><p>　　printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");</p><p>　　int sum, i, key;</p><p>　　int data[MaxLength];</p><p>　　printf(" 請輸入二叉樹結(jié)點(diǎn)總數(shù): &q

55、uot;);</p><p>　　scanf("%d",&sum);</p><p>　　printf(" 請依次輸入結(jié)點(diǎn)數(shù)值大小(以空格或者回車隔開):\n");</p><p>　　for(i=0;i<sum;i++)</p><p>　　scanf("%d", &

56、amp;data[i]);</p><p>　　for(i=0;i<sum;i++)</p><p>　　Insert_Node(data[i]);</p><p>　　printf(" 先序遞歸遍歷后的結(jié)果為:\n");</p><p>　　Pre_travel(root);</p><p&g

57、t;　　printf("\n 中序遞歸遍歷后的結(jié)果為:\n");</p><p>　　Mid_travel(root);</p><p>　　printf("\n 后序遞歸遍歷后的結(jié)果為:\n");</p><p>　　Suf_travel(root);</p><p>　　printf("\

58、n 中序非遞歸遍歷后的結(jié)果為:\n");</p><p>　　NRMid_travel(root);</p><p>　　printf("\n 層次遍歷后的結(jié)果為:\n");</p><p>　　Level_travel(root);</p><p>　　//為便于測試，多次查找一下</p><

59、;p>　　printf("\n 請輸入要查找的關(guān)鍵字(數(shù)字,非數(shù)字時終止):\n");</p><p>　　while(scanf("%d", &key))</p><p><b>　　{</b></p><p>　　//scanf("%d", &key);<

60、;/p><p>　　if(Node_search(key))</p><p>　　printf(" 該關(guān)鍵字存在！\n");</p><p><b>　　else</b></p><p>　　printf(" 該關(guān)鍵字不存在！\n");</p><p><

61、b>　　}</b></p><p><b>　　//釋放內(nèi)存</b></p><p>　　Free_node(root);</p><p>　　root = NULL;</p><p><b>　　return 0;</b></p><p><b>

62、;　　}</b></p><p>　　用戶手冊（調(diào)試演示）</p><p>　　包含主界面顯示，當(dāng)我們輸入結(jié)點(diǎn)總數(shù)為12，各結(jié)點(diǎn)元素分別為1 2 3 4 5 6 7 8 9 10 11 12 的二叉樹，程序依次創(chuàng)建了該樹，然后依照先序、中序、后序等方式對其進(jìn)行遍歷，遍歷結(jié)束后順帶了一個查找結(jié)點(diǎn)元素的查找函數(shù)search( )，結(jié)果如下圖所示：</p><p&