二叉树汇总

知识点

二叉树的种类

满二叉树

满二叉树（Full Binary Tree），也称为完全二叉树，是一种特殊类型的二叉树。在满二叉树中，除了叶子节点外，每个节点都有两个子节点，并且所有叶子节点都处于相同的深度或层级上。

满二叉树的定义特点如下：

  1. 每个节点要么没有子节点，要么有两个子节点。
  2. 所有叶子节点都在同一层级上，也就是说从根节点到任意叶子节点的路径长度是相同的。

图示：

1
2
3
4
5
     A
   /   \
  B     C
 / \   / \
D   E F   G

在上述示例中，每个节点都有两个子节点，且所有叶子节点 D、E、F 和 G 都在相同的深度上。

满二叉树具有一些特殊的性质，例如：

  1. 对于具有 n 层的满二叉树，总节点数为 2^n - 1。
  2. 第 i 层的节点数为 2^(i-1)。
  3. 最后一层的节点数等于前面所有层的节点数之和加 1。

满二叉树经常用于研究和实现二叉树相关的算法和数据结构。它在某些场景下可以提供更高效的操作和存储结构。

完全二叉树

完全二叉树（Complete Binary Tree）是一种特殊类型的二叉树，它除了最后一层的叶子节点可能不满外，其它层的节点都必须填满。

完全二叉树的定义特点如下：

  1. 所有的叶子节点都集中在最后一层或倒数第二层。
  2. 如果存在某个节点的右子节点为空，则该节点右侧的所有节点都必须为空。
  3. 完全二叉树从左到右依次填充节点。

下面是一个例子展示了一个完全二叉树的结构：

1
2
3
4
5
6
7
       A
     /   \
    B     C
   / \   /
  D   E F
 / \
G   H

在上述示例中，所有的叶子节点 G、H、F 都集中在最后一层，倒数第二层只有一个节点 C 的左子节点为空。按照上述定义，这是一个完全二叉树。

和满二叉树相比，完全二叉树的特点是它不强调每个节点都有两个子节点，只要满足前面提到的三个条件就可以。

完全二叉树具有一些重要的性质，例如：

  1. 对于具有 n 个节点的完全二叉树，节点编号从 1 到 n，对于任意节点 i，有以下性质：
    • 如果 i > 1，则其父节点的编号为 i/2。
    • 如果 2*i ≤ n，则其左子节点的编号为 2*i。
    • 如果 2*i+1 ≤ n，则其右子节点的编号为 2*i+1。

完全二叉树在一些算法和数据结构中经常被使用，例如堆（Heap）数据结构就是基于完全二叉树实现的。由于其特殊的性质，在某些场景下可以提供更高效的操作和存储结构。

二叉树的递归遍历