数据结构实验报告(二叉树的基本操作)

班级：计科1202班

姓名：***

学号：**********

时间：2013.11.16实验内容

设计一个与二叉树基本操作相关的演示程序，要求实现以下功能：

（1）创建二叉树。按照用户需要的二叉树，构建二叉树。

（2）将创建的二叉树以树状形式输出。

（3）分别以先序，中序，后序三种遍历方式访问二叉树。

（4）输出二叉树的叶子结点以及叶子结点的个数。

（5）输出二叉树的高度。

实验目的

（1）掌握二叉树的存储实现。

（2）掌握二叉树的遍历思想。

（3）掌握二叉树常见算法的程序实现。

概要设计

主界面设计

为了实现二叉树相关功能的管理，需要设计一个含有多个菜单项的主控菜单子程序以链接系统的各个子功能，方便用户使用本程序。

存储结构设计

本程序采用二叉链式存储结构（BiTNode）存储二叉树的结点信息。二叉树的链表中的结点至少包括三个域：数据域（data），左孩子指针域（LChild），右孩子指针域（RChild）。

系统功能设计

本程序除了完成二叉树的创建功能外，还设置了8个子功能菜单。由于这8个子功能都是建立在二叉树的构造上，所以二叉树的创建由主函数main（）完成。8个子功能设计描述如下：

（1）树状输出二叉树。树状输出二叉树由函数TranslevelPrint（）实现。当用户选择该功能时，系统以树状的形式输出用户所创建的二叉树。

（2）先序遍历二叉树。由函数PreOrder（）实现。该功能按照先序遍历访问二叉树的方法输出先序序列。

（3）中序遍历二叉树。由函数InOrder（）实现。该功能按照中序遍历访问二叉树的方法输出中序序列。

（4）后序遍历二叉树。由函数PostOrder（）实现。该功能按照后序遍历访问二叉树的方法输出后序序列。

（5）输出叶子结点。该功能采用先序遍历二叉树的方法，依次输出叶子结点。由函数PreOrderLeaf（）实现。

（6）输出叶子结点个数。该功能计算并输出二叉树叶子结点的个数，由LeafCount（）函数实现。采用递归算法计算二叉树叶子结点的个数，算法思想是：当二叉树为空时，叶子总结点数为0；当二叉树只有一个结点时，叶子结点个数为1；否则，叶子结点总数为左右子树结点之和。

（7）输出二叉树的深度。该功能即输出二叉树结点所在层次的最大值。由函数PostOrderDepth（）实现。

（8）退出。由函数exit（）实现。

详细设计

详细设计参见附录源代码。

测试结果

（1）首先输入二叉树结点：

（2）出现主界面：

（3）分别选择不同的功能即可得到不同的结果：

树状输出：

先序，中序，后序遍历分别显示如下：

（4）选择功能5，6，7即可出现叶子结点，叶子结点的个数，和该二叉树的深度

最后，选择功能8，退出该系统。

实验心得

（1）总结本次实习的收获

通过本次实验，加强了对二叉树的认识与相关操作的算法、编程实现；通过实验，我熟悉二叉树树的基本操作，掌握二叉树的实现以及实际应用。加深了对二叉树的理解，逐步培养解决实际问题的编程能力以及进一步了解了二叉树图转化为括号表示法。递归的使用，要注意，初始时的状态以及如何使用递归，注意普遍性，思考时从普通的开始。通过这次上机操作，让我明白书本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新

（2）本系统的不足之处

系统的健壮行不够强

代码不够优化。

（3）遇到的困难

对于一些不会编译的程序，通过百度会了求叶子结点数，然后仿照求叶子结点数的方法，自己编出了求度为2的结点数的算法，学会了很多东西，对编程更加有兴趣了。

附录

源代码：

#include

#include

#include

#include

#define MAXLEN 100

#define NLAYER 4

typedef struct BiTNode

{

/* data */

char data;

struct BiTNode *LChild,*RChild;

}BiTNode,*BiTree;

BiTree T;

//建立二叉树

void CreatBiTree(BiTree *bt)//按照先序序列建造二叉树

