数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究用于 C++ 中的二叉树的 BFS 与 DFS？
BFS（广度优先搜索） − 它是一种树遍历算法，又称为层次序遍历树。在此遍历中，我们将按行遍历树，即第 1 行，然后是第 2 行，依此类推。
DFS（深度优先搜索） − 它是一种树遍历算法，遍历结构达到其最深节点。有三种最常用的方法用于使用 DFS 遍历树。它进入每个节点的深度作为根节点，然后进入下一个。
以树为例
让我们使用这两种方法找出树的遍历 −
BFS traversal : A B K M S T DFS traversal : Preorder : A M N K S T PostOrder: M B S T K A InOrder: M B A S K T
现在，正如我们所知，这两种算法的使用在应用中有一些相似之处，也有一些不同之处。两者都已在动态规划中找到应用，所以让我们看看它们如何工作。
BFS 和 DFS 的时间复杂度都是O(n)。
BFS 中遍历所需空间是宽度的顺序O(w)，而 DFS 中遍历所需的的空间是树的高度顺序O(h)。
实施广度优先搜索树遍历算法
示例
#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 << "Level Order traversal of binary tree is
"; 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; }
输出
Level Order traversal of binary tree is 1 2 3 4 5
实施深度优先搜索算法
示例
#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 << "
Preorder traversal of binary tree is
";
printPreorder(root);
cout << "
Inorder traversal of binary tree is
";
printInorder(root);
cout << "
Postorder traversal of binary tree is
";
printPostorder(root);
return 0;
}输出
Preorder traversal of binary tree is 1 2 4 5 3 Inorder traversal of binary tree is 4 2 5 1 3 Postorder traversal of binary tree is 4 5 2 3 1
更新于：2019 年 10 月 4 日
9K+ 查看
广告