二叉树的广度优先和深度优先遍历

其实之前我们已经学过了二叉树的先序遍历，中序遍历和后序遍历，这些遍历的方式都是几行代码利用递归的方式来实现的。其实这些遍历方式是不怎么符合我们的逻辑的（至少是不符合我的逻辑），不过他们确实的使用简单的算法就可以遍历二叉树的好办法。这不是说这些遍历方式不好（二叉排序树还就是需要中序遍历呢），只是我们还可以学习其他的遍历二叉树的方式。比如下面的广度优先遍历和深度优先遍历。

广度优先

广度优先的基本介绍

广度优先遍历（ Breadth-First Search）一般缩写为BFS。

其过程检验来说是对每一层节点依次访问，访问完一层进入下一层，而且每个节点只能访问一次。对于上面的例子来说，广度优先遍历的 结果是：A,B,C,D,E,F,G,H,I(假设每层节点从左到右访问)。

广度优先的算法实现

先往队列中插入左节点，再插右节点，这样出队就是先左节点后右节点了。

广度优先遍历树，需要用到队列（Queue）来存储节点对象,队列的特点就是先进先出。例如，上面这颗树的访问如下：

• 首先将A节点插入队列中，队列中有元素（A）;

• 将A节点弹出，同时将A节点的左、右节点依次插入队列，B在队首，C在队尾，（B，C），此时得到A节点；

• 继续弹出队首元素，即弹出B，并将B的左、右节点插入队列，C在队首，E在队尾（C,D，E），此时得到B节点；

• 继续弹出，即弹出C，并将C节点的左、中、右节点依次插入队列，（D,E,F,G,H），此时得到C节点；

• 将D弹出，此时D没有子节点，队列中元素为（E,F,G,H），得到D节点；

首先构战树节点

struct TreeNode
{
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val):data(val){
        this->left = nullptr;
        this->right = nullptr;
    }
};

这里就不写二叉树这个类了，就写一个树节点就完事了。

删除树

void deleteTree(TreeNode* root){
    if (root == nullptr){
        return;
    }
    if (root->left != nullptr){
        deleteTree(root->left);
    }
    if (root->right != nullptr){
        deleteTree(root->right);
    }
    delete root;
}

广度遍历算法

vector<TreeNode*> BFSsearch(TreeNode* root) {
    // 首先将A节点插入队列中，队列中有元素（A）
    // 队列是先进先出的一种数据结构
    queue<TreeNode*> node_queue;
    // 按广度遍历的算法来保存节点顺序
    vector<TreeNode*> result;
    node_queue.push(root);
    TreeNode* pop_node;
    while (!node_queue.empty()) {
        // 将第一个节点取出，将节点的左右节点放入队列
        pop_node = node_queue.front();
        result.emplace_back(pop_node);
        node_queue.pop();

        if (pop_node->left != nullptr) {
            node_queue.push(pop_node->left);
        }
        if (pop_node->right != nullptr) {
            node_queue.push(pop_node->right);
        }
    }
    return result;
}

主方法中的测试代码

二叉树的结构：
         1
    2        3
 4   5     6   7
                 8

int main(int argc, char const* argv[]) {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    root->right->right->right = new TreeNode(8);

    vector<TreeNode*> bfs = BFSsearch(root);
    for (auto node : bfs) {
        cout << node->data << " ";
    }
    cout << endl;
    deleteTree(root);

    system("pause");
    return 0;
}

输出的结果：

1 2 3 4 5 6 7 8

深度优先

深度优先基本介绍

深度优先是Depth-First Search（DFS）。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。对于上面的例子来说深度优先遍历的结果就是：A,B,D,E,I,C,F,G,H.(假设先走子节点的的左侧)。

深度优先的算法思路

深度优先遍历各个节点，需要使用到栈（Stack）这种数据结构。stack的特点是是先进后出。

先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。

首先将A节点压入栈中，stack（A）;

• 将A节点弹出，同时将A的子节点C，B压入栈中，此时B在栈的顶部，stack(B,C)；

• 将B节点弹出，同时将B的子节点E，D压入栈中，此时D在栈的顶部，stack（D,E,C）；

• 将D节点弹出，没有子节点压入,此时E在栈的顶部，stack（E，C）；

• 将E节点弹出，同时将E的子节点I压入，stack（I,C）；

• …依次往下，最终遍历完成。

可以看到这个深度优先的算法和广度优先的算法是十分的类似的，一个使用的是队列，一个使用的栈。队列的特点是先进先出，队列的特点是先进后出。

深度优先算法代码实现

vector<TreeNode*> DFSsearch(TreeNode* root) {
    vector<TreeNode*> result;
    stack<TreeNode*> node_stack;
    TreeNode* pop_node;
    node_stack.push(root);

    while (!node_stack.empty()) {
        pop_node = node_stack.top();
        node_stack.pop();
        result.push_back(pop_node);

        if (pop_node->right) {
            node_stack.push(pop_node->right);
        }
        if (pop_node->left) {
            node_stack.push(pop_node->left);
        }
    }
    return result;
}

测试代码和上面的基本都是一样的：

二叉树的结构：
         1
    2        3
 4   5     6   7
                 8

*输出结果: *

1 2 4 5 3 6 7 8

总结

二叉树的深度优先及广度优先遍历算法算是二叉树中比较重要的两个算法了。但是深度优先和广度优先这个并不是二叉树中的概念，其实还有其他很多的数据结构及算法都有深度优先和广度优先算法。比如说图的遍历，也有广度优先和深度优先。总之，一点一点去学吧，么得多大的问题。