1、仲愷農(nóng)業(yè)工程學(xué)院實(shí)驗(yàn)報(bào)告紙信息科學(xué)與技術(shù)（院、系） 計(jì)算機(jī) 專業(yè) 144 班 數(shù)據(jù)結(jié)構(gòu)與算法 課學(xué)號(hào)201420224417 姓名劉智龍 實(shí)驗(yàn)日期 2015.12.8 教師評(píng)定 一、實(shí)驗(yàn)?zāi)康?、掌握二叉樹的特點(diǎn)，以及的二叉鏈表存儲(chǔ)結(jié)構(gòu)。2、熟練掌握二叉樹的各種操作，如建立、遍歷、查找和輸出。3、利用已經(jīng)掌握的知識(shí)進(jìn)行實(shí)際應(yīng)用。二、實(shí)驗(yàn)環(huán)境1) 硬件：每個(gè)學(xué)生需配備計(jì)算機(jī)一臺(tái)，操作系統(tǒng)：Windows2000/XP。2) 軟件：visual c+6.0。三、實(shí)驗(yàn)題目和實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)題目：二叉樹操作及應(yīng)用實(shí)驗(yàn)內(nèi)容：1、基本題：教材實(shí)驗(yàn)7.1、實(shí)驗(yàn)7.2、實(shí)驗(yàn)7.3的（1）和（2）2、附加題：實(shí)驗(yàn)7.

2、6、實(shí)驗(yàn)7.8、四、實(shí)驗(yàn)項(xiàng)目的程序結(jié)構(gòu)（包含的各個(gè)文件中的函數(shù)調(diào)用功能描述、程序中的函數(shù)調(diào)用關(guān)系圖）(可寫可不寫) exp2-1.cpp文件main algo2-1.cpp文件InitListListInsert五、實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)結(jié)果（程序運(yùn)行結(jié)果的截圖）實(shí)驗(yàn)7.1結(jié)果：實(shí)驗(yàn)7.2結(jié)果：實(shí)驗(yàn)7.3結(jié)果：六、附錄（程序代碼）實(shí)驗(yàn)7.1源代碼：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/數(shù)據(jù)元素s

3、truct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void CreateBTNode(BTNode *&b,char *str)/由str串創(chuàng)建二叉鏈BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉樹初始時(shí)為空ch=strj;while (ch!='0')/str未掃描完時(shí)循環(huán) switch(ch) case '(':top+;Sttop=p;k=1; break;/為左節(jié)點(diǎn)case ')'

4、:top-;break;case ',':k=2; break; /為右節(jié)點(diǎn)default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL; if (b=NULL) /p指向二叉樹的根節(jié)點(diǎn)b=p;else /已建立二叉樹根節(jié)點(diǎn)switch(k) case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x)/

5、返回data域?yàn)閤的節(jié)點(diǎn)指針BTNode *p;if (b=NULL) return NULL;else if (b->data=x) return b;elsep=FindNode(b->lchild,x);if (p!=NULL) return p;else return FindNode(b->rchild,x);BTNode *LchildNode(BTNode *p)/返回*p節(jié)點(diǎn)的左孩子節(jié)點(diǎn)指針 return p->lchild;BTNode *RchildNode(BTNode *p)/返回*p節(jié)點(diǎn)的右孩子節(jié)點(diǎn)指針 return p->rchild;

6、int BTNodeDepth(BTNode *b)/求二叉樹b的深度 int lchilddep,rchilddep; if (b=NULL) return(0); /空樹的高度為0 else lchilddep=BTNodeDepth(b->lchild);/求左子樹的高度為lchilddep rchilddep=BTNodeDepth(b->rchild);/求右子樹的高度為rchilddepreturn (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1); void DispBTNode(BTNode *b)/以括號(hào)表

