数据结构与算法（第一季）：二叉树

一、树形结构

• 节点最多为两个的树叫做二叉树, 节点多余两个的树叫做多叉树

image

<figcaption></figcaption>

二、生活中的树形结构

image

<figcaption></figcaption>

三、树的基本概念

• 下图是一颗多叉树

image

<figcaption></figcaption>

• 节点: 其中的1、2、3、4、5、6、21、22、31、51、52、61、221、222、223称之为节点
• 根节点: 1称之为根节点
• 父节点: 1是2、3、4、5、6的父节点, 2是21、22的父节点, 以此类推
• 子节点: 与父节点相反, 2、3、4、5、6是1的子节点, 21、22是2的子节点, 以此类推
• 兄弟节点: 同一个父节点下的子节点互为兄弟节点, 例如上图中的21和22是兄弟节点, 但是22和31虽然都在同一层, 而父节点不同, 所以不是兄弟节点

---

• 空树: 一棵树没有任何节点, 包括没有根节点
• 一棵树可以只有一个节点, 也就是根节点
• 子树: 一棵树可以有很多节点, 而其中除了整体是一颗树外, 其中的子节点也可以单独看成一棵树, 例如2、21、22、221、222、223就是一颗子树
• 左子树: 左侧的子节点称为左子树, 例如21是2的左子树
• 右子树: 右侧的子节点称为右子树, 例如22、221、222、223是2的右子树

---

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

---

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

树的深度等于树的高度

四、有序树、无序树, 深林

image

<figcaption></figcaption>

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

五、二叉树

1、二叉树的特点

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

image

<figcaption></figcaption>

注意: 二叉树是有序树

2、二叉树的性质

image

<figcaption></figcaption>

• 非空二叉树的第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, 这是因为n1的每个节点下有1个子节点, 所以边是n1, n2的每一个节点都有2个子节点所以是n2 * 2
  • 反过来看, 因为所有的节点上面都有一条边, 只有根节点上没有边
  • 所以 二叉树的边数T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
  • 即: n1 + 2 * n2 = n0 + n1 + n2 - 1 可以推出 n0 = n2 + 1

六、真二叉树

• 真二叉树: 所有节点的度要么为0, 要么为2, 即没有只有一个子节点的节点

image

<figcaption></figcaption>

• 下图不是真二叉树, 因为节点15的度是1

image

<figcaption></figcaption>

七、满二叉树

• 满二叉树: 最后一层节点的度都为0, 其他节点的度都为2

image

<figcaption></figcaption>

• 假设满二叉树的高度为h(h >= 1), 那么
  • 第i层的节点数量: 2^(i - 1)
  • 叶子节点数量: 2^h - 1
  • 总结点数量n
    • n = 2^h - 1 = 2^0 + 2^1 + 2^2 + 2^3 +...+ h^(h - 1)
    • h = log2(n + 1)

在同样高度的二叉树中, 满二叉树的叶子节点数量最多, 总结点数量最多
满二叉树一定是真二叉树, 真二叉树不一定是满二叉树

八、完全二叉树

• 完全二叉树: 对节点从上到下, 从左到右开始编号, 其所有编号都能与相同高度的满二叉树中的编号对应

image

<figcaption></figcaption>

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

九、完全二叉树的性质

image

<figcaption></figcaption>

• 度为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 <= log2(n) < h
  h = floor(log2n) + 1
  复制代码
  

floor是向下取整, 另外, ceiling是向上取整

• 一个有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, 它无右子节点

• 一个有n个节点的完整二叉树(n > 0), 从上到下, 从左到右对节点从0开始编号, 对任意第i个节点

  • 如果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 = 2n0 + n1 - 1
  • 完全二叉树的n1要么为0, 要么为1
    • n1 = 1时, n = 2n0, n必然是偶数, n0 = n / 2
    • n1 = 0时, n = 2n0 - 1, n必然为奇数, n0 = (n + 1) / 2
  • 叶子节点个数n0 = floor((n + 1) / 2) = ceiling(n / 2)
  • 非叶子节点个数n1 + n2 = floor(n / 2) = ceiling((n - 1) / 2)
  • 因此叶子节点个数为384