实验：二叉树的递归遍历算法
实验：二叉树的递归遍历算法
一、实验目的
领会二叉树的各种遍历过程以及遍历算法设计。
二、实验环境
VC++6.0
三、实验准备
（1）复习课件中理论知识
（2）练习课堂所讲的例子
四、实验内容
编写一个程序BiTree.cpp，用二叉链表的存储二叉树，用按先序建立二叉树，并实现二叉树的各种递归基本运算，并在此基础上设计一个main方法，完成如下功能：
（1）二叉树类型的定义；
（2）按先序建立二叉树；
（3）先序递归遍历；
（4）中序递归遍历；
（5）后序递归遍历；
（6）统计结点个数；
（7）统计叶子结点个数；
（8）求树的深度；
（9）main函数中调用这些函数进行测试。
五、实验步骤
1.根据实验要求，定义相关变量。
2.定义字符型二叉树结构体，并按照先序的方式构造建立二叉树的函数。
3.构造先序，中序，后序，三种遍历方式。
4.构造统计叶子节点个数，求树的深度函数。
5.构造主函数，进行定义二叉树，和相应的解决问题的函数，并输出结果。
六、实验总结
1.在构造函数时，分清楚所对应函数的功能，确保每一个分块的作用和内容有其较好的健壮性。
2.编写代码时，分清实现代码和伪码的区别。
3.遇到问题时，多进行调试。
附：源代码
#include<bits/stdc++.h>
using namespace std;
typedef char TElemTypd;
typedef struct BiTNode{//定义二叉树
TElemTypd data;
struct BiTNode *lchild,*rchild ;
}BiTNode,*BiTree;
char ch;
int sum=0;
int a1=0,a2=0,ans=0;
int CreateBiTree(BiTree &T)//先序构建二叉树
{
cin>>ch;
if(ch=='#')
T=NULL;
else{
if(!(T=(BiTNode * )malloc(sizeof(BiTNode))))exit(-2);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return 1;
}
void xianxu(BiTree T){//先序
if(T){
cout<<T->data;//根
xianxu(T->lchild);//左
xianxu(T->rchild);//右
}
}
void zhongxu(BiTree T){//中序
if(T){
zhongxu(T->lchild);//左
cout<<T->data;//根
zhongxu(T->rchild);//右
}
}
void houxu(BiTree T){//后序
if(T){
houxu(T->lchild);//左
houxu(T->rchild);//右
cout<<T->data;//根
}
}
int jiedian(BiTree &T){//统计节点个数
if(T){
sum++;
jiedian(T->lchild);//左
jiedian(T->rchild);//右
}
return sum;
}
int shendu(BiTree &T){//求树的深度
if(T){
a1=shendu(T->lchild);//左
a2=shendu(T->rchild);//右
ans=1+max(a1,a2);
}
return ans;
}
int main()
{
BiTree T;
CreateBiTree(T);
xianxu(T); cout<<endl;
zhongxu(T);cout<<endl;
houxu(T);cout<<endl;
cout<<"节点个数为："<<jiedian(T)<<endl;
cout<<"树的深度为："<<shendu(T)<<endl;
return 0;
}