我正在读一本关于数据结构的书，它说左平衡二叉树是一棵树，其中叶子只占据最后一层的最左边的位置。
这对我来说似乎有点模糊。这是否意味着叶子仅在根的左侧并且分布在整个级别，或者叶子仅存在于整个树的左侧。究竟什么构成左平衡？
我不确定我的猜测是否涵盖了任何答案，所以如果有人可以提供帮助，将不胜感激:-)。
问问题
4217 次
4 回答
6
您可以将左平衡二叉树视为平衡二叉树，其中每个节点的左子树在右子树之前填充。用更非正式的术语来说，这是一棵树，其中最底层的节点都在整个树的左侧。
以这棵树为例：
这棵树是平衡的，但不是左平衡的。然而，如果节点 67 被移除，那么这棵树将是左平衡的。
于 2011-09-01T19:51:22.967 回答
3
在我看来，左平衡二叉树的定义与完全二叉树的定义相同。
于 2011-09-01T19:52:23.550 回答
2
我真的不知道答案，但根据书中的描述，我听起来像这样......
对于初学者，让我们这样想。树中的每一“行”都有一个数字，从零开始向上计数。编号最高的行被认为是最后一层。
请记住，叶节点是没有任何子节点的节点。所以这棵树满足最后一层的每个叶子节点都必须在左边的条件，像这样：
50
/ \
/ \
35 70
/ \ / \
10 34 57 90
/ / /
9 7 78
如果我们添加一个“98”作为 90 的右孩子或一个“59”作为 57 的右孩子，那么这棵树将不再是左平衡的。
编辑：阅读Brandon E Taylor 的回答后，你绝对不应该选择这个。再看一遍，又读了一遍描述，他不仅说得通了，而且更符合描述了。
于 2011-09-01T19:57:04.237 回答
1
除了Brandon E Taylor 的回答之外，左平衡二叉树是一种二叉树，当它以数组形式表示时，表示树节点的元素之间不应存在任何间隙。
例如，对于大小为 6 的树，这里有一些可能的数组表示，具有以下标准
1- let _ denote an empty slot in the array
2- let i be the index of a slot in an array (i is 1-based)
2- for any parent at index i the left child is at index (2*i) and the right child is at index (2*i)+1
1 2 3 4 _ _ <- left balanced
6 3 2 4 1 <- left balanced
4 2 1 _ 6 <- not left balanced
为了进一步详细说明，让我们代表user265312的答案：
50 35 70 10 34 57 90 9 _ 7 _ _ _ 78 _ <- not left balanced
同时Brandon的回答（在删除节点 67 之后）不违反左平衡规则：
50 17 72 12 23 54 76 9 14 19 _ _ _ _ _ <- left balanced
于 2019-05-10T12:26:58.470 回答