一、深度优先遍历

二叉树的深度优先遍历有三种方式,先序(先根次序)、中序(中根次序)和后序(后根次序)遍历。
因为树的定义本身是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。若采用非递归的方法遍历二叉树,需要采用栈去模拟实现。在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点。

二、广度优先搜索(按层遍历)

广度优先周游的方式是按层次从上到下,从左到右的逐层访问,不难想到,可以利用一个队列来实现。基本思想如下:

1. 按层遍历

#include <iostream>
#include <vector>
#include <queue>
struct Node
{
    int val;
    Node * left;
    Node * right;
    Node(int v) { val = v; left = nullptr; right = nullptr; };
};
//二叉树按层遍历
void level(Node * node, std::vector<int> & Result)
{
    std::queue<Node *> levelQueue;
    levelQueue.emplace(node);
    Node * nowNode = nullptr;
    while (1)
    {
        if (levelQueue.empty())
            break;
        nowNode = levelQueue.front();
        levelQueue.pop();
        if (nowNode == nullptr)
            continue;
        else
        {
            Result.emplace_back(nowNode->val);
            if (nowNode->left != nullptr)
                levelQueue.emplace(nowNode->left);
            if (nowNode->right != nullptr)
                levelQueue.emplace(nowNode->right);
        }
    }
}
int main(void)//按图的最广搜索,使用队列
{
    Node * begin = new Node(1);
    Node * nowpos = begin;
    nowpos->left = new Node(2);
    nowpos->left->left = new Node(3);
    nowpos->left->right = new Node(3);
    begin->right = new Node(4);
    std::vector<int> Result;
    level(begin, Result);
    return 0;
}