2019考研计算机数据结构考点：二叉树

考研网

根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。
    　　二、二叉树
    1. 二叉树的定义及其主要特性
    1.1定义
    ①树中每个结点至多有两棵子树，且子树有序。
    ②满二叉树是一棵深度为k，结点数为2k-1的二叉树;3完全二叉树是至多在最下两层上结点的度数可以小于2，并且最下层的结点集中在该层最左的位置的二叉树。
    1.2二叉树的五种基本形态
   

   

    1.3二叉树的主要特性
    ①二叉树第i层上的结点数最多为2i-1;
    ②深度为k的二叉树至多有2k-1个结点;
    3在任意二叉树中，叶子数为n0，度为2的结点数为n2，则n0=n2+1;
    1.4满二叉树与完全二叉树
    ①满二叉树
    深度为k，且有2k-1个结点。(对满二叉树中的结点约定编号：自根起，从上到下，从左到右)
    ②完全二叉树
    仅允许最下层右侧分支不满，若按从上到下，从左到右为树中结点编号，则与满二叉树相同。
    二者关系：
    满二叉树是完全二叉树。
    完全二叉树不一定是满二叉树。