algorithm - 完整的二叉树定义

Question

我有一些关于二叉树的问题:

• 维基百科指出二叉树是完整的，当“完整的二叉树是一棵二叉树，其中除了可能的最后一层外，每个级别都被完全填充，并且所有节点都是尽可能靠左。”最后一段“as far left as possible”是什么意思？

• 如果 (1) 它为空，或 (2) 它的左右子节点高度平衡且左树的高度为在右侧树的高度的 1 以内，取自 How to determine if binary tree is balanced? ，这是正确的还是 1 值有“抖动”？我在链接的答案中读到，左右树的高度之间也可能存在 4 的差异因子

• 完全和高度平衡的定义只适用于二叉树还是任何其他树？

Answer 1

• 根据维基百科中的定义引用，我得到了 this page .定义取自那里但被修改:

  Definition: A binary tree in which every level, except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

  它继续下面的注释，

  A complete binary tree has 2k nodes at every depth k < n and between 2n and 2^(n+1) - 1 nodes altogether.

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

• 通常高度平衡树的定义就是你描述。换句话说:

  A tree is balanced if and only if for every node the heights of its two subtrees differ by at most 1.

  该定义取自 here .同样，有时定义会更加灵活以服务于特定目的。例如， AVL tree 的定义说是

  In an AVL tree, the heights of the two child subtrees of any node differ by at most one

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

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