深度优先搜索与广度优先搜索

迈不过友情╰ 2022-06-09 07:57 291阅读 0赞

# [二叉树深度优先遍历和广度优先遍历][Link 1] #

![805461-20160514164458359-1600906940.png][]

对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序为：ABDECFG。怎么实现这个顺序呢 ？深度优先搜索二叉树是先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。

广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面二叉树的遍历顺序为：ABCDEFG.可以利用队列实现广度优先搜索。

下面给出二叉树dfs和bfs的具体代码：

1 #include <vector>
     2 #include <iostream>
     3 #include <stack>
     4 #include <queue>
     5 using namespace std;
     6 
     7 struct BitNode
     8 {
     9     int data;
    10     BitNode *left, *right;
    11     BitNode(int x) :data(x), left(0), right(0){}
    12 };
    13 
    14 void Create(BitNode *&root)
    15 {
    16     int key;
    17     cin >> key;
    18     if (key == -1)
    19         root = NULL;
    20     else
    21     {
    22         root = new BitNode(key);
    23         Create(root->left);
    24         Create(root->right);
    25     }
    26 }
    27 
    28 void PreOrderTraversal(BitNode *root)
    29 {
    30     if (root)
    31     {
    32         cout << root->data << " ";
    33         PreOrderTraversal(root->left);
    34         PreOrderTraversal(root->right);
    35     }
    36 }
    37 
    38 //深度优先搜索
    39 //利用栈，现将右子树压栈再将左子树压栈
    40 void DepthFirstSearch(BitNode *root)
    41 {
    42     stack<BitNode*> nodeStack;
    43     nodeStack.push(root);
    44     while (!nodeStack.empty())
    45     {
    46         BitNode *node = nodeStack.top();
    47         cout << node->data << ' ';
    48         nodeStack.pop();
    49         if (node->right)
    50         {
    51             nodeStack.push(node->right);
    52         }
    53         if (node->left)
    54         {
    55             nodeStack.push(node->left);
    56         }
    57     }
    58 }
    59 
    60 //广度优先搜索
    61 void BreadthFirstSearch(BitNode *root)
    62 {
    63     queue<BitNode*> nodeQueue;
    64     nodeQueue.push(root);
    65     while (!nodeQueue.empty())
    66     {
    67         BitNode *node = nodeQueue.front();
    68         cout << node->data << ' ';
    69         nodeQueue.pop();
    70         if (node->left)
    71         {
    72             nodeQueue.push(node->left);
    73         }
    74         if (node->right)
    75         {
    76             nodeQueue.push(node->right);
    77         }
    78     }
    79 }
    80 
    81 int  main()
    82 {
    83     BitNode *root = NULL;
    84     Create(root);
    85     //前序遍历
    86     PreOrderTraversal(root);
    87     //深度优先遍历
    88     cout << endl << "dfs" << endl;
    89     DepthFirstSearch(root);
    90     //广度优先搜索
    91     cout << endl << "bfs" << endl;
    92     BreadthFirstSearch(root);
    93 }

[Link 1]: http://www.cnblogs.com/zhangbaochong/p/5492877.html
[805461-20160514164458359-1600906940.png]: /images/20220609/0372f6c59b824b3d87ad4dd4e410d345.png