資料結構
網路
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+ 檢視
廣告