描述树结构的节点上的最小信息

Question

我的问题是:描述节点之间的关系以在树上强制执行结构所需的最小信息量是多少？如何简明扼要地表达这些规则？

我有一个树数据结构(在C++中，如果对任何人都重要的话)。A std：：向父母返回指针的向量。)。节点可以是专用的。当一个节点是专门化的，它可能是“有效的”，因为它有一定的父母或可能只有当它有特定的子节点。系统不具备100%的所有节点类型的知识(也就是说，用户使用新节点构建插件，而这些节点可能有新的规则)。虽然一切都很好，但它依赖于我们对如何建造一棵树的先验知识。(新用户可以在逻辑上没有任何意义的地方放置节点，这是我们想要检测和预防的。)

我们希望能够“执行”一个有效的结构。允许将一些节点附加到任何地方，而其他节点则有特殊的位置等等。当然，所有节点都继承了一个公共基类，并有其所有子节点的列表和指向其父节点的指针。很简单。

我的第一次尝试只是允许节点列出它们的有效父类型。然而，这会导致一些节点非常混乱，并将自己依附于父母，而这根本就没有意义。为了解决这个问题，我添加了一个节点可以接受的子类型列表。这很好地实现了树的配对，但也使得管理更加困难，而且，考虑到某些节点可能具有的多个继承级别，很难在允许其他节点的同时屏蔽某些类型的子节点。

在这一点上，我认为问这个问题是值得的。树不是我的specialty...and，当然有人知道一种定义良好的方法来构造这样的树，并以灵活和有意义的方式执行关系。想法还是想法？

其他信息，如果它是重要的:结构往往非常宽(数百到数千个节点)和浅(2-10层深)。有一个根，有1到5棵子树.这是真正的工作开始的地方。我很乐意使用STL，Boost，或其他任何可能在这里有所帮助的库。我不想改造这棵树。如何表示节点之间的关系以构造树是问题的重点。

Answer 1

我对您的问题的理解是，您希望在节点之间建立一个或多个关系。

最简单的方法是对每种关系都有一个链接。如果您想要在关系中沿着两个方向(向前和向后)遍历，您将需要为每个关系有两个链接。

如果您想拥有动态关系，我建议每个节点都有一个map，std::map<relation, link>。第一项，键，将是枚举关系标识符(或std::string)。该值将是指向该节点的链接。这样你就可以说出这样的话：

next_node = node_links[NEXT_BY_ALPHABETICAL];

我建议你画出你的对象之间的关系。还绘制树和节点之间的关系。

另一种选择是有独立的树，每种关系都有一棵树。这些树中的每个节点都包含指向数据项的指针。因此，只有一个数据项存在；但是可能有一个或多个索引(关系)指针。

最后，您可能需要考虑使用数据库，可能是关系数据库。