數(shù)據(jù)結(jié)構(gòu)實(shí)踐

1、目錄第一章 課程設(shè)計(jì)性質(zhì)與目的.4第二章 設(shè)計(jì)內(nèi)容及基本要求.5第三章 詳細(xì)設(shè)計(jì)說(shuō)明.113.1 項(xiàng)目一.73.2 項(xiàng)目二.163.3 項(xiàng)目三.26第四章 實(shí)訓(xùn)總結(jié).37附錄 （參考文獻(xiàn)、核心代碼）第一章 課程設(shè)計(jì)性質(zhì)與目的數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)是信息管理與信息系統(tǒng)專業(yè)集中實(shí)踐性環(huán)節(jié)之一，其目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)良好的程序設(shè)計(jì)技能。鏈表和順序表操作的設(shè)計(jì)目的： 1掌握線性表的在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 2掌握線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上的基本操作。二叉樹(shù)操作的設(shè)計(jì)目的： 1掌握二叉樹(shù)的概念

2、和性。2. 掌握任意二叉樹(shù)存儲(chǔ)結(jié)構(gòu)。 3掌握任意二叉樹(shù)的基本操作。第二章 設(shè)計(jì)內(nèi)容及基本要求一、實(shí)驗(yàn)實(shí)訓(xùn)的基本要求是：本實(shí)訓(xùn)面向應(yīng)用，以解決實(shí)際問(wèn)題為主。題目以選用學(xué)生相對(duì)比較熟悉的為宜，要求通過(guò)本實(shí)訓(xùn)，理解有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念、不同數(shù)據(jù)類型的存儲(chǔ)和基本操作的算法實(shí)現(xiàn)，理解數(shù)據(jù)類型的邏輯結(jié)構(gòu)及物理存儲(chǔ)結(jié)構(gòu)， 通過(guò)自己設(shè)計(jì)，編程、調(diào)試、測(cè)試、能夠基本掌握在不同存儲(chǔ)結(jié)構(gòu)下的算法實(shí)現(xiàn)及算法優(yōu)化，樹(shù)立并培養(yǎng)系統(tǒng)規(guī)范開(kāi)發(fā)的理念。實(shí)訓(xùn)中學(xué)生要將相關(guān)課程中學(xué)到的知識(shí)、思想和理念盡量應(yīng)用在實(shí)訓(xùn)中。結(jié)束后要按規(guī)定提交代碼和各種文檔。實(shí)訓(xùn)基本步驟：1. 選題設(shè)計(jì)的課題盡量結(jié)合教學(xué)、科研的實(shí)際課題，規(guī)模、大小適當(dāng)

3、，具有一定復(fù)雜度。應(yīng)根據(jù)題目大小、難度確定是否分組，組內(nèi)成員人數(shù)。2. 數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì)根據(jù)需求分析，選擇合理的數(shù)據(jù)結(jié)構(gòu)及設(shè)計(jì)相應(yīng)的算法。 3. 編碼根據(jù)已設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)和算法，編寫代碼。4. 測(cè)試按照系統(tǒng)測(cè)試的原則、方法和步驟，對(duì)系統(tǒng)進(jìn)行測(cè)試。測(cè)試中應(yīng)形成測(cè)試報(bào)告。5. 編寫實(shí)訓(xùn)報(bào)告實(shí)訓(xùn)說(shuō)明書，內(nèi)容及要求如下：（1） 封面（2） 成績(jī)?cè)u(píng)定（3） 目錄（4） 說(shuō)明書正文，主要內(nèi)容包括：一、 設(shè)計(jì)題目 二、 運(yùn)行環(huán)境（軟、硬件環(huán)境） 三、 數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì)的思想 四、 數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計(jì)五、 源代碼 六、 運(yùn)行結(jié)果分析 七、 實(shí)習(xí)總結(jié)（收獲及體會(huì)）參考資料：附錄（核心代碼）。二、設(shè)計(jì)內(nèi)容 項(xiàng)

