[数据结构]二叉树的建立及应用


一. 实验目的:

1. 熟练掌握二叉树的二叉链表存储结构
2. 掌握二叉树的非线性和递归性特点
3. 熟练掌握二叉树的递归遍历操作的实现方法
4. 加深对二叉树结构和性质的理解,逐步培养解决实际问题的编程能力

二. 实验内容

1. 按先序序列输入字符序列,建立二叉链表。如ABC??DE?G??F???(?表示空格)
2. 中序遍历二叉树:递归算法。
3. 后序遍历二叉树:递归算法。
4. 求二叉树的高度、深度。
5. 求二叉树的叶子个数。
6. 应用训练: 建立表达树,并计算表达式2^(1+3)的值。
7. 提示:若求表达式4+5的值,则输入其表达树的先序字符序列:+4□□5□□

三. 实验指导

1. 首先将二叉树的链式存储结构定义放在一个头文件:如取名为BinTreeDef.h。
2. 将二叉树的基本操作算法也集中放在一个文件之中,如取名为BinTreeAlgo.h。包含关于二叉树的链式结构操作的一些基本算法,如:InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTraverse、InOrderTraverse 等。
3. 将函数的测试和主函数组合成一个文件,如取名为 BinTreeUse.cpp。

发表评论