实验四二叉树的建立和遍历
学院专业班
学号姓名
一．实习目的
1.掌握二叉链表的存储结构；
2.掌握二叉链表的建立；
3.掌握二叉树的先序遍历、中序遍历、后序遍历的递归算法；
4. 掌握二叉树遍历算法的应用；
二．实习内容
1.按先序序列建立二叉树的二叉链表（算法6.4）（空树用#表示）
2.对生成的二叉树分别进行先序遍历、中序遍历、后序遍历，输出结果。
3．统计二叉树中结点个数；
4. 求二叉树的高度；
三．实验步骤
1.定义二叉链表的存储结构
# "stdio.h"
# ".h"
char ;
{
data;
, ; // 左右孩子指针
},*;
2.编写函数二叉树的遍历算法java，按先序序列建立二叉树的二叉链表;
测试的字符序列为abdg###e##c#f##;
程序代码为：
void ( &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)二叉树的遍历算法java-二叉树的建立和遍历实验报告，构造二叉链表表示的二叉树T。以#表示空树
ch;
scanf("%c",&ch);
if(ch=='#') // 空
T=NULL;
else
{
T=( )(()); // 生成根结点
if(!T)
exit(-1);
T->data=ch;
(T->);// 递归构造左子树
(T->);// 构造右子树
}
}
2. 编写二叉树的先序遍历、中序遍历、后序遍历的递归算法
int ( T)
{ // 初始条件：二叉树T存在，先序递归遍历T；
if(T==NULL) 1;
if(T!=NULL) // T不空
{("%5c",T->data); // 访问根结点(T->);// 先序遍历左子树
(T->);// 先序遍历右子树
}
}
int ( T)
{ // 初始条件：二叉树T存在二叉树的遍历算法java，中序递归遍历T；
if(T==NULL) 1;
if(T!=NULL) // T不空
{
(T->);// 中序遍历左子树
("%5c",T->data); // 访问根结点(T->);// 中序遍历右子树
}
}
int ( T)
{ // 初始条件：二叉树T存在，
// 操作结果：后序递归遍历T；
if(T==NULL) 1;
if(T!=NULL) // T不空
{
(T->);// 后序遍历左子树
(T->);// 后序遍历右子树
("%5c",T->data); // 访问根结点
}
}
3. 编写函数统计二叉树中结点个数；（遍历算法）
int ( T)
{ int n=0,k=0,m=0;
if(T==NULL)
0;
else
{ if(T->!=NULL ) k=(T->); // 后序遍历左子树,得到左子树结点个数
if(T->!=NULL ) m=(T->); // 再后序遍历右子树
n=m+k+1 ;
}
n;
}
4. 编写函数求二叉树的高度；
int ( T)
{ int lh,rh,th;
if(T==NULL) 0;
lh= (T->); // 递归求T的左子树的高度lh
rh= (T->); //递归求T的右子树的高度rh
if(lh>rh) th=lh+1;
else th=rh+1;
th;
}
4. 编写main 函数，调用函数，输出结构
void main()
{
int i,k,h ;
T;
("请按先序输入二叉树(如:ab###表示a为根结点,b为左子树的二叉树)n");
(T);
("先序遍历的结果为：n");
i=(T); ("n");
("中序遍历的结果为：n");
i=(T);("n");
("后序遍历的结果为：n");
i=(T);("n");
k=(T);
("结点个数为%dn",k);
h= (T);
("输出树的高度为%dn", h);
}
4.运行结果（截图）
图1.二叉树的建立和遍历
四实验小结
通过本次实习，我掌握了先序、中序、后序遍历中的递归算法的使用，从而实现了对二叉树的先序、中序、后序遍历。