完整的二叉树定义

Question

我对二叉树有一些疑问：

• Wikipedia指出，当“完整的二叉树是其中所有级别（可能除了最后一个级别）均已完全填充且所有节点都位于最左侧”的二叉树时，该二叉树即已 完成 。最后的“越远越好”的段落是什么意思？

• 如果（1）它是空的，或者（2）它的左右子级是平衡的，并且左树的高度在以下高度的1之内，则格式正确的二叉树被称为“高度平衡”。正确的树，取自如何确定二叉树是否平衡？，这是正确的还是1值上有“抖动”？我在链接的答案上读到，左右树的高度之间可能还有4的差异因子

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

Answer 1

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

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

虽然下面有一个注释，

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

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

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

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

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

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

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

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