C#虚拟二叉树图形化程序设计(2)
意义:数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。本次课题设计中，程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”，并且使用“一文数组”来作为其存储结构。一文数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历和删除二叉排序树中某个结点。
1.2 主要研究内容
主要通过研究二叉树的遍历，用最小面积法，界内算法和满二叉树算法结合画图的类分别用Visual Studio 2007软件来实现画出树的图形，通过对图形和方法的分析，了解每个算法实现的有点和缺点，总结哪种算法更简单，更有效率。同时，也为了帮助我们进一步的对二叉树的了解，及其意义。对于，一些新的类的学习，如绘制类的设计思想，设计接口，虚拟画布的研究以及对画点，画线，画圈的方法的学习。
2 二叉树
2.1 树
树形结构是一种典型的非线性的结构，除用于表示相邻关系外，还可以表示层次关系。
2.1.1 树的定义
树是n（n>=0）个结点（Node）的有限集。在任意一颗非空树中，有且仅有一个特定的称谓根（Root）的结点，当n》1时，其余结点分成m（m>0）个互不相交的有限集T1，T2，...,Tm，其中每个集合本身又是一棵树，并且成为根的子树。树的定义是递归的，即在树的定义中又用到了树的概念，它刻画了的固有特性，即一棵树由若干课子树构成，而子树又由更小的若干棵子树构成。
不包含任何结点的树称为空树。图1.1所示的是由9个结点组成的树，其中结点A是根节点，它有两棵子树，分别以B、C、D为根，而以B为根的子树又可以分成两棵子树，以C为根的子树又可以分成1棵子树，以D为根的子树有H、I，以I为根的子树又分成三棵子树。
2.1.2 树的表示
图1.1所示的同一棵树的4种表示方法。
(1) 树形表示法：这种方法直观、清晰、是常用的一种表示方法。
(2) 括号表示法：用多层括号来描述相关树和子树的关系，较少使用。
(3) 文氏图表示法：采用集合的包含关系来表示树和子树的关系，较少使用。
凹入表示法
（a） 树形表示法
（b） 括号表示法
（c） 文氏图表示法
（d） 凹入表示法
图1.1 图的表示法
2.1.3 树的基本用语
（1） 树的结点：数据元数的内容及指向其子树的分支统称为结点。
（2） 结点的度：在数中，结点拥有子树的个数称为结点的度。
（3） 树的度：树内各结点的度的最大值。
（4） 叶子或终端点：度为0的结点称为叶子或终端结点。
（5） 非终端结点或分支结点：度不为0的结点称为非终端结点或分支结点。除根据结点之外，分支结点也称为内部结点。
（6） 孩子、双亲：结点的子树的根称为该节点的孩子，该结点的称为孩子的双亲或父亲。
（7） 兄弟：同一个双亲的孩子称为兄弟。
（8） 祖先和子孙：结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任何一结点都称为该结点的子孙。