数据结构二叉树实验报告

来源：99网

数据结构实验报告

课程数据结构_实验名称二叉树实验

院系电信学院专业班级计科10-4

姓名学号

一、实验构思

首先构造二叉树的存储结构，用data存储当前节点的值，分别用lchild，rchild表示该节点的左右孩子。然后应用BiTreeCreate函数，根据用户的输入构造二叉树，当输入时表示没有孩子。采用递归的思想构造Preorder，Inorder，Postorder函数，分别实现二叉树的先序，中序，和后序的遍历。然后编写了Sumleaf，Depth函数，来求叶子节点的数目和二叉树的深度。

二、实验设计

二叉树的存储结构：typedefstructBiTNode

chardata;

structBiTNodelchild；

structBiTNoderchild;

}BiTNode,BiTree;

子程序模块：

BiTreeCreate(BiTreeT)创建二叉树{

charch;ch=getchar();if(ch=='')T=NULL;else{if(!(T=(BiTNode)malloc(sizeof(BiTNode))))printf("Error!");T->data=ch;T->lchild=Create(T->lchild);T->rchild=Create(T->rchild);}

returnT;

voidPreorder(BiTreeT)先序遍历二叉树{

if(T){printf("%c",T->data);Preorder(T->lchild);Preorder(T->rchild);}

intSumleaf(BiTreeT)求二叉树T的叶子节点数目{

intsum=0,m,n;if(T){if((!T->lchild)(!T->rchild))sum++;m=Sumleaf(T->lchild);sum+=m;n=Sumleaf(T->rchild);sum+=n;}

returnsum;

voidInorder(BiTreeT)中序遍历二叉树{

if(T)

Inorder(T->lchild);

printf("%c",T->data);

Inorder(T->rchild);

voidPostorder(BiTreeT)后序遍历二叉树{

if(T)

Postorder(T->lchild);

Postorder(T->rchild);

printf("%c",T->data);

intDepth(BiTreeT)求二叉树的深度{

if(!T)

dep=0;intdep=0,depl,depr;

else{

depl=Depth(T->lchild);

depr=Depth(T->rchild);

dep=1+(depl>deprdepl:depr);}

returndep;

主程序模块：

intmain()

BiTreeT=0;intsum,dep;

printf("请输入你需要建立的二叉树 ");

printf(" 例如输入序列ABCDEGF（其中的表示空）并且输入过程中不要加回车输入完之后可以按回车退出 ");

T=Create(T);

printf("先序遍历的结果是： ");

Preorder(T);

printf(" ");

printf("中序遍历的结果是： ");

Inorder(T);

printf(" ");

printf("后序遍历的结果是： ");

Postorder(T);

printf(" ");

printf("统计的叶子数： ");

sum=Sumleaf(T);

printf("%d",sum);

printf(" 统计树的深度： ");

dep=Depth(T);

printf(" %d ",dep);

三、实现描述

各函数原型说明：BiTreeCreate(BiTreeT)/构造二叉树T

voidPreorder(BiTreeT)/对二叉树T进行先序遍历voidInorder(BiTreeT)/对二叉树T进行中序遍历

voidPostorder(BiTreeT)/对二叉树T进行后序遍历intSumleaf(BiTreeT)/求二叉树T的叶子节点数目intDepth(BiTreeT)/求二叉树T的深度

函数间的调用关系：intmain()

调用Create函数，构造二叉树T

调用Preorder函数，对二叉树进行先序遍历

调用Inorder函数，对二叉树进行中序遍历

调用Postorder函数，对二叉树进行后序遍历

调用Sumleaf函数，统计二叉树的叶子节点数

调用Depth函数，统计二叉树的深度

时间复杂度分析：在对二叉树进行遍历的过程中，用到了递归的思想，对于二叉树中的每一个结点，从头到尾只访问过一次，所以，对于含有N个结点的二叉树，其遍历的时间复杂度为o(n)。

四、源程序代码

include

defineNULL0

typedefstructBiTNode

chardata;

structBiTNodelchild,rchild;

}BiTNode,BiTree;

BiTreeCreate(BiTreeT)

charch[20];

inti=0;

for(i=0;i<20getchar()!='

全部频道

数据结构二叉树实验报告