左平衡二叉树

Question

我正在读一本关于数据结构的书，书中说左平衡二叉树是一种叶子只占据最后一层最左边位置的树。

这对我来说似乎有点含糊。这是否意味着叶子只在根的左侧，并分布在整个层级中，或者叶子只存在于整个树的左侧。到底是什么构成了左平衡？

我不确定我的猜测是否涵盖了任何答案，所以如果有人能提供帮助，我将非常感激:-)。

Answer 1

您可以将左平衡二叉树视为平衡二叉树，其中每个节点的左子树在右子树之前填充。在更多的非正式术语中，这是一种树，其中最底层的节点都在整个树的左侧。

以这棵树为例：

​

​

这棵树是平衡的，但不是左平衡的。然而，如果节点67被移除，则树将是左平衡的。

Answer 2

在我看来，左平衡二叉树的定义与完全二叉树的定义是相同的。

Answer 3

我真的不知道答案，但根据书中的描述，我听起来是这样的……

首先，让我们这样想。树中的每个“行”都有一个数字，从零开始并向上计数。具有最高编号的行被认为是最后一级。

请记住，叶节点是没有任何子节点的节点。因此，树满足最后一层中的每个叶节点必须在左侧的条件，如下所示：

          50
       /     \
     /         \
    35         70
   /  \       /  \
 10    34    57  90
 /     /        /
9     7        78

如果我们添加一个"98“作为90的右子树，或者添加一个"59”作为57的右子树，那么这棵树将不再是左平衡的。

编辑：在阅读了Brandon E Taylor's answer之后，你绝对不应该选择这个。在看了一遍又一遍描述之后，他的描述不仅更有意义，而且更符合描述。