严格二叉树

树是一种常见的非线性数据结构。与数组、栈、队列和链表等线性数据结构不同，树展现出一种分层结构。树的排序信息无关紧要。树由两个指针和节点组成。这两个指针代表父节点的左孩子和右孩子。让我们彻底理解树中使用的术语。

• 树中没有父节点的最高节点被视为树的根。每棵树都有一个根节点。
• 父节点：一个节点的父节点是该节点在节点树中的前一个节点。
• 子节点：一个节点的直接后继节点被称为该节点的子节点。
• 兄弟节点：同一父节点的子节点互为兄弟节点。
• 边：边作为父节点和子节点之间的连接节点。
• 叶子：没有子节点的节点被称为叶子节点。它是树的最后一个节点。一棵树可以有多个叶子节点。
• 一个节点的子树是把该特定节点视为根节点的树。
• 深度：一个节点的深度是它与根节点之间的距离。
• 高度：一个节点的高度是它与子树中最深节点之间的距离。
• 任何节点的最大高度被称为树的高度。这与根节点的高度相同。
• 层：在树中，层是与特定节点对应的父节点的数量。
• 节点度：一个节点的度由它拥有的子节点数量决定。
• 二叉树有 (N+1) 个 NULL 节点，其中 N 是树中节点的总数。

树是一种常见的非线性数据结构。与数组、栈、队列和链表等线性数据结构不同，树展现出一种分层结构。树的排序信息无关紧要。树由两个指针和节点组成。这两个指针代表父节点的左孩子和右孩子。让我们彻底理解树中使用的术语。

• 树中没有父节点的最高节点被视为树的根。每棵树都有一个根节点。
• 父节点：一个节点的父节点是该节点在节点树中的前一个节点。
• 子节点：一个节点的直接后继节点被称为该节点的子节点。
• 兄弟节点：同一父节点的子节点互为兄弟节点。
• 边：边作为父节点和子节点之间的连接节点。
• 叶子：没有子节点的节点被称为叶子节点。它是树的最后一个节点。一棵树可以有多个叶子节点。
• 一个节点的子树是把该特定节点视为根节点的树。
• 深度：一个节点的深度是它与根节点之间的距离。
• 高度：一个节点的高度是它与子树中最深节点之间的距离。
• 任何节点的最大高度被称为树的高度。这与根节点的高度相同。
• 层：在树中，层是与特定节点对应的父节点的数量。
• 节点度：一个节点的度由它拥有的子节点数量决定。
• 二叉树有 (N+1) 个 NULL 节点，其中 N 是树中节点的总数。

二叉树表示

树中的每个节点都包含以下信息：

• 指向左子节点的指针
• 指向右子节点的指针

在 C 语言中，我们可以使用结构体来表示树节点。我们可以利用其他语言的面向对象特性中的类。下面是一个包含整数数据的树节点的示例。

什么是严格二叉树？

严格二叉树的另一个名称是完全二叉树。只有当每个节点要么有 0 个子节点，要么有 2 个子节点时，这棵树才被认为是严格二叉树。“严格二叉树”也可以指除叶节点外，所有节点都必须有两个子节点的树。

让我们以一个简单的例子来检查一下完全二叉树。

如上图所示，这棵树是一棵严格二叉树，因为每个节点要么有零个子节点，要么有两个子节点。

严格二叉树的特性

• 叶节点的数量比内部节点的数量多一个。鉴于上面的例子中有 5 个内部节点，因此也有 6 个叶节点。
• 最大节点数为 2h+1 -1，这对应于二叉树中的节点数量。
• 整个二叉树必须至少有 2*h-1 个节点。
• 整个二叉树的最小高度为 log2(n+1) - 1。
• 整个二叉树的最大高度可以使用以下公式计算：
  n = 2*h - 1
  n+1 = 2*h
  h = (n+1)/2

完全二叉树

由于二叉树被称为完全二叉树，当所有节点都从左侧添加时，新层级不会添加节点，直到前一个层级完全填满。所有节点都必须在最后一层尽可能靠左。

• 一个或两个内部节点可能会产生子节点。但是，由于节点必须从左侧开始插入，因此只有一个内部节点可能只有一个子节点，而其余节点都将有 0 个或 2 个子节点。
• 叶节点位于最底层。
• 高度为 h 的完全二叉树最多可以有 2(h+1) - 1 个节点，最少可以有 2 个节点。