是否有可能设计一个节点有无限多个孩子的树？

Question

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

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

Answer 1

你实际上无法存储无限多的孩子,因为那不适合记忆.但是,您可以存储无限多个子节点 - 也就是说,您可以创建树,其中每个节点可以包含任意数量的没有固定上限的子节点.

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

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

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

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

希望这可以帮助!