數據結構：類似於樹的圖 - 但不是樹

Question

我已經在C中實現了一個基於一系列鏈表的數據結構，它似乎與樹相似 - 但不足以被引用因爲在理論上它允許循環的存在。這裏有一個節點的基本輪廓：

• 有一個單一的，可識別的根沒有父節點或兄弟;
• 每個節點都包含一個指向它的「父親」的指針，它的最近的「兄弟」和他的第一個「孩子」;
• 有沒有孩子和兄弟的「外」節點。

如何命名這樣的數據結構？它不能是一棵樹，因爲即使指針被明確地標記和使用不同，像父親 - >孩子 - >兄弟 - >父親這樣的週期也可能存在。我的問題是：像「父親」，「孩子」和「兄弟」這樣的術語可以用在圖表的上下文中，還是僅用於樹木？經過相當多的研究，我仍然無法澄清這個問題。

在此先感謝！

Answer 1

我想說你仍然可以稱它爲一棵樹，因爲基礎是一個樹型數據結構。我的聲明有優先權：「Patricia Tries」被稱爲樹，即使它們的葉節點可能指向樹（創建週期）。我相信還有其他的例子。

聽起來好像你有的附加鏈接基本上只是爲了方便，可以隱式確定（而不是明確存儲）。通過顯式地存儲它們，可以在樹操作（插入，刪除等）上施加額外的不變量，但不會影響基礎組織，這是一棵樹。

正是因爲您單獨命名和處理這些附加鏈接，它們可以被認爲是樹上的「疊加層」。

最後，如果它適用於您，它並不重要，您稱之爲什麼類別。讀一本像Sedgewick的「C語言算法」這樣的書，你會意識到這裏有大量的數據結構，發明自己的東西沒有錯！

還有一點：樹是圖的一個特例，所以將它作爲圖（或者使用圖算法）也沒有什麼不對。