如何表示一棵樹，其中每個孩子可能在多個父母下

Question

我正在尋找代表一組結構化數據的最佳方法。

我設計一個產品選擇器。它會要求用戶提出一些問題以縮小產品範圍。

即

1問題：「什麼是產品集團」

答：組別1

在組別1，可用商品類別（任選其一）：
組別
產品組別
類別4

答：分類四

在類別4的組別，可用的類型分別是：
的Type3
成的Type5

答：成的Type5

對於成的Type5，在分類四，Group1中可用的產品Chacteristics是...等

所以每一個新的問題表明不僅基於以前的答案，但在列表中的所有之前的答案。 （即，如果Category4在Group2中，則類別4中可用的某些類型將不同）。它就像一棵樹，每個孩子都可能在不同的父母身邊。

可能有多達10級這樣的水平。

什麼是最有效的結構來存儲這個層次？

Answer 1

沒有問題的任何額外的知識和不同的分佈，這裏是你應該做的：

每個節點有存儲在其位的n維數組，其中n是它的級別（組是級別0）。然後，當你到達關卡i時，你將查看該關卡中的所有節點，並且每個節點查看是否適合當前歷史記錄的位打開或關閉。 （節點之間沒有指針或節點，節點只是我使用的一個方便的名稱）。

在每個級別的陣列的尺寸將是以前的水平的總大小，例如在類型級別（級別2）中，您可以使用維度（＃Groups）*（＃類別）的二維數組。

示例：
要知道的Type5是否不應該出現在類別4，組1，你會去其陣列中的單元[1] [4]，並且如果它是在（1），那麼它應該出現，否則（0）它不應該。如果您使用的是允許指針算術的語言（如c/C++），您可以通過維持需要去的偏移量來稍微優化矩陣訪問，因爲它總是以相同的方式啓動：[1]，[ 1] [4]，[1] [4] [5]，...但是，當一切已經正常工作時，這應該晚得多。

如果以後你瞭解你的問題的詳細信息，如大多數這些連接的或不存在，那麼你能想到的，而不是常規的那些有關使用稀疏矩陣，例如，。