数据结构与算法学习之二叉树

树介绍

在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。

它是由 n（n>0）个有限节点组成一个具有层次关系的集合。它具有以下的特点：

  • 每个节点都只有有限个子节点或无子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树；
  • 树里面没有环路(cycle)

树的分类

  • 无序树：树中任意节点的子节点之间没有顺序关系，称为无序树，也称为自由树。
  • 有序树：树中任意节点的子节点之间有顺序关系，为有序树：
    • 二叉树
    • 霍夫曼树
    • B树

一些术语概念

  • 结点：树上包含的一个数据元素；
  • 根节点：树的开端的节点；
  • 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
  • 子节点：一个节点含有的子树的根节点称为该节点的子节点；
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点；
  • 节点的度：一个节点含有的子树的个数；
  • 树的度：一棵树中，所有节点中度最大的称为树的度；
  • 叶节点或终端节点：度 为零的节点；
  • 非终端节点或分支节点：度不为零的节点；
  • 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
  • 深度：对于任意节点n，其深度为从根到n的唯一路径的长度，根的深度为0；
  • 高度：对于任意节点n，其高度为从n到一叶子节点的最长路径长，所有叶子节点的高度为0；
  • 树的深度：所有节点深度中的最大值；
  • 树的高度：所有节点高度中的最大值；
  • 一棵树可以没有任何阶段，则成为空树；
  • 一棵树也可以只有一个节点，即根节点；

左右子树只在二叉树中有意义，因为二叉树非左即右：

  • 左子树：以当前节点看，它的左子节点那一分支的子树，该子树以当前节点左子节点为根；
  • 右子树：以当前节点看，它的右子节点那一分支的子树，该子树以当前节点右子节点为根；

二叉树

二元树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构；

  • 每个节点的度最大为 2 （最多拥有两颗子树）；
  • 左子树和右子树是有顺序的，即是某节点只有一个子树也要区分左右子树；

二叉树的性质

  • 非空二叉树的第 i 层，最多有 2^i-1^ 个节点 (i ≥ 1)；

  • 在高度为 h 的二叉树上最多有 2^h^ - 1 个节点 (h ≥ 1)；

  • 对于任何一棵非空二叉树，如果叶子节点个数为n0，度为 2 的节点个数为n2，则有：n0 = n2 + 1；

    设度为 1 的节点个数为 n1，那么二叉树的节点总数 n = n0 + n1 + n2，

    叉树的边数 T= n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1

真二叉树

真二叉树的所有节点的度要么为 0，要么为 2；

满二叉树

满二叉树的所有节点的度要么为 0，要么为 2，且所有叶子节点都在同一层；

  • 在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多

  • 满二叉树一定是真二叉树，真二叉树不一定是满二叉树；

假设满二叉树的高度为 h (h ≥ 1)，则有

  • 第 i 层的节点数量为 2^i-1^
  • 叶子节点数量为 2^h-1^
  • 总节点数量 n = 2^h^ - 1 = 2^0^ + 2^1^ + 2^2^ + … + 2^h-1^

完全二叉树

完全二叉树的叶子节点只会出现在最后 2 层，且最后一层的叶子节点都靠左对齐；

也就是说，除最后一层外的其馀层都是满的，最后一层要么是满的，要么在右边缺少连续若干节点；

  • 完全二叉树从根节点到倒数第二层是一棵满二叉树；
  • 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；

完全二叉树的性质

  • 度为 1 的节点只有左子树；
  • 度为 1 的节点要么是 1 个，要么是 0 个；
  • 同样节点数量的二叉树，完全二叉树的高度最小；

假设完全二叉树的高度为 h ( h > 1 )，那么：

  • 至少有 2^h-1^ 个节点( 2^0^ + 2^1^ + 2^2^ + … + 2^h-2^ + 1 )

  • 最多有 2^h^ - 1 个节点(2^0^ + 2^1^ + 2^2^ + … + 2^h-1^，满二叉树)

  • 总节点数量为 n，

    • 2^h-1^ < n < 2^h^
    • h - 1 < log2n < h
    • h = floor(log2n) + 1

一棵有 n 个节点的完全二叉树 (n>0)，从上到下、从左到右对节点从 1 开始进行编号，对任意第 i 个节点：

  • 如果 i = 1，它是根节点；
  • 如果 i > 1，它的父节点编号为 floor(i/2)；
  • 如果 2i ≤ n，它的左子节点编号为 2i；
  • 如果 2i > n，它无左子节点；
  • 如果 2i + 1 ≤ n，它的右子节点编号为 2i + 1；
  • 如果 2i + 1 > n，它无右子节点；

若从 0 开始编号：

  • 如果 i = 0，它是根节点；
  • 如果 i > 0，它的父节点编号为 floor((i - 1)/2)；
  • 如果 2i + 1 ≤ n - 1，它的左子节点编号为 2i + 1；
  • 如果 2i + 1 > n - 1，它无左子节点；
  • 如果 2i + 2 ≤ n - 1，它的右子节点编号为 2i + 2；
  • 如果 2i + 2 > n - 1，它无右子节点；

测试题

如果一棵完全二叉树有768个节点，求叶子节点的个数

假设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2

总结点个数n = n0 + n1 + n2，而且n0 = n2 +1

n = 2 * n0 + n1 - 1

完全二叉树的 n1 要么为 0，要么为1

  • n1为1时， n = 2* n0， n 必然是偶数；叶子节点个数n0= n/2，非叶子节点个数 n1 +n2 = n/2
  • n1为0时， n=2 * n0 - 1， n 必然是奇数；叶子节点个数n0 = (n + 1)/2，非叶子节点个数 n1 + n2 = (n - 1) /2