是否爲二叉樹？

所以，我看到了幾個例子，如是否爲二叉樹？

http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/

他們返回1，或者真正是一個樹爲空。擴展問題 - 假設我必須找到TreeSmall是TreeBig的子樹，並且我的TreeSmall是null，那麼返回值checkSubtree(smallTree)是否應該爲true或false？ A true表示TreeSmall是tree，其值爲null。這對我沒有意義。

來源

2013-09-21 JavaDeveloper

這取決於您的實施。你可以決定'null'是一棵樹，或者你可以決定一棵樹需要什麼東西。只要你保持一致，這一切都會奏效。 – Teepeemm

有一個用於空樹的公共靜態最終EMPTY_TREE通常是一個好主意。通過這種方式，您可以避免所有那些會遺漏代碼的空檢查，並在您忘記它們時繞過NPE。 –

在純粹的計算機科學中，null是一個有效的二叉樹。它被稱爲空的二叉樹。就像一個空集仍然是一個有效的集合。此外，只有一個根節點且沒有子節點的二叉樹也是有效的（但不是空的）。有關更多信息，請參閱this Stack Overflow answer。

在實際實現中，有兩種方法可以解決這個問題。

假設一個有效的二叉樹必須至少有一個節點，並且不允許空樹。每個節點不必有孩子。此樹上的所有遞歸方法都不會降爲null級別。相反，當他們看到節點的左側孩子或右側孩子爲空時，他們停止。只要您不將null傳遞給任何期望樹的地方，此實現就會工作。
假設null是一個有效的二叉樹（形式上，只是空樹）。在這個實現中，首先檢查指針是否爲null，然後再對其進行任何操作（例如檢查左/右兒童等）。此實現適用於指向樹的任何指針。您可以自由地將空指針傳遞給期望樹的方法。

雙方都有效。第二個實施具有靈活性的優點。您可以將null傳遞給期望樹的任何內容，並且不會引發異常。第一種實現的優點是不浪費時間降低到「子節點」爲空，並且您不必在每個在節點上運行的函數/方法的開始處使用空檢查。您只需要爲孩子進行空檢查。

來源

2013-09-21 21:31:07 Shashank

這取決於應用程序，並且是一個定義問題。

編輯：

例如維基百科「定義」一個BST如下：

在計算機科學中，二進制搜索樹（BST），有時也被稱爲有序或排序二叉樹，是具有以下屬性的基於節點的二叉樹數據結構：

節點的左子樹只包含鍵小於節點鍵的節點。

節點的右側子樹只包含密鑰大於節點密鑰的節點。

左右子樹也必須都是二叉搜索樹。

必須有沒有重複的節點

讓我們測試那些null：

左子樹不存在，所以沒有節點違反這條規則 - >檢查
類似於第一個 - >檢查
如果所有這些測試都通過了，那麼也會通過，因爲兩個子樹都是空的 - >檢查
當然也有不重複 - >檢查

因此，通過這個定義null是一個有效的BST。你也可以通過要求「必須有一個根節點」來解決這個問題。這不會影響BST的任何實際屬性，但可能會在明確的應用程序中。

來源

2013-09-21 21:12:44 sotix

Ex falso sequitur quodlibet - 既然「空」根本就沒有，它可以被解釋爲任何東西。這確實是一個設計問題。在這種情況下，有些人可能聲稱checkSubTree（）應該拋出類似IllegalArgumentException的東西。另一種方法是引入表示空樹的特殊對象或實例（參見NullObjectPattern）。這樣的空對象將是所有帳戶的樹，例如， EmptyTree instanceof Tree，而null instanceof Tree將永遠是錯誤的。

來源

2013-09-21 21:31:29 rec

是否爲二叉樹？

回答

相關問題