1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用</b></p><p><b>　　一、問(wèn)題描述</b></p><p>　　二叉樹(shù)是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，在實(shí)際中應(yīng)用十分廣泛。二叉樹(shù)有順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)，可以運(yùn)用遞歸和非遞歸設(shè)計(jì)算法，能夠求解節(jié)點(diǎn)在二叉樹(shù)中的層次數(shù)等問(wèn)題。在實(shí)際應(yīng)用中，要求以同學(xué)錄為例完成系統(tǒng)的設(shè)計(jì)與管理。</p>

2、<p><b>　　二、基本要求</b></p><p>　　1、選擇合適的存儲(chǔ)結(jié)構(gòu)，完成二叉樹(shù)的建立。最好采用順序和鏈?zhǔn)絻煞N方法。</p><p>　　2、在順序二叉樹(shù)中求解節(jié)點(diǎn)所在層次數(shù)。</p><p>　　3、在鏈?zhǔn)蕉鏄?shù)中求解節(jié)點(diǎn)所在層次數(shù)。</p><p>　　4、以同學(xué)錄為例，利用二叉樹(shù)存儲(chǔ)結(jié)

3、構(gòu)，實(shí)現(xiàn)建立、查找、新增、刪除等功能。</p><p><b>　　三、測(cè)試數(shù)據(jù)</b></p><p>　　1、分別以順序和鏈?zhǔn)酱鎯?chǔ)測(cè)試圖示二叉樹(shù)中節(jié)點(diǎn)E所在層次：</p><p>　　2、同學(xué)錄的測(cè)試數(shù)據(jù)：</p><p>　　"趙一","1979-01-01","1

4、5811111111","0807011001"</p><p>　　"錢(qián)二","1980-02-02","15822222222","0807011002"</p><p>　　"孫三","1981-03-03","1583333

5、3333","0807011003"</p><p>　　"李四","1982-04-04","15844444444","0807011004"</p><p>　　在上表的的基礎(chǔ)上，測(cè)試表的建立，以及記錄的新增、修改、刪除等。</p><p><b

6、>　　四、算法思想</b></p><p>　　1、在順序二叉樹(shù)下求節(jié)點(diǎn)所在層次數(shù)</p><p>　　本題中順序二叉樹(shù)按照滿二叉樹(shù)的原則建立，空節(jié)點(diǎn)存“0”。故節(jié)點(diǎn)所在層次count與節(jié)點(diǎn)下標(biāo)m有如下關(guān)系：</p><p>　　1)初始層次數(shù)count=1，當(dāng)m=0時(shí)，所查節(jié)點(diǎn)不存在</p><p>　　2)當(dāng)m非0時(shí)，令

7、m=m/2，count加一</p><p>　　3)m不為1時(shí)，返回層次數(shù)count；m為1時(shí)，重復(fù)步驟2)</p><p>　　2、在鏈?zhǔn)蕉鏄?shù)下求節(jié)點(diǎn)所在層次數(shù)</p><p>　　算法要用非遞歸算法求解二叉樹(shù)中給定節(jié)點(diǎn)的深度，為實(shí)現(xiàn)層次非遞歸求解，必須借用數(shù)據(jù)結(jié)構(gòu)保存將要訪問(wèn)的節(jié)點(diǎn)，在函數(shù)CengciTree(BiTreeLink T,char c)中用數(shù)組q

8、ueue實(shí)現(xiàn)此功能。具體編程時(shí)，用變量n保存當(dāng)前訪問(wèn)的節(jié)點(diǎn)的層次數(shù)目并初始化為1，front和rear是數(shù)組queue中當(dāng)前正在訪問(wèn)的節(jié)點(diǎn)的下標(biāo)以及可插入節(jié)點(diǎn)的下標(biāo)，而flag起到標(biāo)志作用用來(lái)表明是否要增加當(dāng)前的層次數(shù)n。</p><p>　　算法開(kāi)始時(shí)，首先判斷樹(shù)是否為空，若為空樹(shù)退出程序；若樹(shù)不為空，則先判斷根節(jié)點(diǎn)的值是否與要查找節(jié)點(diǎn)的值相等，若相等則返回n，否則將當(dāng)前層次n加1，并將根節(jié)點(diǎn)的左孩子、右孩子以

