在二叉搜索樹中是必需的結構

我已經看過一些BST的代碼，我可以看到每個節點都是一個結構。這是必要的嗎？在二叉搜索樹中是必需的結構

2010-02-08 neuromancer

結構不是必要的。你可以使用類來代替。在C++中，類默認爲私有成員，在您首次公開或受保護的聲明之前，類定義中的所有內容都將是私有的。結構，默認情況下會員是公共的。 – Zaki 2010-02-08 05:57:02

你的意思是必要的？ – 2010-02-08 12:59:02

結構不是必需的。任何數據類型都可以使用。 BST需要指向節點的指針，並且節點需要有內容（或者它們可以是指向數據的指針）。例如，你可以有一個void指針數組：void * tree_array [200] [3];'最後一個維數用於* left，data，*和* right *指針。你有什麼反對'struct's？ – 2010-02-08 19:41:02

int flat_tree[ 1000 ][ 3 ]; 
    // for each tree node, value is stored in element [id][0] 
         // id of left_child stored in element [id][1] 
         // id of right_child stored in element [id][2]

...

我不會去任何進一步與此有關。

一般來說，struct s/class es用於任何類型的鏈接數據結構。一般來說，類型系統的任何特性都可能被忽略或忽略，你可以以非常痛苦的方式在一個數組中執行所有的操作（堆分配等）。

來源

2010-02-08 05:33:46 Potatoswatter

到目前爲止最佳答案：與此同時，它顯示兩個答案。理論上不，實際上是。 – MSalters 2010-02-08 09:45:40

第二個維度可能使這更容易，其中索引值可以是左邊的0，數據1和右邊的2。 – 2010-02-08 19:42:17

@Thomas：相對而言; v） – Potatoswatter 2010-02-08 21:32:59

不，它可能是一個班級。它不可能是原始的，因爲它需要存儲一個值並且也指向兒童。

嗯，我應該說，你也可以代表你的BST作爲一個數組，其中節點在i位置的左，右孩子都在位置2 * i + 1和2 * i + 2，分別。但是，那麼您將不得不擔心調整大小，並且您需要一個特殊的值來表示空值，並且刪除操作變得非常複雜。除了學術活動之外，我不推薦這種方法。

來源

2010-02-08 05:17:47 danben

糟糕，我沒有看到你的答案。不過，我認爲你的意思是** 3 ** * i + 2。 – Potatoswatter 2010-02-08 05:39:15

不，2是正確的。 – danben 2010-02-08 05:46:49

3似乎更好......這個混亂是一個很好的理由，爲什麼一個人應該使用結構。 – Thilo 2010-02-08 05:48:07

它不是強制性的。
但是由於一個節點包含的數據和兩個鏈接一起構成一個邏輯實體，它們通常放在一個結構中。因此，編寫將節點作爲參數或返回節點的函數變得更加容易。

來源

2010-02-08 05:24:21 codaddict

不，不嚴格地說。在FORTRAN時代，人們使用平行陣列或二維數組。

託尼霍爾的Dahl，Dijkstra和Hoare的「結構化編程」一節討論了數據結構和記錄類型。

來源

2010-02-08 05:40:43

如果您的有效載荷承認了一個最終值，那麼您可以比並行數組更簡單：您可以使用隱式樹（也就是說，根本不打算使用鏈接）。

payload_type a[tree_size];

只要僅包含有效載荷值的長平陣列，其中位置陣列中的編碼鏈接結構：

a[0]是根
a[1]是根 - >左
a[2]是root-> right
a[3]是root-> left-> left
a[4]是根 - >左>右
...

對於位置的節點i，轉到2 * i + 1的左，2 * I + 2爲右

你初始化它到所有的最終值，並開始添加東西...

來源

2010-02-10 20:06:04 dmckee

在二叉搜索樹中是必需的結構

回答

相關問題