特点

  • 每个节点最多有两个子树 就是度为 0 - 2
  • 二叉树是有序的
  • 左边的树叫左子树，右边的树叫右子树，即使只有一个子树，也要分出他是左子树还是右子树

    为什么说二叉树和树是两种数据结构呢？就是因为二叉树是有序的这个原因

特殊类型

  • 斜树

由一个根节点加上两棵分别称为左子树和右子树组成

  • 满二叉树

叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点

  • 完全二叉树

第i个编号和满二叉树的第i个编号位置一样 则就是完全二叉树
叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大

性质

  • 二叉树的第i层上最多有 2i−12i−1个结点
  • 在深度为k的二叉树中，最多有2k−12k−1个结点
  • 在一科二叉树中，如果叶子结点的个数是n0n0,度为2的结点个数为n2n2 则 n0n0 = n2n2+1 这个上面那两个明白这个就ok
  • 具有n个结点的完全二叉树的深度为⌊log2n⌋⌊log2n⌋ 这个也很好理解吗 就是对第2条性质的取对数呗
  • 对于一个完全二叉树开始从1编号，
    • 对于i>1的元素 则它的双亲结点是 ⌊i/2⌋⌊i/2⌋
    • 如果2*i <= n 那么结点i的左孩子为 2i 否则的话没有左孩子
    • 如果2*i +1 <= n 那么结点i的右孩子为 2i +1 否则的话没有右孩子