4、目一：順序表操作1、設(shè)計(jì)目的 （1）掌握線性表的在順序結(jié)構(gòu)上的實(shí)現(xiàn)。 （2）掌握線性表在順序結(jié)構(gòu)上的基本操作2、設(shè)計(jì)內(nèi)容和要求利用順序表的插入運(yùn)算建立順序表，然后實(shí)現(xiàn)順序表的查找、插入、刪除、計(jì)數(shù)、輸出、排序、逆置等運(yùn)算（查找、插入、刪除、查找、計(jì)數(shù)、輸出、排序、逆置要單獨(dú)寫成函數(shù)），并能在屏幕上輸出操作前后的結(jié)果。 項(xiàng)目二：鏈表操作1、設(shè)計(jì)目的 （1）掌握線性表的在鏈?zhǔn)浇Y(jié)構(gòu)上的實(shí)現(xiàn)。 （2）掌握線性表在鏈?zhǔn)浇Y(jié)構(gòu)上的基本操作2、設(shè)計(jì)內(nèi)容和要求利用鏈表的插入運(yùn)算建立鏈表，然后實(shí)現(xiàn)鏈表的查找、插入、刪除、計(jì)數(shù)、輸出、排序、逆置等運(yùn)算（查找、插入、刪除、查找、計(jì)數(shù)、輸出、排序、逆置要單獨(dú)寫成函數(shù)），

5、并能在屏幕上輸出操作前后的結(jié)果。 項(xiàng)目三：二叉樹(shù)的基本操作1、設(shè)計(jì)目的（1）掌握二叉樹(shù)的概念和性質(zhì) （2）掌握任意二叉樹(shù)存儲(chǔ)結(jié)構(gòu)。 （3）掌握任意二叉樹(shù)的基本操作。2、設(shè)計(jì)內(nèi)容和要求（1）對(duì)任意給定的二叉樹(shù)（頂點(diǎn)數(shù)自定）建立它的二叉鏈表存儲(chǔ)結(jié)構(gòu)，并利用棧的五種基本運(yùn)算（置空棧、進(jìn)棧、出棧、取棧頂元素、判棧空）實(shí)現(xiàn)二叉樹(shù)的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。 （2） 求二叉樹(shù)高度、結(jié)點(diǎn)數(shù)、度為1的結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)。第三章 詳細(xì)設(shè)計(jì)說(shuō)明項(xiàng)目一：順序表操作：考查知識(shí)點(diǎn)：（1）利用順序表的插入運(yùn)算建立順序表；（2）實(shí)現(xiàn)順序表的查找、插入、刪除、計(jì)數(shù)、輸出、排序、逆置等運(yùn)算（查找、插入、刪除

6、、查找、計(jì)數(shù)、輸出、排序、逆置要單獨(dú)寫成函數(shù)）；（3）能夠在屏幕上輸出操作前后的結(jié)果。一、算法1. 創(chuàng)建：#define LIST_INIT_SIZE 100#define LISTINCREMENT 20typedf structElemType *elem;int length;int listsize;SqList;Status InitList.Sq(SqList&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW); L.lengh=0;L.listsize=L

