实现二叉树的基本操作及求二叉树深度和叶子数
1、实验四 二叉树的基本操作
一、实验目的：
（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；
（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想；
（3）掌握二叉树和叶子数、深度之间的关系及联系。
2、二、实验内容：
构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的叶子数和深度。
3、三、实验步骤：
(一) 需求分析
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）深度模块
4、 四、测试结果
1. 进入演示程序后的显示主界面：
请输入二叉树中的元素；
先序、中序、后序遍历和叶子数、深度分别输出结果。
2.测试结果
以扩展先序遍历序列输入，其中#代表空子树：ABC##DE#G##F###
先序遍历序列为：ABCDEGF
中序遍历序列为：CBEGDFA
后序遍历序列为：CGEFDBA
此二叉树的叶子数为：3
此二叉树的深度为：5
3.程序运行结果截图：
5、五、源代码
#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);//计算叶子节点数
}