7、示法輸出二叉樹if (b!=NULL)printf("%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL)printf("(");DispBTNode(b->lchild);if (b->rchild!=NULL) printf(",");DispBTNode(b->rchild);printf(")");int BTWidth(BTNode *b) /求二叉樹b的寬度struct int lno;/節(jié)點(diǎn)的層次編號(hào)BTNode *

8、p;/節(jié)點(diǎn)指針 QuMaxSize;/定義順序非循環(huán)隊(duì)列int front,rear;/定義隊(duì)首和隊(duì)尾指針int lnum,max,i,n;front=rear=0;/置隊(duì)列為空隊(duì) if (b!=NULL) rear+;Qurear.p=b;/根節(jié)點(diǎn)指針入隊(duì)Qurear.lno=1;/根節(jié)點(diǎn)的層次編號(hào)為1while (rear!=front)/隊(duì)列不為空f(shuō)ront+;b=Qufront.p;/隊(duì)頭出隊(duì)lnum=Qufront.lno;if (b->lchild!=NULL)/左孩子入隊(duì)rear+;Qurear.p=b->lchild;Qurear.lno=lnum+1;if (b-

9、>rchild!=NULL)/右孩子入隊(duì)rear+;Qurear.p=b->rchild;Qurear.lno=lnum+1;max=0;lnum=1;i=1;while (i<=rear)n=0;while (i<=rear && Qui.lno=lnum) n+;i+;lnum=Qui.lno;if (n>max) max=n;return max;elsereturn 0;int Nodes(BTNode *b)/求二叉樹b的節(jié)點(diǎn)個(gè)數(shù)int num1,num2; if (b=NULL) return 0; else if (b->lch

10、ild=NULL && b->rchild=NULL) return 1; else num1=Nodes(b->lchild); num2=Nodes(b->rchild); return (num1+num2+1);int LeafNodes(BTNode *b)/求二叉樹b的葉子節(jié)點(diǎn)個(gè)數(shù)int num1,num2; if (b=NULL) return 0; else if (b->lchild=NULL && b->rchild=NULL) return 1; else num1=LeafNodes(b->lchild

11、); num2=LeafNodes(b->rchild); return (num1+num2);void DestroyBTNode(BTNode *&b)if (b!=NULL)DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)");printf("二叉樹的基本運(yùn)算如下:n");printf("

12、 (1)輸出二叉樹:");DispBTNode(b);printf("n");printf(" (2)H節(jié)點(diǎn):");p=FindNode(b,'H');if (p!=NULL)lp=LchildNode(p);if (lp!=NULL) printf("左孩子為%c ",lp->data);elseprintf("無(wú)左孩子 ");rp=RchildNode(p);if (rp!=NULL)printf("右孩子為%c",rp->data);elseprint

