原创内容，转载请注明原文网址：http://homeqin.cn/a/wenzhangboke/jishutiandi/2018/1227/281.html

常州微信网站平台开发-二叉树深度优先遍历和广度优先遍历

　　对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。以上面二叉树为例，深度优先搜索的顺序

为：ABDECFG。常州手游开发怎么实现这个顺序呢 ？深度优先搜索二叉树是先访问根结点，然后遍历左子树接着是遍历右子树，因此我们可以利用堆栈的先进后出的特点，

现将右子树压栈，再将左子树压栈，这样左子树就位于栈顶，可以保证结点的左子树先与右子树被遍历。

　　广度优先搜索(Breadth First Search),又叫宽度优先搜索或横向优先搜索，是从根结点开始沿着树的宽度搜索遍历，上面常州游戏开发培训二叉树的遍历顺序为：ABCDEFG.

可以利用队列实现广度优先搜索。

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

#include <vector>

#include <iostream>

#include <stack>

#include <queue>

using namespace std;

struct BitNode

{

    int data;

    BitNode *left, *right;

    BitNode(int x) :data(x), left(0), right(0){}

};

void Create(BitNode *&root)

{

    int key;

    cin >> key;

    if (key == -1)

        root = NULL;

    else

    {

        root = new BitNode(key);

        Create(root->left);

        Create(root->right);

    }

}

void PreOrderTraversal(BitNode *root)

{

    if (root)

    {

        cout << root->data << " ";

        PreOrderTraversal(root->left);

        PreOrderTraversal(root->right);

    }

}

//深度优先搜索

//利用栈，现将右子树压栈再将左子树压栈

void DepthFirstSearch(BitNode *root)

{

    stack<BitNode*> nodeStack;

    nodeStack.push(root);

    while (!nodeStack.empty())

    {

        BitNode *node = nodeStack.top();

        cout << node->data << ' ';

        nodeStack.pop();

        if (node->right)

        {

            nodeStack.push(node->right);

        }

        if (node->left)

        {

            nodeStack.push(node->left);

        }

    }

}

//广度优先搜索

void BreadthFirstSearch(BitNode *root)

{

    queue<BitNode*> nodeQueue;

    nodeQueue.push(root);

    while (!nodeQueue.empty())

    {

        BitNode *node = nodeQueue.front();

        cout << node->data << ' ';

        nodeQueue.pop();

        if (node->left)

        {

            nodeQueue.push(node->left);

        }

        if (node->right)

        {

            nodeQueue.push(node->right);

        }

    }

}

int  main()

{

    BitNode *root = NULL;

    Create(root);

    //前序遍历

    PreOrderTraversal(root);

    //深度优先遍历

    cout << endl << "dfs" << endl;

    DepthFirstSearch(root);

    //广度优先搜索

    cout << endl << "bfs" << endl;

    BreadthFirstSearch(root);

}