algorithm - 是否可以设计一棵节点有无限多个子节点的树？

Question

如何设计一棵有很多(无限数量)分支的树？

我们应该使用哪种数据结构来存储子节点？

Answer 1

您实际上不能存储无限多的子项，因为内存无法容纳。但是，您可以无限制地存储许多 child - 也就是说，您可以创建树，其中每个节点可以有任意数量的 child ，没有固定的上限。

有几种标准方法可以做到这一点。您可以让每个树节点存储其所有子节点的列表(可能作为动态数组或链接列表)，这通常通过尝试来完成。例如，在 C++ 中，您可能有这样的东西:

struct Node {
   /* ... Data for the node goes here ... */
   std::vector<Node*> children;
};

或者，您可以使用 left-child/right-sibling representation , 将多路树表示为二叉树。这通常用于优先级队列，如二项式堆。例如:

struct Node {
    /* ... data for the node ... */
    Node* firstChild;
    Node* nextSibling;
};

希望这对您有所帮助!