完整的二叉树定义

• 在参考了Wikipedia中的定义之后，我进入了 此页面。定义是从那里获取的，但已修改：

定义： 二叉树，其中所有级别（可能最深的级别）都被完全填充。在树的高度n处，所有节点都必须尽可能地向左移。

虽然下面有一个注释，

一个完整的二叉树在每个深度k <n处都有2k个节点，并且在2n和2 ^（n + 1）之间-总共有1个节点。

有时，定义会根据便利性而有所不同（对某些有用）。据我了解，该段落可能是一个变体，需要叶节点首先填充最深层的左侧（即，从左到右填充）。我通常发现的定义与上面的描述完全相同，但没有该段落。

• 通常，对高度平衡树的定义就是您所描述的。换一种说法：

当且仅当对于每个节点，其两个子树的高度相差最多1时，树才是平衡的。

这个定义是从这里得到的。同样，有时可以使定义变得更灵活以服务于特定目的。例如，AVL树的定义说明

在AVL树中，任何节点的两个子树的高度最多相差一个

仍然，我记得曾经不得不重写算法，以便如果任何节点的两个子子树最多相差2，则该树将被认为是高度平衡的。请注意，您给出的定义是递归的，这对于二进制很常见树木。

• 在子代数可变的树中，您将不能说它是完整的（任何父代都可以拥有想要的子代数）。尽管如此，它仍然可以应用于 n元树 （具有固定数量的

  n

  子级）。