实验五二叉树建立及应用
一、实验目的
1．熟悉二叉树的存贮结构及遍历方式，掌握有关算法的实现。

2．能够利用二叉树解决具体问题。

二、实验环境
⒈硬件：每个学生需配备计算机一台。

操作系统：DOS或Windows；
⒉软件：DOS或Windows操作系统+Turbo C；
三、实验要求
⒈要求采用二叉链表作为存贮结构，完成二叉树的建立、先序、中序、和后序遍历的
操作。

⒉输入数据：树中每个结点的数据类型设定为字符型。

3．设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序遍历，求该二叉树所有叶子结点总数。

四、实验内容
附：参考程序为类C语言程序，非标准C语言程序，需要进行相应的修改。

二叉链表结构如下：P134
typedef struct lnode
{char data;
struct lnode *lchild,*rchild;
}lnode,*tree;
1．建树子函数P137
status creat(tree &t)
{//按先序次序输入二叉树中结点的值，’.’字符表示空树
scanf(&ch);
if(ch=='.')
t=null;
else
{t=(tree)malloc(sizeof(lnode));
t->data=ch;
creat(t->lchild);
creat(t->rchild);}
return ok;
}
2．先序遍历子函数P136
preorder(tree t)
{
if(t!=null)
{printf(t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
3．后序遍历子函数P136
postorder(tree t)
{if(t!=null)
{postorder(t->lchild);
postorder(t->rchild);
printf(t->data);
}
}
五、思考题
1. 已知二叉树先序和中序序列，唯一地构造一棵二叉树并且验证其正确性。

2. 建立一个二叉树，并且按层次遍历操作。

六、报告要求
1．报告要求用专门的实验报告纸书写，字迹清晰，格式规范。

2．报告中应写清姓名、学号、实验日期、实验题目、实验目的、实验要求。

3．报告中应书写源程序，且源程序中要有注释。

4．报告中应包含运行结果及结果分析。

如调试通过，请注明‘通过’并写出输入的数据及运行结果；如未调试通过或结果不正确，试分析原因。

5．报告最后包含实验总结和体会。

七、对综合性实验的说明
实验五是一个综合性的实验，实验中的数据元素采用二叉链表作为存储结构。

该实验要求学生完成建树、遍历、统计叶子结点等多项要求，集成了树、二叉链表、递归等多个知识点。