7、IST_INIT_SIZE;return Ok;/InitList_Sq2.插入:Status ListInsert_Sq(SqList&L,int i,ElemType e)/插入if(i<1|i>L.length+1)return ERROR;if(L.length>=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINC

8、REMENT;q=&(L.elemi-1);/q指示插入位置for(p=&(L.elemL.length-1);p>=q;-p)*(p+1)=*p;*q=e+L.length；return OK;/ListInsert_Sq3.刪除：Status ListDelete_Sq(SqList &L，nt i,ElemType&e)if(i<1|(i>L.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;/表尾元素的位置for(+p;p<=q;+p)=*p;-L.le

9、ngth;/表長(zhǎng)減1return OK;/ListDelete_Sq4.查找：Int LocateElem_Sq(SqList L，ElemType e， /查找Status（*compare）（ElemType，ElemType）i=1；p=L.elem;while(i<=L.length&&!(*compare)(*p+,e)+i;if(i<=L.length) return i;else return 0;/LocateElem_Sq二、源代碼#include <stdio.h>#include <stdlib.h>#include &

10、lt;iostream.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 20typedef struct ElemType *list;int length;int listsize;SqList;int InitList_Sq(SqList &L) L.lis

11、t = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType); if (!L.list) exit (OVERFLOW); / 存儲(chǔ)分配失敗int i,y; L.length = 0; L.listsize = LIST_INIT_SIZE; printf("請(qǐng)輸入元素個(gè)數(shù):");scanf("%d",&y);printf("請(qǐng)輸入元素:n");for(i=0;i<y;i+,L.length+)scanf("%d",&L.listi);for

12、(i=0;i<L.length;i+)printf("%d ",L.listi);printf("n"); return OK; / InitList_Sq/*輸出函數(shù)*void output_Sq(SqList &L) printf("輸出順序表n");for(int i=0;i<L.length;i+) printf("%d ",L.listi);printf("n"); /*插入*Status ListInsert_Sq(SqList &L) ElemType

13、*q,*p,*newbase;int i,e;printf("請(qǐng)輸入插入位置i:"); scanf(" %d",&i);if(i < 1 | i > L.length + 1) return ERROR;if(L.length >= L.listsize)newbase = (ElemType *)realloc(L.list,(L.listsize + LISTINCREMENT) * sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.list = newbase;L.listsize

14、 += LISTINCREMENT;q = &(L.listi-1); / q指示插入位置for (p = & (L.listL.length-1); p >= q; -p)*(p+1) = *p; / 插入位置及之后的元素右移printf("輸入插入數(shù)值e: ");scanf("%d",&e);*q = e; +L.length; printf("輸出插入之后的順序表:");for( i=0;i<L.length;i+) printf("%d ",L.listi);printf

15、("n");return OK; / ListInsert_Sq/*刪除*int ListDelete_Sq(SqList &L) ElemType *p,*q;int i,e;printf("請(qǐng)輸入你要?jiǎng)h除的元素位序：");scanf("%d",&i);if (i < 1) | (i > L.length) return ERROR; p = & (L.listi-1); e = *p; q = L.list + L.length - 1; / 表尾元素的位置printf("刪除的元素值

16、為: %dn",e);for (+p; p <= q; +p) *(p-1) = *p; -L.length; for( i=0;i<L.length;i+) printf("%d ",L.listi);printf("n");return OK; / ListDelete_Sq /*查找* Status LocateElem_Sq(SqList L) int e,i;printf("請(qǐng)輸入你要查找元素的數(shù)值: ");scanf("%d",&e);printf("你要查找元素

17、的位序?yàn)? ");for(i=0;i<L.length;i+)if(e=L.listi)printf("%d ",i+1);printf("n");return 0; /*排序（由小到大）*void Print_Sq(SqList &L) int t;for(int j=0;j<L.length-1;j+)for(int i=0;i<L.length-1-j;i+)if(L.listi>L.listi+1)t=L.listi;L.listi=L.listi+1;L.listi+1=t;printf("輸

18、出排序（由小到大）表n");for(int i=0;i<L.length;i+) printf("%d ",L.listi);printf("n");/*計(jì)數(shù)*void ListLength_Sq(SqList L) printf("輸出表中元素個(gè)數(shù)n");printf("%dn",L.length);/*逆置*void inverse_Sq(SqList &L) int t,i;for(i=0;i<=L.length/2-1;i+)t=L.listi;L.listi=L.listL.

19、length-i-1;L.listL.length-i-1=t;printf("輸出逆置順序表n");for( i=0;i<L.length;i+) printf("%d ",L.listi);printf("n");/*退出* int Quit_Sq(SqList L) exit (0); return 0; /*主函數(shù)*void main() SqList L;int i;printf(" 1. 構(gòu)造 n");printf(" 2. 插入 n");printf(" 3. 刪除

20、 n");printf(" 4. 排序 n");printf(" 5. 計(jì)數(shù) n");printf(" 6. 查找 n");printf(" 7. 逆置 n");printf(" 8. 輸出 n");printf(" 9. 退出 n");for(;)printf("Please choose 1 to 9 :n");scanf("%d",&i);switch(i)case 1:InitList_Sq(L);break;

21、case 2:ListInsert_Sq(L); break;case 3:ListDelete_Sq(L); break;case 4:Print_Sq(L); break;case 5:ListLength_Sq(L); break;case 6:LocateElem_Sq(L);break;case 7:inverse_Sq(L);break;case 8:output_Sq(L);break;case 9: Quit_Sq(L);break;default:printf("輸入有誤");三、操作結(jié)果項(xiàng)目二：鏈表操作考查知識(shí)點(diǎn)：（1）利用鏈表的插入運(yùn)算建立鏈表；（2）

22、實(shí)現(xiàn)鏈表的查找、插入、刪除、計(jì)數(shù)、輸出、排序、逆置等運(yùn)算（查找、插入、刪除、查找、計(jì)數(shù)、輸出、排序、逆置要單獨(dú)寫成函數(shù)）；（3）能夠在屏幕上輸出操作前后的結(jié)果。一、算法1.創(chuàng)建：void CreateList_L(LinkList &L) /逆序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈線性表L。 L=(LinkList)malloc(sizeof(LNode);/生成新的結(jié)點(diǎn)L->next=NULL; /先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;-i) p=(LinkList)malloc(sizeof(LNode);scanf(&p->data);p-&

23、gt;next = L->next;L->next = p; /插入到表頭/CreateList L2. 插入：Status ListInsert_L(LinkList &L,int i ,ElemType e) /插入p=L;j=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i)return ERROR；s=(LinkList)malloc(sizeof(LNode);s->data=e; s->next=p->next;p->next=s;return OK;3. 刪除：Status

24、 ListDelete_L(LinkList &L,int &e) /刪除j=0;p=L;while(p->next && j<i-1) /尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)p=p->next;+j;if(!(p->next)|j>i-1)return ERROR;q=p->next;p->next=q->next;e=q->data;free(q);return OK;/ListDelete_L4. 查找:Status GetElem_L(LinkList L,int i , ElemType &e)

25、 /查找p=L->next;j=1;while(p && j<i)/按序號(hào)查找p=p->next;j+;if(!p|j>1)retun ERRORe=p->data;retun OK;/GetElem.L二、源代碼#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0typedef struct LNode int data;struct LNode * next;LNode, * LinkList;/逆序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈線性表L。vo

26、id CreateList_L(LinkList &L) int i,x;LNode *p=NULL;L=(LinkList)malloc(sizeof(LNode);/生成新的結(jié)點(diǎn)L->next=NULL; /先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 printf("請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù):"); scanf("%d",&x); printf("請(qǐng)輸入各結(jié)點(diǎn)元素的值為:");for(i=x;i>0;-i) /逆序輸入x個(gè)元素的值 p=(LinkList)malloc(sizeof(LNode);scanf("%d&q

27、uot;,&p->data);p->next = L->next;L->next = p; /插入到表頭p=L->next; /將p指向頭結(jié)點(diǎn) /輸出已創(chuàng)建的鏈表printf("逆序輸出鏈表為:n"); while(p)printf("%d ",p->data);p=p->next;/*插入*int ListInsert_L(LinkList &L) LNode *p,*s;int j=0,e,i;p=L;printf("請(qǐng)輸入所要插入的位置:");scanf("%d

28、",&i);printf("請(qǐng)輸入所要插入的數(shù):");scanf("%d",&e);while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)printf("輸入數(shù)據(jù)有誤,請(qǐng)輸入數(shù)值在1 - x+1之間輸入");s=(LinkList)malloc(sizeof(LNode);s->data=e; s->next=p->next;p->next=s;p=L ->next;while(p)printf("%5d&qu

29、ot;,p->data);p=p->next;printf("n");return OK; /*刪除*int ListDelete_L(LinkList &L,int &e) LNode *p,*q;int i,j=0;p=L;printf("請(qǐng)輸入要?jiǎng)h除的第幾個(gè)結(jié)點(diǎn):"); scanf("%d",&i);while(p->next && j<i-1) /尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)p=p->next;+j;if(!(p->next)|j>i-1)p

30、rintf("輸入的數(shù)值錯(cuò)誤或刪除位置不合理");q=p->next;p->next=q->next;e=q->data;free(q);/釋放被刪除結(jié)點(diǎn)printf("被刪除結(jié)點(diǎn)的數(shù)值為: %dn",e);p=L ->next;while(p)printf("%5d",p->data);p=p->next;printf("n");return OK; /*計(jì)數(shù)*void CountList_L(LinkList &L) int i=0;LNode *p=L->

31、;next;while(p)i+;p=p->next;printf("結(jié)點(diǎn)個(gè)數(shù)為:%dn",i); /*查找*int LocateElem_L(LinkList L) LinkList p=L;int i,j=0;printf("請(qǐng)輸入要查找的數(shù)的序號(hào):");scanf("%d",&i);while(p && j<i)/按序號(hào)查找p=p->next;j+;if(j!=i|!p)printf("參數(shù)i錯(cuò)或單鏈表不存在");return(NULL);printf("你

32、查找的第 %d 個(gè)結(jié)點(diǎn)的數(shù)值為 %dn",i,p->data);return OK;/*排序*void SortList_L(LinkList L) int i,j,t,k = 0;LNode *p = L->next,*q;while(p)k+;p=p->next;p=L->next; q=p->next; /初始化for(i=0;i<k-1;+i)p = L->next;for(j=0,p;j<k-i-1;+j,p=p->next)q = p->next;if(p->data > q->data) /升

33、序t=p->data;p->data=q->data;q->data=t;p=L->next;printf("輸出升序的鏈表為:n");while(p)printf("%5d",p->data);p=p->next;printf("n"); /*輸出*void OutputList_L(LinkList L) LNode *p;p=L->next;while(p)printf("%5d",p->data);p=p->next;printf("n&

34、quot;);/*逆置*int ReverseList_L(LinkList &L) LNode *p ,*q;p=L->next;q=p->next;L->next=NULL;while(p->next)p->next=L->next; L->next=p; p=q;q=q->next;p->next=L->next;L->next=p;printf("逆置后的鏈表結(jié)果為:");for(p=L->next;p;p=p->next)printf("%d ",p->

35、data);printf("n");return 0;/*主函數(shù)*int main()LinkList L=NULL;int i,e;printf("逆序輸入創(chuàng)建一個(gè)鏈表并實(shí)現(xiàn)下列功能n");printf(" 1. 創(chuàng)建 n");printf(" 2. 插入 n");printf(" 3. 刪除 n");printf(" 4. 計(jì)數(shù) n");printf(" 5. 查找 n");printf(" 6. 排序 n");printf(&qu

36、ot; 7. 輸出 n");printf(" 8. 逆置 n");for(;)printf("請(qǐng)?jiān)?-8功能中選擇一個(gè): ");scanf("%d",&i);/*函數(shù)調(diào)用*switch(i)case 1:CreateList_L(L); break;case 2:ListInsert_L(L); break;case 3:ListDelete_L(L,e); break;case 4:CountList_L(L); break;case 5:LocateElem_L(L); break;case 6:SortList

37、_L(L); break;case 7:OutputList_L(L); break;case 8:ReverseList_L(L); break;default:printf("輸入錯(cuò)誤");printf("n");return 0;三、操作結(jié)果項(xiàng)目三：二叉樹(shù)的操作：一、考查知識(shí)點(diǎn)：1.對(duì)任意給定的二叉樹(shù)（頂點(diǎn)數(shù)自定）建立它的二叉鏈表存儲(chǔ)結(jié)構(gòu)； 2.利用棧的五種基本運(yùn)算（置空棧、進(jìn)棧、出棧、取棧頂元素、判?？眨?shí)現(xiàn)二叉樹(shù)的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。 3. 求二叉樹(shù)高度、結(jié)點(diǎn)數(shù)、度為1的結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)。二、算法：1.創(chuàng)建二叉樹(shù)：S

38、tatus Createbitree(bitree &t) /功能1：構(gòu)建二叉樹(shù)的二叉鏈表scanf(& ch); /按先序遍歷建立二叉樹(shù)if(ch=)T=NULL;elseif(!(T=(BiTNde)malloc(sizeof(BiTNode)exit(OVERFLOW);T->data=ch;Createbitree(t->lchild);Createbitree(t->rchild);Return OK;/CreatBiTree2.先序遍歷： Status PreOrderTraverse(Bitree T,Status（* visit）（TElemT

39、ype)） /采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù) if(T)if(Visist(T->data)if (PreOrderTraverse(p->lchild,Visit);if PreOrderTraverse(p->rchild,Visit);return OK;return ERROR;elese returnOK; / PreOrderTraverse3.中序遍歷：Status InOrderTraverse(Bitree T,Status（* Visit）（TElemType)）InitStack(s);Push (S,T);While(!St

40、ackEmpty(s)While(GetTop(s,p)&&p)Push(S,p->lchild);Pop(S,p);If(!StackEmpty(s)Pop(s,p);if (!Visit(p->data)retu ERROR;Push(S,p->rchild);/if/WhileRetun OK;/ InOrderTraverse二、源代碼#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define true 1#define false 0#define ok

41、 1#define error 0#define overflow -2typedef void status;typedef char BTtype;typedef char Stype;typedef struct BTnode /定義二叉樹(shù)存儲(chǔ)結(jié)構(gòu) BTtype data; struct BTnode *lc,*rc;BTnode,*BTtree;typedef struct/定義棧的存儲(chǔ)結(jié)構(gòu)Stype *base;Stype *top;int stacksize; Sqstack;int max(int a,int b)return a>b?a:b;char Creat(BTtr

42、ee &t)/創(chuàng)建char ch;/printf("按順序輸入二叉樹(shù)各節(jié)點(diǎn)的值："); scanf("%c",&ch);if(ch=' ') t=NULL;else if(!(t=(BTtree )malloc(sizeof(BTnode)printf("創(chuàng)建失敗。"); exit(overflow);t->data=ch;Creat(t->lc);Creat(t->rc);return ok;char orderx(BTtree &t)/先序BTtree p=t;if(p)p

43、rintf("%c",p->data);orderx(p->lc); orderx(p->rc);return 0;char orderz(BTtree &t)/中序BTtree p=t;if(p)orderz(p->lc);printf("%c",p->data); orderz(p->rc);return 0;char orderh(BTtree &t)/后序BTtree p=t;if(p)orderh(p->lc); orderh(p->rc);printf("%c"

44、;,p->data);return 0;int Depth(BTtree t)/求深度int d,dl,dr;if(!t) d=0;else dl=Depth(t->lc); dr=Depth(t->rc);d=max(dl,dr)+1; return d;int Nodes(BTtree &t)/結(jié)點(diǎn)數(shù) int num1,num2; if(t=NULL) return 0; else num1=Nodes(t->lc); num2=Nodes(t->rc); return (num1+num2+1); void Degree(BTtree t,int &

45、amp;n)/度為1的結(jié)點(diǎn)個(gè)數(shù)/int n=0;if(t)if(t->lc && !t->rc) | (!t->lc && t->rc) n+;Degree(t->lc,n);Degree(t->rc,n);void Leaves(BTtree &t,int &yz)/葉子數(shù)/int yz=0;if(t)if(!t->lc) && (!t->rc) yz+;Leaves(t->lc,yz);Leaves(t->rc,yz);/return yz;void Quit()/退

46、出exit(0);int main()BTtree t;int yz=0;int n=0;int x;/用于case或ifprintf("需先按順序輸入二叉樹(shù)各節(jié)點(diǎn)的值："); if(Creat(t) printf("創(chuàng)建成功！n");printf("1、先序n2、中序n3、后序n4、求深度n5、求結(jié)點(diǎn)數(shù)n6、求度為一的結(jié)點(diǎn)數(shù)n7、求葉子數(shù)n8、退出n");/*for(;)printf("請(qǐng)選擇1-9：");scanf("%d",&x);switch(x) case 1:printf(&

47、quot;按順序輸入二叉樹(shù)各節(jié)點(diǎn)的值："); Creat(t); printf("創(chuàng)建成功！n"); break; case 2:printf("先序遍歷二叉樹(shù)："); orderx(t); printf("n");break; case 3:printf("中序遍歷二叉樹(shù)："); orderz(t); printf("n");break; case 4:printf("后序遍歷二叉樹(shù)："); orderh(t); printf("n");break;case 5:printf("二叉樹(shù)的深度為：%dn",Depth(t);break;case 6:printf("二叉樹(shù)的節(jié)點(diǎn)數(shù)為：%dn",Nodes(t);break;case 7:Leaves(t,yz); printf("葉子數(shù)為：%dn",yz);break;case 8:Degree(t,n); printf("度為1的節(jié)點(diǎn)個(gè)數(shù)為：%dn",n);break; case 9