一、 实验目的

  1. 掌握树和二叉树逻辑结构；

  2. 掌握二叉树的顺序存储结构与二叉链表存储结构；

  3. 掌握利用C/C++编程语言实现数据结构的编程方法；

  4. 通过上机实践加强利用数据结构解决实际应用问题的能力；

二、 实验相关知识

  1. 二叉树的顺序存储；

  2. 二叉树的二叉链表存储结构；

  3. 二叉树的先、中、后和层序遍历；

  4. 使用EasyX做简单的图形处理。

三、 实验内容与要求

利用EasyX实现分别实现顺序存储结构与二叉链表存储结构的二叉树的构造，并演示二叉树先序、中序、后序、层序遍历的访问过程。

顺序存储存储结构二叉树

1. 在窗体中绘制63（为了演示效果，节点个数不能太多）个节点的完全二叉树，节点使用圆表示；

2. 利用鼠标点选二叉树的节点，选中与非选中顶点之间使用颜色进行区分；（第一次上机任务节点）

3. 通过改变节点的颜色，演示出该二叉树在先序、中序、后序和层序过程中，节点被访问的顺序；

   4. 参考效果如下：

   （1）选二叉树节点

（2）先序遍历二叉树

（3）中序遍历二叉树

（4）层序遍历二叉树

   二叉链表存储存储结构二叉树（选做）

1. 利用弹出的输入框输入二叉树的扩展先序遍历字符串，创建二叉链表；

2. 计算二叉树各节点的中序遍历次序（决定横坐标值），高度值（决定二叉树的纵坐标值）

3. 根据二叉树各节点纵横位置值，绘制二叉树

4. 通过改变节点的颜色，演示出该二叉树在先序、中序、后序和层序过程中，节点被访问的顺序；

   5. 参考效果如下：      

（1）输入二叉树的扩展先序遍历结果，并绘制二叉树

（2）后序遍历二叉树

（3）层序遍历二叉树

四、编程原理讲解

五、进一步思考

1、还有没有其它更好的办法安排节点的位置；

2、如何在遍历的过程中，在提示文字中，输出当前的遍历序列；

3、结合你所了解的二叉树的应用，思考二叉树的实际创建过程；

4、先、中、后序遍历，若不用递归，如何实现。