algorithm - 完整的二叉树定义

Question

我对二叉树有一些疑问：

• 维基百科指出，当“完整的二叉树是一棵二叉树，其中除了可能的最后一层之外，每一层都被完全填满，并且所有节点都尽可能地靠左”时，二叉树就是完整的。最后一段“尽可能向左”是什么意思？

• 如果（1）它是空的，或者（2）它的左右子树是高度平衡的并且左树的高度在 1正确的树，取自如何确定二叉树是否平衡？，这是正确的还是 1 值有“抖动”？我阅读了我链接的答案，左右树的高度之间也可能存在 4 的差异因子

• 完整和高度平衡的定义是否仅适用于二叉树或任何其他树？

Answer 1

• 根据维基百科中的定义参考，我到了 这个页面。该定义取自那里，但经过修改：

  定义：一棵二叉树，其中每一层，除了可能最深的，都被完全填满。在深度 n 处，即树的高度，所有节点都必须尽可能靠左。

  它继续下面的注释，

  一棵完整的二叉树在每个深度 k < n 以及 2n 和 2^(n+1) - 1 个节点之间都有 2k 个节点。

  有时，定义会因方便而异（对某事有用）。据我了解，该段落可能是一种变体，它需要叶节点首先填充最深层次的左侧（即从左到右填充）。我通常找到的定义与上面描述的完全一样，但没有那段。

• 通常，高度平衡树的定义是您描述的定义。换句话说：

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

  该定义取自这里。同样，有时定义会更加灵活以服务于特定目的。例如，AVL 树的定义说

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

  不过，我记得有一次我必须重写一个算法，以便如果任何节点的两个子子树最多相差 2，那么树将被认为是高度平衡的。请注意，您给出的定义是递归的，这对于二进制非常常见树木。

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

Answer 2

完整和高度平衡的定义是否仅适用于二叉树或任何其他树？

简短的回答：是的，它可以扩展到任何 n 叉树。