我试图自己实现BFS,并为此编写了一些代码。我通过调试器运行了代码,而while循环的所有迭代(最后一个除外)都运行良好。当最后一个指针在队列(缓冲区)内部时,if条件:
if (l) {
buffer.push(l);
cout << l - > val << endl;
}
成为true(当它应该为false时)。并导致分割错误。为什么会这样呢?这是完整的代码...
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node {
int val;
struct node * left;
struct node * right;
};
vector < int > a {
1,
5,
4,
3,
7,
2,
9
};
vector < node > tree(6, {
0,
nullptr,
nullptr
});
void make_tree() {
for (auto i = 0; i < 7; i++) {
tree[i].val = a[i];
}
for (auto j = 0; j < 3; j++) {
tree[j].left = & (tree[2 * (j + 1) - 1]);
tree[j].right = & (tree[2 * (j + 1)]);
}
}
node * temp = & tree[0];
queue < node * > buffer;
void BFS()
{
buffer.push(temp);
node * r = nullptr;
node * l = nullptr;
cout << (buffer.front()) - > val << endl;
while (!buffer.empty())
{
l = (buffer.front() - > left);
if (l) {
buffer.push(l);
cout << l - > val << endl;
}
r = (buffer.front() - > right);
if (r) {
buffer.push(r);
cout << r - > val << endl;
}
buffer.pop();
}
}
int main()
{
make_tree();
BFS();
return 0;
}
您正在从tree
索引到0 .. 6
,但仅创建6个node
。创建7个node
可以解决此问题:
vector < node > tree(7, { 0, nullptr, nullptr });