菜单
　　

       （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）所示。这会造成一定的空间浪费，但如果空结点的数量不是很多，这些浪费可以忽略。
  1. 上一篇：《协议分析与测试》课程考试系统设计与实现
  2. 下一篇：C#公司销售薪资系统设计+需求分析+ER图

  1. 云虚拟环境下资源分配优化算法的研究

  2. 桌面云中虚拟机集中入域的研究和实现

  3. OpenGL虚拟人三维模型控制平台实现

  4. VRML虚拟数字校园的设计与实现

  5. 基于虚拟仿真体验式实践教学体系的构建

  6. WPF虚拟仿真学习平台的设计与开发

  7. 基于python的虚拟仪器技术研究及实现

  8. 电站锅炉暖风器设计任务书

  9. 当代大学生慈善意识研究+文献综述

  10. java+mysql车辆管理系统的设计+源代码

  11. 河岸冲刷和泥沙淤积的监测国内外研究现状

  12. 大众媒体对公共政策制定的影响

  13. 十二层带中心支撑钢结构...

  14. 中考体育项目与体育教学合理结合的研究

  15. 杂拟谷盗体内共生菌沃尔...

  16. 乳业同业并购式全产业链...

  17. 酸性水汽提装置总汽提塔设计+CAD图纸

　　

About

751论文网手机版...

主页：http://www.751com.cn

关闭返回