完整的二叉树定义 [英] Complete binary tree definitions

问题描述

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

I have some questions on binary trees:

• 维基百科指出，一棵二叉树是完备的，当一棵完全二叉树是一棵二叉树，其中每一层(可能除了最后一层)都被完全填充，并且所有节点都为尽量靠左."最后一句尽可能向左"是什么意思?

• Wikipedia states that a binary tree is complete when "A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible." What does the last "as far left as possible" passage mean?

如果(1)它是空的，或者(2)它的左右孩子高度平衡并且左树的高度是在右树高度的 1 以内，取自 如何确定是否二叉树是平衡的?，这是正确的还是 1 值存在抖动"?我在我链接的答案中读到，右树和左树的高度之间也可能存在 4 的差异因子

A well-formed binary tree is said to be "height-balanced" if (1) it is empty, or (2) its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree, taken from How to determine if binary tree is balanced?, is this correct or there's "jitter" on the 1-value? I read on the answer I linked that there could be also a difference factor of 4 between the height of the right and the left tree

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

Do the complete and height-balanced definitions just apply to binary tree or just any other tree?

推荐答案

• 按照维基百科中定义的参考，我得到了此页面.该定义取自那里但已修改:

  • Following the reference of the definition in wikipedia, I got to this page. The definition was taken from there but modified:

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

    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.

    它继续下面的注释，

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

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

    有时，定义因方便而异(对某事有用).该段落可能是一种变体，据我所知，它需要叶节点首先填充最深级别的左侧(即从左到右填充).我通常找到的定义与上面描述的完全一样，但没有那个段落.

    Sometimes, definitions vary according to convenience (be useful for something). That passage might be a variation which, as I understand, requires leaf nodes to fill first the left side of the deepest level (that is, fill from left to right). The definition that I usually found is exactly as described above but without that passage.

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

    Usually the definition taken for height-balanced tree is the one you described. In other words:

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

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

    该定义取自此处.同样，有时定义更灵活以服务于特定目的.例如，AVL 树 的定义表示

    That definition was taken from here. Again, sometimes definitions are made more flexible to serve specific purposes. For example, the definition of an AVL tree says that

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

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

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

    Still, I remember once I had to rewrite an algorithm so that the tree would be considered height-balanced if the two child subtrees of any node differed by at most 2. Note that the definition you gave is recursive, this is very common for binary trees.

    这篇关于完整的二叉树定义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！