实验四 二叉树的基本操作
一、实验目的：
（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；
（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想；
（3）掌握二叉树和叶子数、深度之间的关系及联系。
二、实验内容：
构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的叶子数和深度。
三、实验步骤：
(一) 需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。
2．程序的执行命令为：
1）构造结点类型，然后创建二叉树。
2）根据提示，从键盘输入各个结点。
3）通过选择一种方式（先序、中序或者后序）遍历。
4）输出结果，结束。
(二)概要设计
1.二叉树的二叉链表结点存储类型定义
typedef struct Node {
DataType data;
struct Node *LChild;
struct Node *RChild;
}BitNode,*BitTree;
2.建立如下图所示二叉树：
3.本程序包含六个模块
1) 主程序模块
2)先序遍历模块
3)中序遍历模块
4)后序遍历模块
5）叶子数模块
6）深度模块
四、测试结果
1. 进入演示程序后的显示主界面：
请输入二叉树中的元素；
先序、中序、后序遍历和叶子数、深度分别输出结果。
2.测试结果
以扩展先序遍历序列输入，其中#代表空子树：ABC##DE#G##F###
先序遍历序列为：ABCDEGF
中序遍历序列为：CBEGDFA
后序遍历序列为：CGEFDBA
此二叉树的叶子数为：3
此二叉树的深度为：5
3.程序运行结果截图：
五、源代码
#include
#include
//节点声明，数据域、左孩子指针、右孩子指针
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉树
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}
//先序遍历
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//中序遍历
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
//求二叉树的深度
int Depth(BiTree T)
{
int dep=0,depl,depr;
if(!T) dep=0;
else
{
depl=Depth(T->lchild);
depr=Depth(T->rchild);
dep=1+(depl>depr?depl:depr);
}
return dep;
}
//计算叶子节点数
int leef(BiTree T){
if(!T)
return 0;
else
if(T->lchild ==NULL&&T->rchild ==NULL)
return 1;
else
return leef(T->lchild) +leef(T->rchild );
}
//主函数
void main(){
BiTree T;
printf("请按先序输入序列（其中的“#”表示空）\n\n");
T = CreateBiTree();//建立二叉树
printf("\n先序遍历结果为：");
PreOrderTraverse(T);//先序遍历输出
printf("\n\n中序遍历结果为：");
InOrderTraverse(T);//中序遍历输出
printf("\n\n后序遍历结果为：");
PostOrderTraverse(T);//后序遍历输出
printf("\n\n二叉树深度为：%d\n",Depth(T));
Depth(T);//计算二叉树深
printf("\n叶子节点数为：%d\n\n",leef(T));
leef(T);//计算叶子节点数
}
浙公网安备 33021202002483