C#虚拟二叉树图形化程序设计(3)
时间:2017-02-25 09:36 来源:毕业论文 作者:毕业论文 点击:次
（9） 层数、堂兄弟：从根结点开始定义，根为第一层，根的孩子为第二层。其余结点的层数为双亲结点的层数加1.双亲在同一层上的结点互为堂兄弟。 （10）树的深度：树的结点中的最大层数称为树的深度 （11）有序树和无序树：如果树中结点的各子树从左至右是有次序的（即不能互换），则称为树为有序树，否则为无序树 （12）森林：有限树的集合 2.2 二叉树 二叉树是一种特殊的树，它是树形结构的一个重要类型。它结构简单，存储效率高，算法也相对简单，因此在讨论一般树的存储结构及操作之前，首先研究二叉树这种抽象数据类型。 2.2.1 二叉树的定义 （1） 二叉树 其特点是每个节点至多有两棵子树（即二叉树不存在度大于2)，并且二叉树的子树有左右之分，其次序不能任意颠倒，即如果将其左右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种形态：（a）空二叉树；（b）仅有根结点的二叉树；（c）右子树为空的二叉树；（d）左子树为空的二叉树；（e）左、右子树均为非空的二叉树。 （2） 满二叉树 在一棵二叉树中，如果所有分支结点都同时具有左孩子和右孩子，并且所有叶子结点都在同一层上。这种树的特点是每层上的结点数是最大结点数。如图1.2（a）是一棵满二叉树，图1.2（b）则不是满二叉树，因为虽然所有非叶子结点都有左右孩子，但其叶子结点不在同一层上。 （3） 完全二叉树 只允许树的最后一层出现空结点，且最下层的叶子结点集中在树的左部。显然，一颗满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。若对完全二叉树每个结点自上而下、从左到右顺序编号，则序号为K的任一结点，其非空左、右子结点序号必为2K和2K+1(如图1.2（b）)。 (a) 满二叉树 (b）完全二叉树 (c) 非完全二叉树 图1.2 满二叉树和完全二叉树 2.2.2 二叉树的存储结构 二叉树的存储结构可分为两种：顺序存储结构和链式存储结构。 （1）顺序存储结构：把一个满二叉树自上而下、从左到右顺序编号，并把编号依次存放在数组内，棵得到图1.3（a）所示的结果。设满二叉树结点在数组中的索引号为i，那么有如下性质。 如果i=0，此结点为根结点，无双亲。 如果i>0，则其双亲结点为（i-1）/2。（除法为整除）结点i的左孩子为2i+1，右孩子为2i+2。 如果i>0，当i为奇数十，它是双亲结点的左孩子，它的兄弟为i+1；当i为偶数时，它是双亲结点的右孩子，它的兄弟结点为i-1。 深度为K的满二叉树需要长度为 的数组进行存储。 通过以上性质可知，使用数组存放满二叉树的各结点非常方便，可以根据一个结点的索引号很容易地推算出它的双亲、孩子、兄弟等结点的编号，从而对这些结点进行访问，这是一种存储满二叉树或完全二叉树的最简单、最省空间的做法。 为了用结点在数组中的位置反映出结点之间的逻辑关系，存储一般二叉树时，只需要将数组中空结点所对应的位置设为空即可，其效果如图1.3（b）所示。这会造成一定的空间浪费，但如果空结点的数量不是很多，这些浪费可以忽略。 (责任编辑：qin) |