{

char ch;

scanf("%c

if(ch=='#') *bt=NULL;

else

{

*bt=(BiTree)malloc(sizeof(BiTNode));//生成一个新的结点(*bt)->data=ch;

CreatBiTree(&((*bt)->LChild));//生成左子树

CreatBiTree(&((*bt)->RChild));

}

}

//树形打印二叉树

void TranslevelPrint(BiTree bt)

{

//本算法实现二叉树的按层打印

struct node

{

/* data */

BiTree vec[MAXLEN];//存放树结点

int layer[MAXLEN];//结点所在的层

int locate[MAXLEN];//打印结点的位置

int front,rear;

}q; //定义队列q

int i,j=1,k=0,nlocate;

q.front=0; q.rear=0;//初始化队列q队头，队尾printf(" ");

q.vec[q.rear]=bt;//将二叉树根节点入队列

q.layer[q.rear]=1;

q.locate[q.rear]=20;

q.rear=q.rear+1;

while(q.front{

bt=q.vec[q.front];

i=q.layer[q.front];

nlocate=q.locate[q.front];

if (j{

printf("\\n\\n");

j=j+1; k=0;

while(k{

printf(" ");

k++;

}

}

while(k<(nlocate-1))

{

printf(" ");

k++;

}

printf("%c

q.front=q.front+1;

if(bt->LChild !=NULL)//存在左子树，将左子树根节点入队列

{

q.vec[q.rear]=bt->LChild;

q.layer[q.rear]=i+1;

q.locate[q.rear]=(int)(nlocate-pow(2,NLAYER-i-1));

q.rear=q.rear+1;

}

if(bt->RChild !=NULL)

{

q.vec[q.rear]=bt->RChild;

q.layer[q.rear]=i+1;

q.locate[q.rear]=(int)(nlocate+pow(2,NLAYER-i-1));

q.rear=q.rear+1;

}

}

}

//输出结点

void Visit(char ch)

{

printf("%c

}

//先序遍历二叉树

void PreOrder(BiTree root)

{

//先序遍历二叉树，root为指向二叉树跟结点的指针

if(root!=NULL)

{

Visit(root->data);//访问根结点

PreOrder(root->LChild);//先序遍历左子树

PreOrder(root->RChild);//先序遍历右子树

}

}

//中序遍历二叉树

void InOrder(BiTree root)

{

if(root!=NULL)

{

InOrder(root->LChild);

Visit(root->data);

InOrder(root->RChild);

}

}

void PostOrder(BiTree root)

{

if(root!=NULL)

{

PostOrder(root->LChild);

PostOrder(root->RChild);

Visit(root->data);

}

}

//输出叶子结点

void PreOrderLeaf(BiTree root)

{

//先序遍历二叉树并输出叶子结点

if(root!=NULL)

{

if(root->LChild==NULL&& root->RChild==NULL)

printf("%c

PreOrderLeaf(root->LChild);

PreOrderLeaf(root->RChild);

}

}

//输出叶子结点的个数

int LeafCount(BiTree root)

{

int LeafNum;

if(root==NULL) LeafNum=0;

else if((root->LChild==NULL)&&(root->RChild==NULL)) LeafNum=1;

else LeafNum=LeafCount(root->LChild)+LeafCount(root->RChild);

//叶子数为左右子树数目之和

return LeafNum;

}

//输出二叉树的深度

int PostTreeDepth(BiTree root)

{

//后序遍历求二叉树的深度递归算法

int hl,hr,max;

if(root!=NULL)

{

hl=PostTreeDepth(root->LChild);//求左子·树·的深度

hr=PostTreeDepth(root->RChild);//求右子树的深度

max=hl>hr?hl:hr;//得到左右子树深度较大者

return(max+1);

}

return 0;

}

//主要工作函数，操作区用户界面

void mainwork()

{

int yourchoice;

printf("\\n-------------------------欢迎使用二叉树基本操作程序-------------------\\n");

printf("\\n 菜单选择\\n\\n");

printf(" 1.树状输出二叉树 2.先序遍历二叉树\\n");

printf(" 3.中序遍历二叉树 4.后序遍历二叉树\\n");

printf(" 5.输出叶子结点 6.输出叶子结点的个数\\n");

printf(" 7.输出二叉树的深度8.退出\\n");

printf("\\n----------------------------------------------------------------------\\n");

printf("请输入您的选择：");

scanf("%d

while(!(yourchoice==1||yourchoice==2||yourchoice==3||yourchoice==4

||yourchoice==5||yourchoice==6||yourchoice==7||yourchoice==8)) {

printf("输入选择不明确，请重新输入：\\n");

scanf("%d

}

while(1)

{

switch(yourchoice)

{

case 1:printf("树的形状为：\\n"); TranslevelPrint(T);getch();break;

case 2:printf("先序遍历序列：\\n"); PreOrder(T);getch(); break;

case 3:printf("中序遍历序列：\\n"); InOrder(T); getch();break;

case 4:printf("后序遍历序列：\\n"); PostOrder(T); getch();break;

case 5:printf("叶子结点为：\\n"); PreOrderLeaf(T); getch();break;

case 6:printf("叶子结点的个数为:%d

case 7:printf("二叉树的深度为：%d

case 8:system("cls");exit(0);break;

}

printf("\\n-------------------------欢迎使用二叉树基本操作程序-------------------\\n");

printf("\\n 菜单选择\\n\\n");

printf(" 1.树状输出二叉树 2.先序遍历二叉树\\n");

printf(" 3.中序遍历二叉树 4.后序遍历二叉树\\n");

printf(" 5.输出叶子结点 6.输出叶子结点的个数\\n");

printf(" 7.输出二叉树的深度8.退出\\n");

printf("\\n----------------------------------------------------------------------\\n");

printf("请输入您的选择：");

scanf("%d

}

}

//主函数

int main()

{

printf("首先请输入二叉树的结点序列：\\n");

CreatBiTree(&T);

printf("请按菜单提示操作：\\n");

mainwork();

return 0;

}