c++ - 具有多个子节点的树的广度优先打印

Question

我有一个树数据结构，其中父节点可以有任意数量的子节点（> = 0）。（参见 sample_tree.jpeg）我想创建这样的树。我想到的一种可能的方法是创建一个链表，如 my_approach 图片所示。链表如图所示连接。你能帮我用这种结构写广度优先打印吗？请用 C++ 编写代码。如果不可能，你能推荐合适的结构吗？

Answer 1

将每个节点存储在链表中将是一种（可能）糟糕的管理方式，因为您必须知道接下来应该执行的顺序，特别是如果您没有按照要打印的顺序添加它们出去。

更好的数据结构是为每个节点创建一个类，并给它一个向量的私有变量或它的孩子的链表。

然后使用一个不同的类来管理每个节点的打印，通过为打印它们的顺序维护一个 FIFO 队列。

一些基本的伪代码，就像不久前我这样做了：

class Node {
    public:
        ...    
        void addChildren(vector<Node*>*);


    private:
       vector<Node*> _children;
};

void addChildren(vector<Node*>* queue) {
    for (unsigned int i = 0; i < _children.size(); i++) {
        queue->push_back(_children.at(i));
    }
}

其中 queue 变量只是一个由 main 函数（或另一个类，如果你想要更好的封装）维护的向量，它被迭代了。您可能需要明确添加的唯一内容是队列中的第一个节点。

然后从队列打印时：

vector<Node*> queue;

//create your nodes statically or dynamically
//populate the queue with the first node

for (unsigned int i = 0; i < queue.size(); i++) {
    //print whatever you want from the node here

    //This adds the current node's children to the end of the FIFO queue
    queue.at(i)->getChildren(queue);
}

这应该遍历所有节点并以广度优先的方式添加它们。

请注意，我在这里将链表更改为向量，因为当您只需要将数据添加到容器的末尾时它会更快。