完全二叉樹的定義

Question

我對二叉樹的一些問題：

• 維基百科指出，二叉樹是完成當「完全二叉樹是二叉樹中，每一個級別，除了可能的最後，完全填滿，所有節點儘可能地離開。「最後的「儘可能留下」段落是什麼意思？

• 一個格式良好的二叉樹被稱爲「高度平衡」，如果（1）它是空的，或（2）它的左右子節點是高度平衡的，並且左樹的高度在右邊樹的高度爲1，取自How to determine if binary tree is balanced?，這是正確的還是1值有「抖動」？我讀到了答案，我認爲在右側和左側樹的高度之間也可能有4的差異因子

• 完整和高度平衡定義是否適用於二叉樹或任何其他樹？

Answer 1

• 繼維基百科的定義的參考，我到 this page。該定義是從那裏拍攝，但修改：

  定義：二叉樹中，每一個級別，除了可能最深的，是完全充滿。在深度n處，樹的高度，所有節點必須儘可能地離開。

  它繼續與下面雖然註釋，

  一個完整的二叉樹具有在每一個深度爲k < n和之間2n與2K節點2 ^（N + 1） - 1個節點完全。

  有時候，定義會根據方便程度而有所不同（對某些事物有用）。這段話可能是一個變化，據我所知，要求葉節點首先填充最深層次的左側（即從左到右填充）。我通常發現的定義與上面所描述的完全相同，但沒有通過。

• 通常，高度平衡樹的定義是你所描述的那個。換句話說：

  當且僅當對每個節點的兩個子樹的高度至多1

  區別在於定義是從here拍攝的樹是平衡的。同樣，有時候定義會更靈活，以達到特定的目的。例如，AVL tree的定義說，

  在AVL樹，任何節點 的兩個子子樹的高度最多由一個

  還是不同的，我記得有一次我有重寫一個算法，以便如果任何 節點的兩個子樹最多相差2，那麼樹 將被視爲高度平衡。請注意，您給出的定義是遞歸的，這對二叉樹非常常見。

• 在樹的兒童數量可變的情況下，你不能說它是完整的（任何家長都可以擁有你想要的孩子數量）。不過，它可以適用於n-ary樹（與固定數量的n兒童）。

Answer 2

做完整和高度平衡的定義僅僅適用於二進制 樹或只是任何其他的樹？

簡答：是的，它可以擴展到任何n元樹。