0

我正在 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);
}

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

4

1 回答 1

3

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

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

在第二点上扩展一点：一棵树的预购行走只是意味着每个节点在它的子节点之前被处理。当您进行图搜索时，您希望遍历图的连接组件，只访问每个节点一次，您实际上创建了一个隐式树。也就是说，您的起始节点成为树的根节点。每当您访问一个节点时，您都​​会搜索尚未访问过的相邻节点，即未标记的节点。如果存在这样的节点，则入射边成为树节点，您标记该节点。由于总是只有一个节点被主动持有，因此您需要记住未处理的节点，但是，在某些数据结构中，例如堆栈或队列（而不是显式使用堆栈，您可以进行递归来创建隐式堆栈）。现在，

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

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

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

  • 查看队列前面指示的节点，找到一个未填充的相邻节点：
    • 将节点追加到队列的后面（即矩形中最后一个节点的后面）
    • 标记（即填充）节点
    • 使连接两个节点的线更粗：现在是树边缘
  • 如果没有其他未标记的相邻节点，则将队列中的前节点打勾（即从队列中删除）并继续移动到下一个节点，直到没有其他节点

现在队列矩形包含由图的广度优先搜索所暗示的生成树的前序游走。使用较粗的线可以看到生成树。如果您将队列的矩形视为堆栈，该算法也将起作用，但它会有点混乱，因为您最终会在仍待处理的节点之间勾选节点：而不是查看第一个未勾选的节点，您将查看最后一个未勾选的节点。

在使用图形算法时，我发现将算法可视化非常有帮助。虽然让计算机维护绘图会很好，但在纸上绘制东西并可能通过一些标记的铅笔指示活动节点的低技术替代方案即使不是更好也可以工作。

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

于 2012-01-15T01:33:13.760 回答