BFS vs DFS for C ++中的二叉树？

BFS（广度优先搜索） -这是一种树遍历算法，也称为“级别顺序树遍历”。在此遍历中，我们将逐行遍历树，即第一行，然后第二行，依此类推。

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)。

实施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 << "Level Order traversal of binary tree is \n";
   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

实施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 << "\nPreorder traversal of binary tree is \n";
   printPreorder(root);
   cout << "\nInorder traversal of binary tree is \n";
   printInorder(root);
   cout << "\nPostorder traversal of binary tree is \n";
   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