c++ - 如何使用算法BFS指示生成树的前序

Question

我正在用C ++进行BFS算法的实现以查找生成树，生成树的输出应按顺序显示，但是我对实现表示怀疑，如果不完全了解如何构建树每个节点有很多孩子？考虑递归的树结构可以将树的数据结构写为：

typedef struct node 
{
        int val;
        struct node *left, *right;
}*tree; //tree has been typedefed as a node pointer.

但是不要认为它能像前面提到的那样实现此实现。

这是我以预定顺序返回树的功能：

void preorder(tree t) 
{
        if(t == NULL)
                return;
        printf("%d ", t->val);
        preorder(t->left);
        preorder(t->right);
}

我也想知道是否有任何方法可以在不使用树形结构的情况下对节点进行预排序。

Answer 1

我在帖子中看到了两个具体问题：


一棵树中是否可能有使用两个以上子代的数据结构？当然可以。有趣的是，您发布的节点结构甚至有可能！只需将left指针视为指向第一个子项的指针，并将right指针指向下一个兄弟项的指针。由于对图的广度优先搜索隐式地构建了生成树，因此如果您实际上以某种方式表示它，则可以按顺序遍历该树。
您可以在不使用树形结构的情况下进行预定行走吗？是的，这也是可能的。从本质上讲，DFS和BFS从概念上来说并没有什么不同：您只有一个数据结构，用于维护接下来要访问的节点。对于DFS，这是一个堆栈，对于BFS，这是一个队列。如果在将节点号插入到维护要访问的节点的数据结构中时发出了节点号，则可以得到该树的预排序步行（即，访问该节点的所有子节点都在父节点之后）。


在第二点上进行扩展：一棵树的顺序遍历只意味着每个节点都在其子节点之前进行处理。当您进行图搜索时，您想要遍历图的连接组件，只访问每个节点一次，就可以有效地创建一个隐式树。也就是说，您的起始节点将成为树的根节点。每当您访问节点时，您都​​会搜索尚未访问的相邻节点，即未标记的节点。如果存在这样的节点，则入射边将成为树节点，并标记该节点。由于总是只有一个节点处于活动状态，因此您需要记住一些数据结构中尚未处理的节点，例如一个堆栈或一个队列（您可以进行递归创建隐式创建堆栈，而不是显式使用堆栈）。现在，如果您第一次看到节点时发出该节点号，则您会在其子节点之前对其进行清楚的处理，即最终将节点号写成顺序遍历的顺序。

如果您不明白这一点，请抽出一张纸，画一个图和一个队列：


空心圆的节点及其旁边的节点号
细线边缘
队列只是矩形，开始时不包含任何内容


现在，选择一个节点作为搜索的起始节点，该节点与树的根节点相同。将其编号写入队列中的第一个空白位置并标记，即填充节点。现在继续搜索：


查看队列前面指示的节点，找到未填充的相邻节点：

将节点追加到队列的后面（即，矩形中最后一个节点的后面）
标记（即填充）节点
使连接两个节点的线变粗：现在是树边缘

如果没有其他未标记的相邻节点，则将队列中的前一个节点打勾（即，将其从队列中删除），然后继续进行下一个节点，直到没有其他节点为止


现在，队列矩形包含图的广度优先搜索所隐含的生成树的预定遍历。使用粗线可以看到生成树。如果将队列的矩形视为堆栈，该算法也将起作用，但会有点混乱，因为最终会导致需要处理的节点之间的节点被剔除：而不是查看第一个未剔除的节点，而是查看最后一个未选中的节点。

当使用图算法时，我发现可视化算法非常有帮助。虽然让计算机维护绘图会很不错，但如果不是更好，那是一种技术含量较低的替代方法，它可以在纸上绘图，并可能通过一些带标记的铅笔指示活动节点。

只是对代码的注释：每当您读取任何输入时，请确保您已成功读取数据。顺便说一句，您的代码显然只是C语言，而不是C ++代码：可变长度数组在C ++中不可用。在C ++中，您将使用std::vector<int> followOrder(vertexNumber)而不是int followOrder[vertexNumber]。有趣的是，代码也不是C，因为它使用例如std::queue<int>。