從零開始實現樹

Question

我想通過從頭開始實現一棵樹來了解樹。 在這種情況下，我想用C＃Java或C++來完成。 （不使用內置的方法）

所以每個節點將存儲字符和將有最大每個節點26個的節點。

我將使用什麼數據結構來包含指向每個節點的指針？

基本上我試圖從零開始實施基數樹。

感謝，

Answer 1

你描述的不是很一個基數樹......在基數樹，你可以在一個節點的多個字符，並且對孩子節點的數量沒有上限。

你所描述的聲音由字母更多的限制是什麼？每個節點可以是AZ，並且可以跟另一個字母，AZ等的區別是你選擇持有您的下一個數據結構的關鍵 - 節點指針。

在你描述的樹，用可能是指針的簡單數組的最簡單的結構......所有你需要做的是字符（如「A」）轉換爲字符的ASCII值（「65」），並減去起始偏移量（65）以確定你想要哪個'下一個節點'。佔用更多的空間，但插入和遍歷速度非常快。

在真正的基數樹，你可以有3，4，78，或0子節點，和你的「下一個節點」列表將有排序，插入和刪除的開銷。慢得多。

我不能說Java，但如果我在C＃中實現自定義基數樹，我會使用其中一個內置的.NET集合。編寫你自己的排序列表並不能真正幫助你學習樹的概念，而.NET集合的內置優化很難打敗。然後，你的代碼很簡單：查找你的下一個節點;如果存在，就抓住它並去;如果沒有，則將其添加到下一個節點集合中。

您使用收集取決於你正在通過樹實現什麼......每一個類型的樹包括插入時間，查詢時間等你的選擇取決於什麼是最重要的應用程序之間進行權衡，而不是樹。

有意義嗎？

Answer 2

我會用什麼數據結構包含指向每一個節點？

一個節點。每個節點應該引用（最多）樹中的26個其他節點。在Node內，你可以將它們存儲在一個數組，LinkedList，ArrayList中，或者你可以想象的任何其他集合中。

Answer 3

這並不重要。您可以使用鏈接列表，數組（但這將具有固定大小），或者使用您的語言的標準庫中的List類型。

使用列表/陣列將意味着做一些指數簿記遍歷樹，所以它可能是最容易使用的只是不停地引用父的孩子們。

Answer 4

這是我最近發現的一個不錯的樹型API - 雖然我需要圖表，但很容易看到它是如何設置的，以便爲它所持有的數據分開數據結構，因此您可以使用樹型結構相當於Iterator在樹中導航，等等。

https://jsfcompounds.dev.java.net/treeutils/site/apidocs/com/truchsess/util/package-summary.html

Answer 5

如果你實際上更感興趣的速度比空間，如果每個節點代表只有一個字母（由最高的26暗示的），那麼我只用26個時隙，每個的簡單數組引用一個「節點」（節點是包含你的數組的對象）。

的好處約一個固定大小的數組是你的樣子起來會更快。如果你正在尋找了一個已經保證在較低的套管字母字符「C」，外觀起來會是那麼容易，因爲：

nextNode=nodes[c-'a']; 

字符串的遞歸查詢將是微不足道的。

Answer 6

看看這個西麥朝聖者博客中，「Code Camp Puzzle Reviewed」。其中一種解決方案在C＃中使用Radix，您可以下載該解決方案。

Answer 7

感謝您的快速回復。

是snogfish說是正確的。 基本上，它的一個有26個節點（A-Z）+一個bool的樹是Terminator。

每個節點都有這些值，並且它們相互關聯。

我還沒有深入地學習過指針，所以今天我試着從頭開始使用C＃中不安全的代碼來實現這一點，這是徒勞的。

因此，如果有人能夠提供我使用內部樹類在C＃中開始的代碼，我將不勝感激。一旦我可以開始，我可以將算法移植到其他語言，並將其更改爲使用指針。

非常感謝， 邁克爾