13、f("無(wú)右孩子 ");printf("n");printf(" (3)二叉樹b的深度:%dn",BTNodeDepth(b);printf(" (4)二叉樹b的寬度:%dn",BTWidth(b);printf(" (5)二叉樹b的節(jié)點(diǎn)個(gè)數(shù):%dn",Nodes(b);printf(" (6)二叉樹b的葉子節(jié)點(diǎn)個(gè)數(shù):%dn",LeafNodes(b);printf(" (7)釋放二叉樹bn");DestroyBTNode(b);實(shí)驗(yàn)7.2源代碼：#incl

14、ude <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/數(shù)據(jù)元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void CreateBTNode(BTNode *&b,char *str)/由str串創(chuàng)建二叉鏈BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的

15、二叉樹初始時(shí)為空ch=strj;while (ch!='0')/str未掃描完時(shí)循環(huán) switch(ch) case '(':top+;Sttop=p;k=1; break;/為左節(jié)點(diǎn)case ')':top-;break;case ',':k=2; break; /為右節(jié)點(diǎn)default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL; if (b=NULL) /p指向二叉樹的根節(jié)點(diǎn)b=p;else /已建立二叉樹根節(jié)點(diǎn)

16、switch(k) case 1:Sttop->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b)/以括號(hào)表示法輸出二叉樹if (b!=NULL)printf("%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL)printf("(");DispBTNode(b->lchild);if (b->rchild!=NULL) printf(",&q

17、uot;);DispBTNode(b->rchild);printf(")");void DestroyBTNode(BTNode *&b)if (b!=NULL)DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);void PreOrder(BTNode *b) /先序遍歷的遞歸算法if (b!=NULL) printf("%c ",b->data);/訪問(wèn)根節(jié)點(diǎn)PreOrder(b->lchild);/遞歸訪問(wèn)左子樹PreOrder(b->rc

18、hild);/遞歸訪問(wèn)右子樹void PreOrder1(BTNode *b)BTNode *StMaxSize,*p; int top=-1; if (b!=NULL) top+;/根節(jié)點(diǎn)入棧 Sttop=b; while (top>-1)/棧不為空時(shí)循環(huán) p=Sttop;/退棧并訪問(wèn)該節(jié)點(diǎn) top-; printf("%c ",p->data); if (p->rchild!=NULL)/右孩子入棧 top+; Sttop=p->rchild; if (p->lchild!=NULL)/左孩子入棧 top+; Sttop=p->lch

19、ild;printf("n");void InOrder(BTNode *b) /中序遍歷的遞歸算法if (b!=NULL) InOrder(b->lchild);/遞歸訪問(wèn)左子樹printf("%c ",b->data);/訪問(wèn)根節(jié)點(diǎn)InOrder(b->rchild);/遞歸訪問(wèn)右子樹void InOrder1(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)p=b;while (top>-1 | p!=NULL)while (p!=NULL)top+;Sttop=p

20、;p=p->lchild;if (top>-1)p=Sttop;top-;printf("%c ",p->data);p=p->rchild;printf("n");void PostOrder(BTNode *b) /后序遍歷的遞歸算法if (b!=NULL) PostOrder(b->lchild);/遞歸訪問(wèn)左子樹PostOrder(b->rchild);/遞歸訪問(wèn)右子樹printf("%c ",b->data);/訪問(wèn)根節(jié)點(diǎn)void PostOrder1(BTNode *b)BTNod

21、e *StMaxSize;BTNode *p;int flag,top=-1;/棧指針置初值if (b!=NULL)dowhile (b!=NULL)/將t的所有左節(jié)點(diǎn)入棧top+;Sttop=b;b=b->lchild;p=NULL;/p指向當(dāng)前節(jié)點(diǎn)的前一個(gè)已訪問(wèn)的節(jié)點(diǎn)flag=1;while (top!=-1 && flag)b=Sttop;/取出當(dāng)前的棧頂元素if (b->rchild=p)/右子樹不存在或已被訪問(wèn),訪問(wèn)之printf("%c ",b->data);/訪問(wèn)*b節(jié)點(diǎn)top-;p=b;/p指向則被訪問(wèn)的節(jié)點(diǎn)elseb=b-

22、>rchild;/t指向右子樹flag=0; while (top!=-1);printf("n"); void TravLevel(BTNode *b)BTNode *QuMaxSize;/定義循環(huán)隊(duì)列int front,rear;/定義隊(duì)首和隊(duì)尾指針front=rear=0;/置隊(duì)列為空隊(duì)列 if (b!=NULL) printf("%c ",b->data); rear+;/節(jié)點(diǎn)指針進(jìn)入隊(duì)列Qurear=b; while (rear!=front)/隊(duì)列不為空 front=(front+1)%MaxSize;b=Qufront;/隊(duì)頭出

23、隊(duì)列if (b->lchild!=NULL)/輸出左孩子,并入隊(duì)列printf("%c ",b->lchild->data);rear=(rear+1)%MaxSize;Qurear=b->lchild;if (b->rchild!=NULL)/輸出右孩子,并入隊(duì)列printf("%c ",b->rchild->data);rear=(rear+1)%MaxSize;Qurear=b->rchild; printf("n");void main()BTNode *b;CreateBTNo

24、de(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"); printf("二叉樹b:");DispBTNode(b);printf("n");printf("層次遍歷序列:");TravLevel(b);printf("先序遍歷序列:n");printf(" 遞歸算法:");PreOrder(b);printf("n");printf(" 非遞歸算法:");PreOrder1(b);printf("中序

25、遍歷序列:n");printf(" 遞歸算法:");InOrder(b);printf("n");printf(" 非遞歸算法:");InOrder1(b);printf("后序遍歷序列:n");printf(" 遞歸算法:");PostOrder(b);printf("n");printf(" 非遞歸算法:");PostOrder1(b);DestroyBTNode(b); 實(shí)驗(yàn)7.3源代碼：#include <stdio.h>#i

26、nclude <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;/數(shù)據(jù)元素struct node *lchild;/指向左孩子struct node *rchild;/指向右孩子 BTNode;void CreateBTNode(BTNode *&b,char *str)/由str串創(chuàng)建二叉鏈BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉樹初始時(shí)為空ch=strj;while

27、 (ch!='0')/str未掃描完時(shí)循環(huán) switch(ch) case '(':top+;Sttop=p;k=1; break;/為左節(jié)點(diǎn)case ')':top-;break;case ',':k=2; break; /為右節(jié)點(diǎn)default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL; if (b=NULL) /p指向二叉樹的根節(jié)點(diǎn)b=p;else /已建立二叉樹根節(jié)點(diǎn)switch(k) case 1:Stto

28、p->lchild=p;break;case 2:Sttop->rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b)/以括號(hào)表示法輸出二叉樹if (b!=NULL)printf("%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL)printf("(");DispBTNode(b->lchild);if (b->rchild!=NULL) printf(",");DispBTNode(b-&g

29、t;rchild);printf(")");void DestroyBTNode(BTNode *&b)if (b!=NULL)DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);void AllPath(BTNode *b)struct snode BTNode *node;/存放當(dāng)前節(jié)點(diǎn)指針 int parent;/存放雙親節(jié)點(diǎn)在隊(duì)列中的位置 QuMaxSize;/定義順序隊(duì)列int front,rear,p;/定義隊(duì)頭和隊(duì)尾指針 front=rear=-1;/置隊(duì)列為空隊(duì)列rear+;

30、 Qurear.node=b;/根節(jié)點(diǎn)指針進(jìn)入隊(duì)列Qurear.parent=-1;/根節(jié)點(diǎn)沒(méi)有雙親節(jié)點(diǎn) while (front<rear)/隊(duì)列不為空 front+;b=Qufront.node;/隊(duì)頭出隊(duì)列if (b->lchild=NULL && b->rchild=NULL)/*b為葉子節(jié)點(diǎn)printf(" %c到根節(jié)點(diǎn)逆路徑:",b->data);p=front;while (Qup.parent!=-1)printf("%c ",Qup.node->data);p=Qup.parent;prin

31、tf("%cn",Qup.node->data);if (b->lchild!=NULL)/左孩子入隊(duì)列rear+;Qurear.node=b->lchild;Qurear.parent=front;if (b->rchild!=NULL)/右孩子入隊(duì)列rear+;Qurear.node=b->rchild;Qurear.parent=front; void AllPath1(BTNode *b,ElemType path,int pathlen)int i;if (b!=NULL)if (b->lchild=NULL &&

32、; b->rchild=NULL)/*b為葉子節(jié)點(diǎn)printf(" %c到根節(jié)點(diǎn)逆路徑: %c ",b->data,b->data);for (i=pathlen-1;i>=0;i-)printf("%c ",pathi);printf("n");elsepathpathlen=b->data;/將當(dāng)前節(jié)點(diǎn)放入路徑中pathlen+;/路徑長(zhǎng)度增1AllPath1(b->lchild,path,pathlen);/遞歸掃描左子樹AllPath1(b->rchild,path,pathlen);/遞歸掃描右子樹pathlen-;/恢復(fù)環(huán)境void LongPath(BTNode *b,ElemType path,int pathlen,ElemType longpath,int &longpathlen)int i;if (b=NULL