左平衡二叉树

Question

左平衡二叉树

binary-treetree-balancing

4

我正在阅读一本有关数据结构的书，其中提到左平衡二叉树是指叶子节点只占据最后一层中最左边的位置。

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

我不确定我的猜测是否包含任何答案，所以如果有人能帮助，将不胜感激 :-).

- rubixibuc

4个回答

3

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

- Simone

2

我不太清楚答案，但根据书中的描述，我觉得可能是这样的...

首先，我们可以这样想。树中的每一行都有一个编号，从零开始逐个计数。具有最高编号的行被认为是最后一级。

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

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

如果我们在90的右子节点添加一个“98”，或者在57的右子节点添加一个“59”，那么这棵树就不再是左平衡的了。

编辑：阅读完Brandon E Taylor的答案后，您绝对不应该选择此答案。经过仔细查看和重新阅读描述，他的答案不仅更有意义，而且更符合描述。

- user265312

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

- A. Khaled

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Brandon E Taylor · Accepted Answer

您可以将左平衡二叉树视为平衡二叉树，其中每个节点的左子树在右子树之前被填充。更不正式地说，这是一棵树，其中最底层的节点都在整个树的左侧。以这棵树为例：

此树是平衡的，但不是左平衡的。但是，如果删除节点67，则树将变为左平衡。