二叉树

二叉树意味着节点最多可以有两个子节点。这里，“二叉”这个名字本身就表示“二”；因此，每个节点可以有 0、1 或 2 个子节点。

让我们通过一个例子来理解二叉树。

上面的树是一个二叉树，因为每个节点最多包含两个子节点。上面这棵树的逻辑表示如下所示

在上面的树中，节点 1 包含两个指针，即指向左节点和右节点的左指针和右指针。节点 2 包含两个节点（左节点和右节点）；因此，它有两个指针（左指针和右指针）。节点 3、5 和 6 是叶节点，所以所有这些节点在左侧和右侧都包含 NULL 指针。

二叉树的性质

• 在每个 i 级别，最大节点数为 2ⁱ。
• 树的高度定义为从根节点到叶节点的最长路径。上面显示的树的高度等于 3。因此，高度为 3 的最大节点数等于 (1+2+4+8) = 15。通常，高度为 h 时可能的最大节点数为 (2⁰ + 2¹ + 2²+…2^h) = 2^h+1 -1。
• 高度为 h 时可能的最少节点数等于 h+1。
• 如果节点数最少，则树的高度将是最大值。反之，如果节点数最多，则树的高度将是最小值。

如果二叉树中有“n”个节点。

最小高度可以计算为

众所周知，

n = 2^h+1 -1

n+1 = 2^h+1

两边取对数，

log₂(n+1) = log2(2^h+1)

log₂(n+1) = h+1

h = log₂(n+1) - 1

最大高度可以计算为

众所周知，

n = h+1

h = n-1

二叉树的类型

二叉树有四种类型

• 满二叉树/真二叉树/严格二叉树
• 完全二叉树
• 完美二叉树
• 退化二叉树
• 平衡二叉树

1. 满二叉树/真二叉树/严格二叉树

满二叉树也称为严格二叉树。只有当每个节点必须包含 0 或 2 个子节点时，该树才能被视为满二叉树。满二叉树也可以定义为除叶节点外，每个节点都必须包含 2 个子节点的树。

让我们看一个满二叉树的简单示例。

在上面的树中，我们可以观察到每个节点要么包含零个子节点，要么包含两个子节点；因此，它是一个满二叉树。

满二叉树的属性

• 叶节点数等于内部节点数加 1。在上面的例子中，内部节点数为 5；因此，叶节点数为 6。
• 最大节点数与二叉树中的节点数相同，即 2^h+1 -1。
• 满二叉树中的最小节点数为 2*h-1。
• 满二叉树的最小高度为 log₂(n+1) - 1。
• 满二叉树的最大高度可以计算为

n = 2*h - 1

n+1 = 2*h

h = n+1/2

完全二叉树

完全二叉树是一种除最后一层外所有节点都完全填充的树。在最后一层中，所有节点必须尽可能靠左。在完全二叉树中，节点应从左侧添加。

让我们创建一个完全二叉树。

上面的树是一个完全二叉树，因为所有节点都完全填充，并且最后一层的所有节点都首先添加到左侧。

完全二叉树的属性

• 完全二叉树中的最大节点数为 2^h+1 - 1。
• 完全二叉树中的最小节点数为 2^h。
• 完全二叉树的最小高度为 log₂(n+1) - 1。
• 完全二叉树的最大高度是

完美二叉树

如果所有内部节点都有 2 个子节点，并且所有叶节点都在同一级别，则该树是完美二叉树。

让我们看一个完美二叉树的简单示例。

下面的树不是一个完美的二叉树，因为所有叶节点不在同一级别。

注意：所有完美二叉树都是完全二叉树和满二叉树，但反之则不成立，即所有完全二叉树和满二叉树都是完美二叉树。

退化二叉树

退化二叉树是一种所有内部节点只有一个子节点的树。

让我们通过示例来理解退化二叉树。

上面的树是一个退化二叉树，因为所有节点只有一个子节点。它也称为右倾斜树，因为所有节点都只有右子节点。

上面的树也是一个退化二叉树，因为所有节点都只有一个子节点。它也称为左倾斜树，因为所有节点都只有左子节点。

平衡二叉树

平衡二叉树是一种左右子树的高度差最多为 1 的树。例如，AVL 和 红黑树 都是平衡二叉树。

让我们通过示例来理解平衡二叉树。

上面的树是一个平衡二叉树，因为左右子树的高度差为零。

上面的树不是一个平衡二叉树，因为左右子树的高度差大于 1。

二叉树实现

二叉树是借助指针实现的。树中的第一个节点由根指针表示。树中的每个节点由三部分组成，即数据、左指针和右指针。要创建二叉树，我们首先需要创建节点。我们将创建用户定义的节点，如下所示

在上述结构中，data 是值，left pointer 包含左节点的地址，right pointer 包含右节点的地址。

C 语言中的二叉树程序

上面的代码递归调用 create() 函数，并在每次递归调用时创建新节点。当所有节点都创建完毕后，它就形成了一个二叉树结构。访问节点的过程称为树遍历。有三种遍历类型用于访问节点

• 中序遍历
• 前序遍历
• 后序遍历