C++ 中二叉树的 BFS 与 DFS 哪个好?
server side programmingprogramming
BFS(广度优先搜索) − 是一种树遍历算法，也称为层次顺序树遍历。在此遍历中，我们将逐行遍历树，即第 1 行，然后是第 2 行，依此类推。
DFS(深度优先搜索) − 是一种树遍历算法，可遍历结构到其最深节点。使用 DFS 遍历树的最常用方法有三种。它深入到每个节点作为根节点，然后转到下一个节点。
解决树问题
让我们使用这两种方法找到树的遍历＆minus;
BFS 遍历:A B K M S T DFS 遍历: 前序:A M N K S T 后序:M B S T K A 中序:M B A S K T
现在，我们知道这两种算法的使用在应用中有一些相似之处和一些不同之处。两者都在动态规划中找到了应用，让我们看看这些东西对谁有用。
BFS 和 DFS 的时间复杂度都是 O(n)。
BFS 中遍历所需的空间是树的宽度 O(w) 的数量级，而 DFS 中遍历所需的空间是树的高度 O(h) 的数量级。
BFS 树遍历算法 的实现，
示例
#include <iostream> #includeusing namespace std; struct Node { int data; struct Node *left, *right; }; Node* newNode(int data) { Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } int main() { Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); cout << "二叉树的层序遍历为
"; queue<Node *> q; q.push(root); while (q.empty() == false) { Node *node = q.front(); cout << node->data << " "; q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } return 0; }
输出
二叉树的层序遍历为 1 2 3 4 5
DFS树遍历算法的实现，
示例
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* left, *right;
Node(int data) {
this->data = data;
left = right = NULL;
}
};
void printPostorder(struct Node* node) {
if (node == NULL)
return;
printPostorder(node->left);
printPostorder(node->right);
cout << node->data << " ";
}
void printInorder(struct Node* node) {
if (node == NULL)
return;
printInorder(node->left);
cout << node->data << " ";
printInorder(node->right);
}
void printPreorder(struct Node* node) {
if (node == NULL)
return;
cout << node->data << " ";
printPreorder(node->left);
printPreorder(node->right);
}
int main() {
struct Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "
二叉树的前序遍历是
";
printPreorder(root);
cout << "
二叉树的中序遍历是
";
printInorder(root);
cout << "
二叉树的后序遍历是
";
printPostorder(root);
return 0;
}
输出
二叉树的前序遍历是 1 2 4 5 3 二叉树的中序遍历是 4 2 5 1 3 二叉树的后序遍历是 4 5 2 3 1
