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

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]，...但是，当一切已经正常工作时，这应该晚得多。

如果以后你了解你的问题的详细信息，如大多数这些连接的或不存在，那么你能想到的，而不是常规的那些有关使用稀疏矩阵，例如，。