左平衡二叉树

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的回答后，你绝对不应该选择这一个。在仔细观察并再次阅读描述之后，他的作品不仅更有意义，而且更符合描述。