9、及根節(jié)點(diǎn)本身插入到數(shù)組queue中。可能，有人會(huì)問(wèn)為什么還要將根節(jié)點(diǎn)插入到數(shù)組queue中？這里，將根節(jié)點(diǎn)插入到數(shù)組queue中的目的是，當(dāng)queue[front]保存的是根節(jié)點(diǎn)的指針時(shí)，二叉樹(shù)的一層節(jié)點(diǎn)遍歷結(jié)束了，需要將當(dāng)前層次數(shù)n加1并讓queue[rear]保存根節(jié)點(diǎn)的指針。</p><p>　　算法的核心部分就是while循環(huán)里面的內(nèi)容，首先讓標(biāo)志flag值為0,如果queue[front]不為空且que

10、ue[front]->data的值等于要查找的值c，程序結(jié)束返回n即可；若queue[front]的值是指向根節(jié)點(diǎn)的指針，表明當(dāng)前層次上的所有節(jié)點(diǎn)都已經(jīng)訪問(wèn)過(guò)了，要訪問(wèn)下一個(gè)層次的節(jié)點(diǎn)了，故要把n加1并讓flag值為1以表明在數(shù)組的插入位置queue[rear]需要賦值為跟節(jié)點(diǎn)的指針；如果，均不是上述情況，則將queue[front]的左孩子、右孩子都放到數(shù)組queue中，并將front指向下一個(gè)元素。重復(fù)上述循環(huán)，直到找到了要查

11、找的值，或者遍歷了所有的節(jié)點(diǎn)。</p><p><b>　　3、同學(xué)錄的實(shí)現(xiàn)</b></p><p>　　本題的一個(gè)實(shí)際應(yīng)用是實(shí)現(xiàn)同學(xué)錄，我們采用二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，利用預(yù)置數(shù)組建立二叉樹(shù)；先序方式遍歷二叉樹(shù)并輸出；遞歸算法實(shí)現(xiàn)對(duì)同學(xué)錄的查找；基于查找實(shí)現(xiàn)對(duì)同學(xué)錄的修改和新增成員；求所要操作節(jié)點(diǎn)的父親節(jié)點(diǎn)，從而順利的編寫(xiě)對(duì)同學(xué)錄的刪除操作。</p><

12、p><b>　　五、模塊劃分：</b></p><p>　　1、在順序二叉樹(shù)下求節(jié)點(diǎn)所在層次數(shù)</p><p>　　（1）void Creattree()其功能是建立順序二叉樹(shù)；</p><p>　　（2）void Cengcitree()其功能是求節(jié)點(diǎn)層次</p><p>　　2、在鏈?zhǔn)蕉鏄?shù)下求節(jié)點(diǎn)所在層次數(shù)&

13、lt;/p><p>　?。?）int CreateBiTree(BiTreeLink *T)其功能是建立二叉樹(shù)；</p><p>　　（2）void PreOrderTraverse(BiTreeLink T) 其功能是先序遍歷二叉樹(shù)；</p><p>　　（3）int CengciTree(BiTreeLink T,char c) 其功能是求層次數(shù)</p>

14、<p>　　（1）int n=0,front=0,rear=0,flag;初始化隊(duì)列；</p><p>　?。?）(front+1)%MAXSIZE!=rear判斷隊(duì)列不滿。</p><p>　　3、以同學(xué)錄為例，利用二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)建立、查找、新增、刪除等功能。</p><p>　?。?）void CreateBiTree(DataType *i

15、tems,BiTree *T)其功能是建立同學(xué)錄</p><p>　?。?）void PreOrderTraverse(BiTree T)</p><p>　?。?）PBTNode SearchTree(BiTree T,char *ch)</p><p>　?。?）void ModifyTree(BiTree T)</p><p>　?。?

