左平衡二叉樹

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的回答後，你絕對不應該選擇這一個。在仔細觀察並再次閱讀描述之後，他的作品不僅更有意義，而且更符合描述。