數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告一一實(shí)驗(yàn)7

一、實(shí)驗(yàn)?zāi)康?/p>

掌握二叉鏈表及二叉樹(shù)的創(chuàng)建、遍歷；

二、實(shí)驗(yàn)內(nèi)容

1、（必做題）假設(shè)二叉樹(shù)中數(shù)據(jù)元素類型是字符型，請(qǐng)采用二叉鏈表實(shí)現(xiàn)二叉樹(shù)的以下基本操作：

（1）根據(jù)二叉樹(shù)的先序序列和中序序列構(gòu)造二叉樹(shù)；

（2）根據(jù)先序遍歷二叉樹(shù)；

（3）根據(jù)中序遍歷二叉樹(shù)；

（4）根據(jù)后序遍歷二叉樹(shù)。

測(cè)試數(shù)據(jù)包括如下錯(cuò)誤數(shù)據(jù)：

先序：1234；中序：12345

先序：1234；中序：1245

先序：1234；中序：4231

2、（必做題）對(duì)于一棵二叉樹(shù)，請(qǐng)實(shí)現(xiàn)：

（1）計(jì)算二叉樹(shù)的葉子數(shù)目；

（2）計(jì)算二叉樹(shù)的深度。

3、（選做題）給定n個(gè)權(quán)值，請(qǐng)構(gòu)造它們的最優(yōu)二叉樹(shù)（赫夫曼樹(shù)）。

三、算法描述

（采用自然語(yǔ)言描述）

1,分別輸入n個(gè)先序序列和中序序列，先序序列中第一個(gè)字符為根節(jié)點(diǎn)，在中序序列中找到根節(jié)

點(diǎn)所在的位置，在根節(jié)點(diǎn)左邊的為左子樹(shù)節(jié)點(diǎn)，在根節(jié)點(diǎn)右邊的為右子樹(shù)節(jié)點(diǎn)，然后采用遞歸的形式依

次對(duì)左右子樹(shù)進(jìn)行構(gòu)造；二叉樹(shù)的遍歷也是采用遞歸的形式，先序遍歷二叉樹(shù)：先序遍歷根，先序遍歷

左子樹(shù)，先序遍歷右子樹(shù)；中序遍歷二叉樹(shù)：中序遍歷左子樹(shù)，中序遍歷根，中序遍歷右子樹(shù)；后序遍

歷二叉樹(shù)：后序遍歷左子樹(shù)，后序遍歷右子樹(shù)，后序遍歷根。

四、詳細(xì)設(shè)計(jì)

（畫(huà)出程序流程圖）

五、程序代碼

(給出必要注釋)

1、

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#defineN100

typedefcharElementType;

typedefstructnode

(

ElementTypedata;

structnode*leftChild;

structnode*rightChild;

}BTNode;

BTNode*createBT(char*pre,char*in,intn)

(

BTNode*b;

char*p;

intk;

if(n<=0)

returnNULL;

b=(BTNode*)malloc(sizeof(BTNode));

b->data=*pre;

intj=0;

for(p=in;p<in+n;p++)

(

if(*p==*pre)

break;

)

k=p-in;

b->leftChild=createBT(pre+1,in,k);

b->rightChild=createBT(pre+1+k,p+1,n-k-1);

returnb;

voidshowBTPreOrder(BTNode*b)

if(b!=NULL)

(

printf("%cn,b->data);

showBTPreOrder(b->leftChild);

showBTPreOrder(b->rightChild);

voidshowBTInOrder(BTNode*b)

(

if(b!=NULL)

(

showBTInOrder(b->leftChild);

printf(M%c",b->data);

showBTInOrder(b->rightChild);

)

)

voidshowBTTailOrder(BTNode*b)

(

if(b==NULL)

return;

showBTTailOrder(b->leftChild);

showBTTailOrder(b->rightChild);

printf(H%c*',b->data);

)

intmain()

{

charpre[N];

charin[N];

intn=0;

charch;

BTNode*b=NULL;

printf("請(qǐng)輸入先序序列\(zhòng)n")；

while((ch=getchar())&&ch!

pre|n++]=ch;

printf("請(qǐng)輸入中序序列\(zhòng)n")；

n=0;

while((ch=getchar())&&ch!='\n')

in[n++]=ch;

b=createBT(pre,in,n);

printf("先序遍歷二叉樹(shù):\n");

showBTPreOrder(b);

printf("\nM);

printf("中序遍歷二叉樹(shù):\n)

showBTInOrder(b);

printf(n\nM);

printf("后序遍歷二叉樹(shù):\n")；

showBTTailOrder(b);

printf(n\nn);

return0;

)

2、

#include<stdio.h>

#include<stdlib.h>

#include<malloc.h>

#defineN100

typedefcharElementType;

typedefstructnode

{

ElementTypedata;

structnode*leftChild;

structnode*rightChild;

JBTNode;

BTNode*createBT(char*pre,char*in,intn)

(

BTNode*b;

char*p;

intk;

if(n<=0)

returnNULL;

b=(BTNode*)malloc(sizeof(BTNode));

b->data=*pre;

intj=0;

for(p=in;p<in+n;p++)

if(*p==*pre)

break;

)

k=p-in;

b->leftChild=createBT(pre+1,in,k);

b->rightChild=createBT(pre+1+k,p+1,n-k-1);

returnb;

)

intCounl(BTNode*top){

if(top==NULL){

return0;

)

elseif((top->leftChild==NULL)&&(top->rightChild==NULL)){

return1;

}

else{

returnCount(top->leftChild)+Count(top->rightChild);

)

)

intTreeDepth(BTNode*top)

(

intrightdep=0;

intleftdep=0;

if(top==NULL)

return-1;

if(top->leftChild!=NULL)

leftdep=TreeDepth(top->leftChild);

else

leftdep=-l;

if(top->rightChild!=NULL)

rightdep=TreeDepth(top->rightChild);

else

rightdep="l;

return(rightdep>leftdep)?rightdep+1:leftdep+1;

intmain()

charpre[N];

charin[N];

intn=0;

charch;

BTNode*b=NULL;

printf("請(qǐng)輸入先序序列\(zhòng)n)

while((ch=getchar())&&ch!='\n')

pre[n++]=ch;

printf("請(qǐng)輸入中序序列\(zhòng)n)

n=0;

while((ch=getchar())&&ch!='\n')

in[n++]=ch;

b=createBT(pre,in,n);

printf("二叉樹(shù)的葉子數(shù)目為：%d\n",Count(b));

printf("二叉樹(shù)的深度為：%d\n",TreeDepth(b));

return0;

}

六、測(cè)試和結(jié)果

(給出測(cè)試用例，并給出測(cè)試結(jié)果)

1、

■C:\Users\Administrator\Desktop\shiyan7_1_1\bin\Debug\shiyan7_1_1.exe

請(qǐng)輸入先序序列

ABDHKECFIGJ

請(qǐng)輸入中序序列

HKDBEAIFCGJ

先序遍歷二叉樹(shù)：

ABDHKECFIGJ

巾序遍歷二叉樹(shù)：

HKDBEAIFCGJ

后序遍歷二叉樹(shù)：

KHDEBIFJGCA

Processreturned0(0x0)executiontime：25.048s

Pres