数据结构 | 二叉树 BinaryTree

数据结构 | 二叉树 BinaryTree

树 Tree

以下面的树为例子

树的基本概念

节点

  • 节点:图中 1、2、3 等都是这棵树的节点
  • 根节点:1
  • 父节点:例如 1 是 2、3、4、5、6 的父节点,2 是 21、22的父节点
  • 子节点:与父节点相反,2、3、4、5、6 是 1 的子节点,21、22 是 2 的子节点
  • 兄弟节点:同一个父节点下的子节点互为兄弟节点,例如 21 和 22 是兄弟节点
  • 空树:一棵树没有任何节点,包括没有根节点
  • 一棵树可以只有一个节点,也就是根节点

子树

  • 子树:一棵树可以有很多节点,而其中除了整体是一棵树外,其中的子节点也可以单独看成一棵树,例如 2、21、22、221、222、223 就是一颗子树
  • 左子树:左侧的子节点称为左子树,例如 21 构成 2 的左子树
  • 右子树:右侧的子节点称为右子树,例如 22(及其子节点) 构成 2 的右子树

  • 节点的度:子树的个数,即子节点的个数,就是节点的度,例如根节点 1 有 5 个子节点,所以根节点 1 的是 5。
  • 树的度:所有节点的度的最大值,例如这棵树节点度最大的是根节点,所以这棵树的度是5
  • 叶子节点:度为 0 的节点,即没有子节点的节点
  • 非叶子节点:度不为 0 的节点,即有子节点的节点

深度

  • 层数:根节点在第一层,根节点的子节点在第 2 层,以此类推(有些教科书可能从第 0 层开始计算)
  • 节点的深度:从根节点当前节点的唯一路径上的节点总数
    • 节点 2 的深度:1->2,经历2个节点,所以深度为2
    • 节点 223 的深度:1->2->22->223,经历 4 个节点,所以深度是 4
  • 节点的高度:从当前节点最远叶子节点的路径上的节点总数
    • 节点 2 的高度:2->22->221,经历 3 个节点,所以高度是 3
    • 节点 223 的高度: 223,只有一个节点,所以高度是 1
  • 树的深度:所有节点深度的最大值,例如本树深度为 4
  • 树的高度:所有节点高度的最大值,例如本树高度为 4

树的分类

  • 有序树:树中任意节点的子节点之间有顺序关系,如果两棵树所有的都一样,但是其中的子节点顺序不一样,就是两颗不同的有序树
  • 无序树:树中任意节点的子节点之间没有顺序关系,也称为自由树
  • 森林:由m(m >= 0)棵互不相交的树组成的集合

二叉树 Binary Tree

二叉树的性质

  • 二叉树中每个节点的度最大为 2,即一个节点最多有 2 棵子树
  • 二叉树中节点的左子树和右子树是有顺序的,例如所有节点的左子节点小于右子节点
  • 即使某节点只有一棵子树,也要分左右子树

二叉树的性质

  • 非空二叉树的第 $i$ 层的节点数量最多为 $2^{i-1},(i\geq1)$
  • 高度为 $h$ 的二叉树最多有 $2^h-1$ 个节点 $(h\geq1)$
  • 对于任意一棵非空二叉树,如果叶子节点的个数为 $n_0$,度为 2 的节点个数为 $n_2$,则有 $n_0=n_2+1$
    • 证明:设度为 1 的节点个数为 $n_1$,则二叉树总结点数 $n=n_0+n_1+n_2$,二叉树边数既满足 $T=n_1+2n_2$(计算节点脚下的边),也满足 $T=n-1$(计算节点头顶的边),结合三式,推出 $n_0=n_2+1$

真二叉树

  • 真二叉树即所有的节点的度要么为 0,要么为 2

真二叉树

满二叉树

  • 满二叉树即所有的节点的度要么为 0,要么为 2,且所有叶子节点都在最后一层
  • 满二叉树一定是真二叉树,真二叉树不一定是满二叉树
  • 在同样高度的二叉树中,满二叉树的叶子节点数量最多,总节点数量最多

满二叉树

  • 满二叉树的第 $i$ 层的节点数量为 $2^{i-1}$
  • 满二叉树的高度 $h$ 和 总节点数 $n$ 有如下关系
    • $n=2^h-1$
    • $h=log_2(n+1)$

完全二叉树

  • 完全二叉树的叶子节点只会出现在最后 2 层,且最后 1 层的的叶子节点都靠左对齐
  • 完全二叉树从根节点到倒数第二层是一棵满二叉树
  • 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树

完全二叉树

  • 度为 1 的节点只有左子节点
  • 度为 1 的节点要么有 1 个,要么有 0 个
  • 同样节点数量的二叉树,完全二叉树的高度最小
  • 高度为 $h$ 的完全二叉树
    • 至少有 $2^{h-1}$ 个节点
    • 至多有 $2^h-1$ 个节点(满二叉树)
  • 高度 $h$ 和 总节点数 $n$ 有如下关系
    • $2^{h-1} \leq n$
    • $n \leq 2^h-1$
    • $h-1 \leq n < h$,注意左闭右开
    • $h=floor(log_2n)+1$ ,$floor()$ 为向下取整函数,Java 中若使用强制转型,转成整型默认为向下取整
  • 对于一棵节点数为 $n$ 的完全二叉树($n>0$),如果按照从上到下,从左到右的顺序从 1 开始进行编号,则对任意第 $i$ 个节点:
    • 若 $i=1$,则该节点为根节点
    • 若 $i>1$,则它的父节点编号为 $floor(i/2)$
    • 若 $2i \leq n$,则它的左子节点编号为 $2i$
    • 若 $2i>n$,则它无左子节点(该节点为叶子节点)
    • 若 $2i+1 \leq n$,则它的右子节点编号为 $2i+1$
    • 若 $2i+1>n$,则它无右子节点(该节点不一定是叶子节点)
  • 对于一棵节点数为 $n$ 的完全二叉树($n>0$),如果按照从上到下,从左到右的顺序从 0 开始进行编号,则对任意第 $i$ 个节点:
    • 若 $i=0$,则该节点为根节点
    • 若 $i>0$,则它的父节点编号为 $floor(\frac{i-1}{2})$
    • 若 $2(i+1) \leq n$,则它的左子节点编号为 $2i+1$
    • 若 $2(i+1)>n$,则它无左子节点(该节点为叶子节点)
    • 若 $2(i+1)+1 \leq n$,则它的右子节点编号为 $2i+2$
    • 若 $2(i+1)+1>n$,则它无右子节点(该节点不一定是叶子节点)
  • 对于完全二叉树,若总节点数 $n$ 为偶数,则最后一个节点为左子节点,若总节点数 $n$ 为奇数,则最后一个节点为右子节点
  • 总节点数为 $n$ 的完全二叉树,其叶子节点数量为 $floor(\frac{n+1}{2})$

参考