二叉树基础

1. 二叉树

1.1 概念

二叉树(Binary tree)是树形结构的一个重要类型,二叉树特点是每个节点最多只能有两棵子树,且有左右之分,称为左子树和右子树。

1.2 二叉树的基本形态

  • 空二叉树
  • 只有一个根节点的二叉树
  • 只有左子树
  • 只有右子树
  • 完全二叉树

1.3 二叉树的性质

  • 二叉树的第i层上至多有2i-1个节点
  • 深度为h的二叉树中至多含有2h-1个节点
  • 若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1
  • 具有n个节点的满二叉树深为log2n+1

1.3 二叉树的特殊类型

  • 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。

    ![preview](D:/program x64/Hexo/source/image/view)

  • 完全二叉树:完全二叉树是由满二叉树而引出来的,对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

    ![/img/bVcTHUc](D:/program x64/Hexo/source/image/bVcTHUc)

堆总是一个完全二叉树

2. 堆

2.1 概念

任意节点的值总是大于(小于)子节点的值

  • 如果任意节点的值总是大于子节点的值,称为:最大堆、大顶堆
  • 如果任意节点的值总是小于子节点的值,称为:最小堆、小顶堆

2.2 堆的性质

  • 下标为i的节点的父节点下标:(i-1)/2【整数除法】
  • 下标为i的节点的左孩子下标:i*2+1
  • 下标为i的节点的右孩子下标:i*2+2