Tree類應該包含什麼？

我的課目前正在做Binary Trees作爲我們數據結構單元的一部分。我明白，Node類的構造函數中必須有3個參數（值，左節點，右節點）。作爲要求的一部分，我們必須有一個Tree類。樹類的目的是什麼？是否用於管理整個節點集？它是否僅包含插入，刪除和搜索特定節點所需的功能？Tree類應該包含什麼？

預先感謝您。

我的節點類：

class Node { 
protected int data; 
protected leftNode; 
protected rightNode; 

Node (int data, Node leftNode, Node rightNode){ 
this.data = data; 
this.leftNode = leftNode; 
this.rightNode = rightNode; 
} 
}

來源

2012-04-09 Nyx

受保護的變量的使用是故意的。爲了減少帖子的大小，我已經刪除了getter和setter。 – Nyx 2012-04-09 22:17:09

假設是，正如你懷疑的那樣，有點缺陷。您定義的Node類型是二叉樹的完美優秀實例。

Jack提到您希望在整個節點集合周圍有Tree類型，以便提供像getRoot這樣的操作，插入，刪除等操作。這當然不是一個壞主意，但它絕不是一個要求。其中許多操作本身可能會發生在Node之上，並且您不一定必須執行所有這些操作;例如，針對和反對有一個getRoot操作有爭論。反對它的一個論據是，如果你有算法在某一點上只需要一個子樹，那麼Tree對象保留在根Node可防止你的算法不再需要的垃圾回收Node。

但更一般地，這裏需要提出的真正的問題是這樣的：其中你處理的事情是接口，哪些是實施？因爲如果要將二叉樹作爲調用者的接口展示是一回事，而如果要提供某種有限映射作爲接口，則二叉樹就是實現細節。在前一種情況下，客戶端將「知道」樹是null或帶有值和分支的Node，並且將被允許例如遞歸樹的結構;在後一種情況下，客戶端將「知道」的所有內容是您的班級支持某種形式的put,get和delete操作，但不允許依賴於它存儲爲搜索樹的事實。在後一種情況的許多變體中，您確實會使用Tree類型作爲前端來隱藏客戶端的節點。（例如，Java的內置java.util.TreeMap類是這樣做的。）

所以最短的答案是，真的，這取決於。稍長的答案取決於合同位於二叉樹實現與其用戶之間的內容;調用者允許假設哪些樹有關樹，二叉樹的哪些細節是作者預期將來可以改變的東西等。

來源

2012-04-09 22:27:00

「是用於管理整個節點集合的？」

是的。

「它是否僅包含插入，刪除和搜索特定節點所需的功能？」

基本上，是的。出於這個原因，它應該至少包含對根節點的引用。

來源

2012-04-09 22:10:29 Matthias

任何數據結構的目的都是爲了讓您保持相關值的集合並以有意義的方式操縱它們。

樹是一種特殊的數據結構。對於具有分層結構的數據來說，這是一個很好的選擇：那些具有自然親子關係的數據。對於每個父節點，二叉樹至多有兩個子節點。

值得特別提及的樹的另一個特徵是它是自相似的：樹中的每個節點本身就是一棵子樹的根。遞歸利用了這個事實。

是的，這些都是很好的方法。您可能希望看看java.util.Map接口可能有用的其他人。

來源

2012-04-09 22:10:50 duffymo

是的，它應該給出一個樹的功能接口encapsulating所有與內部結構相關的行爲和算法。

爲什麼這樣好？ 因爲您將定義一些僅僅提供一些功能並且以獨立方式工作的東西，這樣每個人都應該能夠使用您的樹類而不必關心節點，算法等等。

理想的類應該是參數，讓你有Tree<T>，你就可以有例如

T getRoot()

基本上通用的方法，你就必須項目，以便它可以讓你到

插入值
刪除值
搜索值
訪問整個樹
任何

來源

2012-04-09 22:11:00 Jack

在我看來，一個Tree類要堅持樹的根節點的引用，並作爲一個整體的樹操作的方法和屬性，如與屬於每個節點的方法相反，如getLeft(),getValue()。

例如，我會在Tree類中定義一個size屬性，並且向樹添加或移除節點的方法（它也碰巧在這個類中）將負責保持大小最新。

來源

2012-04-09 22:12:48

謝謝你的尺寸想法。 – Nyx 2012-04-09 22:15:11

Tree類應該包含什麼？

回答

相關問題