16、）void DeleteTree(BiTree T)</p><p>　　4、main()主函數(shù)，功能是調(diào)要相關(guān)函數(shù)實(shí)現(xiàn)問(wèn)題的求解。</p><p><b>　　六、數(shù)據(jù)結(jié)構(gòu)：</b></p><p>　　1、二叉樹(shù)的抽象數(shù)據(jù)類型結(jié)構(gòu)定義：</p><p>　　typedef struct Node</p>

17、<p>　　{ TElemType data;</p><p>　　struct Node *lchild,*rchild;</p><p>　　} BiTNode, *BiTreeLink;</p><p>　　2、同學(xué)錄節(jié)點(diǎn)信息：</p><p>　　typedef struct Info{</p><p&

18、gt;　　char name[20];//姓名</p><p>　　char date[11];//生日</p><p>　　char phone[12];//電話</p><p>　　char StudentNum[11];//學(xué)號(hào)</p><p>　　}DataType;</p><p>　　3、同學(xué)錄數(shù)據(jù)存

19、儲(chǔ)結(jié)構(gòu)：</p><p>　　typedef struct Node</p><p>　　{ DataType data;</p><p>　　struct Node *left,*right;</p><p>　　}BTNode, *PBTNode,*BiTree;</p><p><b>　　七、源程序：

20、</b></p><p>　　1、在順序二叉樹(shù)下求節(jié)點(diǎn)所在層次數(shù)</p><p>　　#define maxlen 100</p><p>　　#include"stdio.h"</p><p>　　typedef struct node</p><p>　　{ char data;&l

21、t;/p><p>　　} Bitree[maxlen];</p><p>　　int N; Bitree T;</p><p><b>　　/*建立二叉樹(shù)*/</b></p><p>　　void Creattree()</p><p>　　{ int i; char c;</p>

22、<p>　　printf("請(qǐng)輸入結(jié)點(diǎn)數(shù)目(包括空結(jié)點(diǎn))：");</p><p>　　scanf("%d",&N);</p><p>　　printf("請(qǐng)輸入結(jié)點(diǎn)(空結(jié)點(diǎn)為0):");</p><p>　　for(i=1;i<=N;i++)</p><p>

23、<b>　　{</b></p><p>　　scanf("%s",&c);</p><p>　　T[i].data=c;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　/*

24、求二叉樹(shù)節(jié)點(diǎn)所在層次*/</p><p>　　void Cengcitree()</p><p><b>　　{</b></p><p>　　int i,m=0,count=1; char c;</p><p>　　printf("請(qǐng)輸入某一結(jié)點(diǎn)：");</p><p>　　s

25、canf("%s",&c);</p><p><b>　　i=1;</b></p><p>　　while(i<=N)</p><p><b>　　{</b></p><p>　　if(T[i].data==c){m=i; break;}</p>&

26、lt;p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　if (m==0)</b></p><p>　　printf("\n節(jié)點(diǎn)不存在");</p><p>　　while(m!=1)</p&g

27、t;<p><b>　　{</b></p><p><b>　　m=m/2;</b></p><p><b>　　count++;</b></p><p><b>　　}</b></p><p>　　printf("\n節(jié)點(diǎn)所在層次

28、:%d\n",count);</p><p><b>　　}</b></p><p><b>　　/*主函數(shù)*/</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　Creattree

29、();</p><p>　　Cengcitree();}</p><p>　　2、在鏈?zhǔn)蕉鏄?shù)下求節(jié)點(diǎn)所在層次數(shù)</p><p>　　#include "stdio.h"</p><p>　　#include <stdlib.h> </p><p>　　#include <mall

30、oc.h></p><p>　　#define MAXSIZE 20</p><p>　　#define NULL 0</p><p>　　typedef char TElemType;</p><p>　　/* 二叉鏈樹(shù)的類型定義*/</p><p>　　typedef struct BiTNode</p

31、><p>　　{ TElemType data;</p><p>　　struct BiTNode *lchild,*rchild;</p><p>　　} BiTNode, *BiTreeLink;</p><p>　　/*先序建立二叉樹(shù)*/</p><p>　　int CreateBiTree(BiTreeLink *

32、T)</p><p>　　{ char ch;</p><p>　　scanf("%c",&ch);</p><p>　　if (ch==' ')</p><p><b>　　*T=NULL;</b></p><p><b>　　else<

33、;/b></p><p>　　{ *T=(BiTreeLink)malloc(sizeof(BiTNode));</p><p>　　if (!(*T)) return 0; /* 未分配到空間錯(cuò)誤返回*/</p><p>　　(*T)->data=ch;</p><p>　　CreateBiTree(&(*T)->

34、lchild);</p><p>　　CreateBiTree(&(*T)->rchild); }</p><p>　　return 1; }</p><p>　　/* 先序遍歷二叉樹(shù)*/</p><p>　　void PreOrderTraverse(BiTreeLink T)</p><p><

35、b>　　{ if (T)</b></p><p>　　{ printf("%c",T->data);</p><p>　　PreOrderTraverse(T->lchild);</p><p>　　PreOrderTraverse(T->rchild); }</p><p><b

36、>　　}</b></p><p>　　/*求二叉樹(shù)節(jié)點(diǎn)所在層次數(shù)*/</p><p>　　int CengciTree(BiTreeLink T,char c)</p><p><b>　　{</b></p><p>　　int n=1,front=0,rear=0,flag;</p>&

37、lt;p>　　BiTreeLink queue[MAXSIZE];//</p><p><b>　　if(!T)</b></p><p><b>　　{</b></p><p>　　printf("樹(shù)為空!\n");</p><p><b>　　return n;

38、</b></p><p><b>　　}</b></p><p>　　if(T->data==c)</p><p><b>　　return n;</b></p><p>　　queue[rear++]=T->lchild;</p><p>　　que

39、ue[rear++]=T->rchild;</p><p>　　queue[rear++]=T;</p><p><b>　　n++;</b></p><p>　　while((front+1)%MAXSIZE!=rear)</p><p><b>　　{</b></p><

40、;p><b>　　flag=0;</b></p><p>　　if(queue[front]&&queue[front]->data==c) return n;</p><p>　　if(queue[front]==T)</p><p><b>　　{ </b></p><

41、p><b>　　n++;</b></p><p><b>　　flag=1;</b></p><p><b>　　}</b></p><p>　　else if(queue[front])</p><p><b>　　{ </b></p>

42、<p>　　queue[rear]=queue[front]->lchild;</p><p>　　rear=(rear+1)%MAXSIZE;</p><p>　　queue[rear]=queue[front]->rchild;</p><p>　　rear=(rear+1)%MAXSIZE;</p><p>&

43、lt;b>　　}</b></p><p><b>　　if(flag)</b></p><p><b>　　{</b></p><p>　　queue[rear]=T;</p><p>　　rear=(rear+1)%MAXSIZE;</p><p><

44、;b>　　}</b></p><p>　　front=(front+1)%MAXSIZE;</p><p><b>　　}</b></p><p>　　printf("\n元素%c不存在。\n",c);</p><p>　　return -1;</p><p>

45、;<b>　　}</b></p><p>　　/****主函數(shù)****/</p><p>　　int main()</p><p><b>　　{ </b></p><p>　　BiTreeLink T;</p><p><b>　　int c=0;</b&g

46、t;</p><p><b>　　char x;</b></p><p>　　printf("請(qǐng)輸入節(jié)點(diǎn)\n"); CreateBiTree(&T);</p><p>　　printf("\n先序:"); PreOrderTraverse(T);</p><p>

47、　　printf("\n請(qǐng)輸入節(jié)點(diǎn)：");</p><p>　　getchar();</p><p>　　printf("\n請(qǐng)輸入要查詢的字符：");</p><p>　　scanf("%c",&x); </p><p>　　printf("\n所在層次%3d\n

48、\n",CengciTree(T,x));</p><p>　　system("pause");</p><p>　　return 0; </p><p><b>　　}</b></p><p>　　3、以同學(xué)錄為例，利用二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)建立、查找、新增、刪除等功能。</p>

49、<p>　　#include "stdio.h"</p><p>　　#include "stdlib.h"</p><p>　　#include "string.h"</p><p>　　/****二叉鏈樹(shù)的類型定義****/</p><p>　　typedef st

50、ruct Info{</p><p>　　char name[20];//姓名</p><p>　　char date[11];//生日</p><p>　　char phone[12];//電話</p><p>　　char StudentNum[11];//學(xué)號(hào)</p><p>　　}DataType;<

51、;/p><p>　　typedef struct Node</p><p>　　{ DataType data;</p><p>　　struct Node *left,*right;</p><p>　　}BTNode, *PBTNode,*BiTree;</p><p>　　/*****插入（左孩子）****/<

52、/p><p>　　PBTNode InsertLeft(PBTNode T,DataType x)</p><p>　　{ PBTNode p;</p><p>　　if(!T) return NULL;</p><p>　　if(T->left ==NULL)</p><p>　　{p=(PBTNode)mall

53、oc(sizeof(BTNode));</p><p>　　p->data=x;</p><p>　　p->left =NULL;</p><p>　　p->right =NULL;</p><p>　　T->left =p;</p><p>　　return p;}</p>&l

54、t;p>　　return NULL;</p><p><b>　　}</b></p><p>　　/*****插入（右孩子）****/</p><p>　　PBTNode InsertRight(PBTNode T,DataType x)</p><p>　　{ PBTNode p;</p><

55、p>　　if(!T) return NULL;</p><p>　　if(T->right ==NULL)</p><p>　　{p=(PBTNode)malloc(sizeof(BTNode));</p><p>　　p->data=x;</p><p>　　p->left =NULL;</p>&l

56、t;p>　　p->right =NULL;</p><p>　　T->right =p;</p><p>　　return p;}</p><p>　　return NULL;</p><p><b>　　}</b></p><p>　　/*****插入****/</p&g

57、t;<p>　　void InsertChild(PBTNode T,DataType x)</p><p>　　{if (T->left==NULL && T->right==NULL && !strcmp(T->data.name ," 無(wú)"))</p><p>　　{T->data=x;}&

58、lt;/p><p>　　else if (InsertLeft(T,x)) return;</p><p><b>　　else{</b></p><p>　　if (InsertRight(T,x)) return;</p><p>　　else InsertChild(T->left ,x);}</p>

59、<p><b>　　}</b></p><p>　　/****建立二叉樹(shù)****/</p><p>　　void CreateBiTree(DataType *items,BiTree *T)</p><p><b>　　{ int i;</b></p><p>　　printf(&q

60、uot;本程序通過(guò)預(yù)置數(shù)組建立二叉樹(shù)\n");</p><p>　　(*T)=(PBTNode)malloc(sizeof(BTNode));</p><p>　　(*T)->left=NULL;</p><p>　　(*T)->right=NULL;</p><p>　　(*T)->data=items[0];&

61、lt;/p><p>　　for(i=1;i<4;i++)</p><p>　　{ InsertChild(*T,items[i]);}</p><p><b>　　}</b></p><p>　　/****先序遍歷二叉樹(shù)****/</p><p>　　void PreOrderTraverse(

62、BiTree T)</p><p><b>　　{ if (T)</b></p><p>　　{printf("\n\t姓名\t\t學(xué)號(hào)\t\t生日\(chéng)t\t電話\n");</p><p>　　printf("\n\t%s\t%s\t%s\t%s\n\n",T->data.name,T->dat

63、a.StudentNum,T->data.date,T->data.phone);</p><p>　　PreOrderTraverse(T->left);</p><p>　　PreOrderTraverse(T->right); }</p><p><b>　　}</b></p><p>　　

64、/****查找二叉樹(shù)****/</p><p>　　PBTNode SearchTree(BiTree T,char *ch)</p><p>　　{PBTNode flag=NULL;</p><p><b>　　if (T)</b></p><p>　　{if(!strcmp(T->data.name,ch

65、))</p><p>　　{printf("\n\t%s\t%s\t%s\t%s\n\n",T->data.name,T->data.StudentNum,T->data.date,T->data.phone);</p><p>　　flag=T; return flag;</p><p><b>　　}<

66、;/b></p><p>　　else flag=SearchTree(T->left,ch);</p><p>　　if(flag) return flag;</p><p><b>　　else</b></p><p>　　flag=SearchTree(T->right,ch);</p>

67、;<p><b>　　}</b></p><p>　　return flag;</p><p><b>　　}</b></p><p>　　/****查找父親節(jié)點(diǎn)****/</p><p>　　PBTNode SearchFather(PBTNode r,BiTree T,int *f

68、lag)</p><p>　　{ PBTNode p=NULL; </p><p><b>　　if(T)</b></p><p>　　{ if(T->left==r)</p><p>　　{(*flag)=0; p=T;return p;}//flag=0表示左孩子的父親</p><p>

69、;　　else if(T->right==r) </p><p>　　{(*flag)=1; p=T;return p;}</p><p><b>　　else</b></p><p>　　{p=SearchFather(r,T->left,flag);</p><p>　　if(p) return p;&l

70、t;/p><p>　　else p=SearchFather(r,T->right,flag);}</p><p><b>　　}</b></p><p><b>　　return p;</b></p><p><b>　　}</b></p><p>

71、　　/****修改二叉樹(shù)****/</p><p>　　void ModifyTree(BiTree T)</p><p>　　{ char ch[20],Mod[12]; PBTNode ModifyNode; int caseflag;</p><p>　　printf("請(qǐng)輸入要修改信息的姓名:"); scanf("%s&quo

72、t;,ch); </p><p>　　ModifyNode=SearchTree(T,ch);</p><p>　　if(!ModifyNode)</p><p>　　printf("\n查找的姓名不存在\n"); </p><p><b>　　else</b></p><p>

73、;　　{while(1){</p><p>　　printf("\n\</p><p><b>　　1.修改生日\(chéng)n\</b></p><p><b>　　2.修改電話\n\</b></p><p><b>　　3.修改學(xué)號(hào)\n\</b></p><

74、;p>　　4.不修改\n");</p><p>　　scanf("%d",&caseflag);</p><p>　　switch(caseflag)</p><p><b>　　{case 1:</b></p><p>　　printf("請(qǐng)輸入修改后的生日:&qu

75、ot;);</p><p>　　scanf("%s",Mod);</p><p>　　strcpy(ModifyNode->data.date,Mod);</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p>

76、;<p>　　printf("請(qǐng)輸入修改后的電話:");</p><p>　　scanf("%s",Mod);</p><p>　　strcpy(ModifyNode->data.phone,Mod);</p><p><b>　　break;</b></p><p

77、><b>　　case 3:</b></p><p>　　printf("請(qǐng)輸入修改后的學(xué)號(hào):");</p><p>　　scanf("%s",Mod);</p><p>　　strcpy(ModifyNode->data.StudentNum,Mod);</p><p&g

78、t;<b>　　break;</b></p><p>　　case 4:return;}</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　/

79、****刪除二叉樹(shù)****/</p><p>　　void DeleteTree(BiTree T)</p><p>　　{ char ch[20]; PBTNode DelNodeFather,DelNode,p,q;int flag;</p><p>　　printf("請(qǐng)輸入要?jiǎng)h除信息的姓名:"); scanf("%s"

80、;,ch); </p><p>　　DelNode=SearchTree(T,ch);</p><p>　　if(!DelNode)</p><p>　　printf("\n查找的姓名不存在\n"); </p><p><b>　　else</b></p><p>　　{if

81、(T==DelNode)</p><p>　　{if(DelNode->left)</p><p>　　{p=DelNode->left;</p><p>　　while(p->right)</p><p>　　{p=p->right;}</p><p>　　p->right=DelNod

82、e->right;</p><p>　　q=DelNode->left;</p><p>　　*DelNode=*q;</p><p>　　q->left=NULL;</p><p>　　q->right=NULL;</p><p><b>　　free(q);}</b>&

83、lt;/p><p>　　else if(DelNode->right)</p><p>　　{q=DelNode->right;</p><p>　　*DelNode=*q;</p><p>　　q->left=NULL;</p><p>　　q->right=NULL;</p>&

84、lt;p><b>　　free(q);}</b></p><p>　　else {strcpy(T->data.name," 無(wú)");</p><p>　　strcpy(T->data.StudentNum," 無(wú)");</p><p>　　strcpy(T->data.

85、date," 無(wú)");</p><p>　　strcpy(T->data.phone," 無(wú)");}</p><p><b>　　}</b></p><p><b>　　else </b></p><p>　　{ DelNodeFather=

86、SearchFather(DelNode,T,&flag); </p><p>　　if(DelNode->left)</p><p>　　{p=DelNode->left;</p><p>　　while (p->right)</p><p>　　{p=p->right;}</p><p&

87、gt;　　p->right=DelNode->right;</p><p>　　q=DelNode->left;</p><p>　　*DelNode=*q;</p><p>　　q->left=NULL;</p><p>　　q->right=NULL;</p><p><b>

88、;　　free(q);}</b></p><p>　　else{q=DelNode->right;</p><p><b>　　if(q)</b></p><p>　　{*DelNode=*q;</p><p>　　q->left=NULL;</p><p>　　q-&

89、gt;right=NULL;</p><p><b>　　free(q);}</b></p><p>　　else{free(DelNode);</p><p>　　if (flag==0) DelNodeFather->left=NULL;</p><p>　　if (flag==1) DelNodeFathe

90、r->right=NULL;}</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n刪除指定姓名后的同學(xué)錄\n");</p><p><b>　　}</b></p>&l

91、t;p><b>　　}</b></p><p>　　/****主函數(shù)****/</p><p>　　void main()</p><p>　　{ BiTree T; </p><p>　　Int caseflag;</p><p>　　char ch[20]; </p>&l

92、t;p>　　DataType x={"周五","1983-05-05","15855555555","0807011005"};</p><p>　　DataType items[4]={</p><p>　　{"趙一","1979-01-01","158

93、11111111","0807011001"},</p><p>　　{"錢(qián)二","1980-02-02","15822222222","0807011002"},</p><p>　　{"孫三","1981-03-03","158

94、33333333","0807011003"},</p><p>　　{"李四","1982-04-04","15844444444","0807011004"}};</p><p>　　CreateBiTree(items,&T);</p><p>

95、;　　printf("\n先序遍歷:\n"); PreOrderTraverse(T);</p><p><b>　　while(1){</b></p><p>　　printf("\n\</p><p>　　1.按姓名查找\n\</p><p>　　2.新增同學(xué)信息\n\</p>

96、;<p>　　3.修改同學(xué)信息\n\</p><p>　　4.刪除同學(xué)信息\n\</p><p>　　5.退出\n\n");</p><p>　　scanf("%d",&caseflag);</p><p>　　switch(caseflag)</p><p><

97、;b>　　{case 1:</b></p><p>　　printf("請(qǐng)輸入要查找的姓名:"); scanf("%s",ch); </p><p>　　if(!SearchTree(T,ch))</p><p>　　printf("\n查找的姓名不存在\n"); </p>

98、<p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　printf("\n新增:\n");</p><p>　　InsertChild(T,x);</p><p>　　PreOrderTraverse(T);

99、</p><p><b>　　break;</b></p><p><b>　　case 3:</b></p><p>　　ModifyTree(T);</p><p>　　PreOrderTraverse(T);</p><p><b>　　break;</

100、b></p><p><b>　　case 4:</b></p><p>　　DeleteTree(T);</p><p>　　PreOrderTraverse(T);</p><p><b>　　break;</b></p><p>　　case 5:return;}

101、</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　八、測(cè)試結(jié)果：</b></p><p>　　2、在順序二叉樹(shù)中求解節(jié)點(diǎn)所在層次數(shù)。</p><p><b>　　I</b>

102、</p><p>　　3、在鏈?zhǔn)蕉鏄?shù)中求解節(jié)點(diǎn)所在層次數(shù)。</p><p>　　4、以同學(xué)錄為例，利用二叉樹(shù)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)建立、查找、新增、修改、刪除等功能。</p><p><b>　　(1)建立:</b></p><p><b>　　2、查找：</b></p><p>&

103、lt;b>　　3、新增：</b></p><p><b>　　4、修改：</b></p><p><b>　　5、刪除：</b></p><p><b>　　九、參考文獻(xiàn)</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》嚴(yán)蔚敏 吳偉民 主編；</p>

104、;<p>　　《C語(yǔ)言程序設(shè)計(jì)》譚浩強(qiáng) 主編；</p><p><b>　　小結(jié)</b></p><p>　　此次課程設(shè)計(jì)我們小組的題目是《二叉樹(shù)的應(yīng)用》，在老師的指導(dǎo)下，我們首先分析了課程設(shè)計(jì)的任務(wù)、要求和目的，經(jīng)過(guò)小組討論，明確了題目的含義、所需要的知識(shí)，最終確定了問(wèn)題的解決方案。我主要是對(duì)二叉樹(shù)中節(jié)點(diǎn)所在的層次數(shù)進(jìn)行求解，而另兩位組員的任務(wù)是完成二

105、叉樹(shù)在現(xiàn)實(shí)生活中的具體應(yīng)用實(shí)例的設(shè)計(jì)，雖然同為二叉樹(shù)的內(nèi)容，但是具體方面有些差異，所以經(jīng)過(guò)小組討論，在征得老師的同意之后，我們分成兩小組分別進(jìn)行課程設(shè)計(jì)，以下就是我在此次課程設(shè)計(jì)中的小結(jié)：</p><p>　　為了充分利用時(shí)間更好的完成老師下達(dá)課程設(shè)計(jì)任務(wù)，我溫習(xí)了之前學(xué)習(xí)的C語(yǔ)言知識(shí)和數(shù)據(jù)結(jié)構(gòu)中關(guān)于隊(duì)列、二叉樹(shù)的有關(guān)知識(shí)，然后充分利用上課時(shí)間查閱資料和編寫(xiě)代碼，通過(guò)對(duì)一些現(xiàn)有源代碼的研究，以及指導(dǎo)老師提供關(guān)于二

106、叉樹(shù)的部分源代碼研究，逐漸對(duì)整個(gè)課程設(shè)計(jì)有了更清晰的認(rèn)識(shí)，在腦海中有了明確的設(shè)計(jì)思路。在編寫(xiě)代碼的過(guò)程中，由于C語(yǔ)言知識(shí)的不扎實(shí)，頻繁的出現(xiàn)錯(cuò)誤，虛心請(qǐng)教老師和同學(xué)，經(jīng)過(guò)指導(dǎo)，對(duì)程序進(jìn)行不停的修改和調(diào)試，完成了此次課程設(shè)計(jì)。</p><p>　　本次課程設(shè)計(jì)訓(xùn)練了我對(duì)計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象進(jìn)行分析的能力，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)及相應(yīng)算法的能力。讓我對(duì)所學(xué)課程內(nèi)容掌握情況的一次自我驗(yàn)證。同時(shí)這些日子里小組同學(xué)之間互相學(xué)習(xí)