数据结构实验七

数据结构实验报告一一实验7

一、实验目的

掌握二叉链表及二叉树的创建、遍历；

二、实验内容

1、（必做题）假设二叉树中数据元素类型是字符型，请采用二叉链表实现二叉树的以下基本操作：

（1）根据二叉树的先序序列和中序序列构造二叉树；

（2）根据先序遍历二叉树；

（3）根据中序遍历二叉树；

（4）根据后序遍历二叉树。

测试数据包括如下错误数据：

先序：1234；中序：12345

先序：1234；中序：1245

先序：1234；中序：4231

2、（必做题）对于一棵二叉树，请实现：

（1）计算二叉树的叶子数目；

（2）计算二叉树的深度。

3、（选做题）给定n个权值，请构造它们的最优二叉树（赫夫曼树）。

三、算法描述

（采用自然语言描述）

1,分别输入n个先序序列和中序序列，先序序列中第一个字符为根节点，在中序序列中找到根节

点所在的位置，在根节点左边的为左子树节点，在根节点右边的为右子树节点，然后采用递归的形式依

次对左右子树进行构造；二叉树的遍历也是采用递归的形式，先序遍历二叉树：先序遍历根，先序遍历

左子树，先序遍历右子树；中序遍历二叉树：中序遍历左子树，中序遍历根，中序遍历右子树；后序遍

历二叉树：后序遍历左子树，后序遍历右子树，后序遍历根。

四、详细设计

（画出程序流程图）

五、程序代码

(给出必要注释)

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("请输入先序序列\n")；

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

pre|n++]=ch;

printf("请输入中序序列\n")；

n=0;

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

in[n++]=ch;

b=createBT(pre,in,n);

printf("先序遍历二叉树:\n");

showBTPreOrder(b);

printf("\nM);

printf("中序遍历二叉树:\n)

showBTInOrder(b);

printf(n\nM);

printf("后序遍历二叉树:\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("请输入先序序列\n)

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

pre[n++]=ch;

printf("请输入中序序列\n)

n=0;

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

in[n++]=ch;

b=createBT(pre,in,n);

printf("二叉树的叶子数目为：%d\n",Count(b));

printf("二叉树的深度为：%d\n",TreeDepth(b));

return0;

}

六、测试和结果

(给出测试用例，并给出测试结果)

1、

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

请输入先序序列

ABDHKECFIGJ

请输入中序序列

HKDBEAIFCGJ

先序遍历二叉树：

ABDHKECFIGJ

巾序遍历二叉树：

HKDBEAIFCGJ

后序遍历二叉树：

KHDEBIFJGCA

Processreturned0(0x0)executiontime：25.048s

Pres