二叉树

前言

二叉树的遍历主要有深度优先遍历和广度优先遍历，深度优先遍历是优先访问一个子树上的所有节点，访问的属性是竖向的，而广度优先遍历则是优先访问同一层的所有节点，访问属性是横向的。

深度优先遍历

深度优先遍历主要有三种顺序：

• 前序遍历 —— 根左右
• 中序遍历 —— 左根右
• 后序遍历 —— 左右根

这三种遍历顺序用递归可以很容易实现，主要讲的是非递归的实现方法。而要使用迭代的方法来遍历二叉树，需要用到栈的特性。

前序遍历（非递归C++）

算法：

1. 根节点入栈
2. 访问栈顶元素并将其出栈
3. 将左右子树入栈，由于访问顺序是"根左右"，且使用的是栈，因此右子树先于左子树入栈
4. 重复步骤2、3，直到栈为空

void preOrder(BTNode* root) {
    stack<BTNode*> S;
    BTNode* cur = NULL;
    if(root == NULL)
        return;
    S.push(root);   //根节点入栈
    while(!S.empty()) {
        //访问顺序"根左右"
        cur = S.top();
        cout<<""<<cur->data<<"\n";
        //出栈访问过的节点
        S.pop();
        //先入栈右子树，这样就可以先访问左子树
        if(cur->right != NULL)
            S.push(cur->right);
        if(cur->left != NULL)
            S.push(cur->left);
    }
}

中序遍历（非递归C++）

算法：

1. 根节点入栈
2. 遍历左孩子节点，入栈，直到左子树为空
3. 访问栈顶节点并将栈顶节点出栈
4. 对右子树进行步骤2、3，访问当前节点的右子树
5. 重复步骤2、3、4，直到栈空

void midOrder(BTNode* root) {
    stack<BTNode*> S;
    BTNode* cur = NULL;
    if(root == NULL)
        return;
    S.push(root);   //根节点入栈
    cur = root;
    while(!S.empty()) {
        //访问顺序"左根右"
        while(cur) {    //将左孩子依次入栈
            S.push(cur);
            cur = cur->left;
        }
        //访问最左孩子
        cur = S.top();
        cout<<""<<cur->data<<"\n";
        S.pop();
        //对右子树进行一样的操作
        cur = cur->right;
    }
}

层次遍历

层次遍历就是广度优先遍历，需要使用队列的特性FIFO

算法：

1. 根节点入队
2. 若队列非空，出队一个元素并访问，接着将其左右孩子入队
3. 重复步骤2直至队空

void levelOrder(BTNode* root) {
    queue<BTNode*> Q;
    if(root == NULL)
        return;
    BTNode* cur = root;
    Q.push(root);
    while(!Q.empty()) {
        //访问队首元素
        cur = Q.front();
        cout<<cur->data<<"\n";
        Q.pop();
        /*将左右孩子入队*/
        if(cur->left != NULL)
            Q.push(cur->left);
        if(cur->right != NULL)
            Q.push(cur->left);
    }
}