構建二叉樹圖

Question

這是一個Binary Tree圖。我無法理解該圖是如何創建的。您的頂部有5個，但您如何確定接下來的數字和順序是什麼？有人能一步步地走過我嗎？

Answer 1

Ofcourse，

嗯，你說這是二叉樹。因此，這是算法： 當插入新號碼時，如果號碼較小，如果它更大，則它會左移 ，它會向右移動。您應該檢查這個小程序 產生二叉樹的理解它是如何工作的

link to applet

Answer 2

數字的具體排列不是規範的（即存在其他有效的排列方式）。唯一的要求是每個節點的左側子樹只包含較小的節點，而右側的子樹只包含較大的節點。

您對特定安排的方式取決於用於填充它的算法以及插入值的順序。這在「平衡樹」部分的文章中有部分解釋。插入時，您需要保持樹木平衡。多久重新平衡一下，以及如何重新平衡是數百萬頁教科書，研究論文和代碼行的主題。

總之，你的問題的答案是「這取決於」。

對於幼稚的實現，它不一定會產生平衡的樹，每個插入操作只是簡單地走樹，如果數目小於當前訪問的節點，則向左移動;如果變大則忽略相等的值需要確保不發生或決定處理它們的政策。當你到達一個死衚衕時（即一個空的左指針或右指針），在那裏插入一個插入值的新節點。

側欄：值得注意的是，由於其簡單性，在很少的情況下，naïve算法可以滿足您的需求。您可以簡單地通過在插入之前隨機移動輸入數據來避免不平衡樹。然而，在大多數情況下，你最好甚至不使用二叉樹。散列表幾乎總是可取的。

Answer 3

這聽起來像你是專門搞不清楚該鏈接的圖。該圖似乎有錯誤。

正如其他人所說，有多種有效的安排，但對排序二叉樹的要求是每個節點的左子樹只包含較小的元素，而右子樹只包含較大的元素。

在你的問題中提供的鏈接圖中，自6> 5以來違反了。元素6屬於5的右側子樹，它似乎是作者的一個簡單錯誤。