二叉树遍历

简介

二叉树的遍历，从和根节点的关系来看，可以分为前序遍历，中序遍历，后序遍历三种方式，这三种遍历形式在部分场景也被称之为先根遍历，中根遍历，后根遍历。从遍历的方式来看，可以分为广度优先遍历和深度优先遍历。

原理

先序遍历

前序遍历二叉树是先遍历根节点，然后遍历左子树，最后遍历右子树。可以想象是绕着二叉树外围转一圈的路径。

非递归算法：

void printPreorder2(TreeNode* head){
    cout << "Pre Order:" << endl;
    if (head != nullptr){
        stack<TreeNode*> *sta = new stack<TreeNode*>;
        sta->push(head);
        TreeNode* cur = head;
        while(!sta->empty()){
            cur = sta->top();
            sta->pop();
            cout << cur->value << " ";
            if (cur->right != nullptr){
                sta->push(cur->right);
            }
            if (cur->left != nullptr){
                sta->push(cur->left);     // 先压右边节点，再压左边节点，这与栈的特性有关
            }
        }
    }
    cout << endl;
}

中序遍历

中序遍历是把先遍历左子树，然后遍历根节点，最后遍历右子树，所以中序遍历是从左到右遍历的，二叉树在平面上的投影就是中序遍历的结果。

非递归算法：

void printInorder2(TreeNode* head){
     cout << "In Order:" << endl;
     if(head != nullptr){
         stack<TreeNode*>* sta = new stack<TreeNode*>;
         TreeNode* cur = head;
         while(!sta->empty() || cur != nullptr){
             if(cur != nullptr){
                sta->push(cur);
                cur = cur->left;
             }else{
                cur = sta->top();
                sta->pop();
                cout << cur->value << " ";
                cur = cur->right;
             }
         }
     }
     cout << endl;
}

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后遍历根节点，可以认为是和摘葡萄的过程类似，先从左到右把下面的葡萄摘了，然后再摘上面的葡萄。

递归算法：

非递归算法：

void printPostorder2(TreeNode* head){
    cout << "Post Order:" << endl;
    if (head != nullptr){
        stack<TreeNode*>* sta1 = new stack<TreeNode*>;
        stack<TreeNode*>* sta2 = new stack<TreeNode*>;
        TreeNode* cur = head;
        sta1->push(cur);
        while(!sta1->empty()){
            cur = sta1->top();
            sta1->pop();      // 弹出的是最晚被压入栈的数据
            sta2->push(cur);
            if(cur->left != nullptr){
                sta1->push(cur->left);
            }
            if(cur->right != nullptr){
                sta1->push(cur->right);
            }
        }
        while(!sta2->empty()){
            cur = sta2->top();
            sta2->pop();
            cout << cur->value << " ";
        }
    }
    cout << endl;
}