二叉树的遍历方式（递归、非递归）

二叉树的前序、中序、后序遍历方式，递归与非递归。（层序遍历的方式已经在之前的博客中写过）

递归方式比较简单。

前序遍历：

void preorder(TreeNode* root){
       if (root){
        cout << root -> val << endl;
        preorder(root -> left);
        preorder(root -> right);
       }
}

前序遍历非递归：

基本思路：利用栈。先输出结点值，再入栈。然后遍历左子树。退栈时，遍历栈顶结点的右子树。

void preorder(const TreeNode* root){
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p || !s.empty()){
        if (p){
            cout << p -> data << " ";
            s.push(p);
            p = p -> left;
        }
        else{
            p = s.top();
            s.pop();
            p = p -> right;  
        }
    }

}

中序遍历非递归：先进栈，再遍历左子树，出栈时才会输出结点值

void inorder(TreeNode* root){
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p || !s.empty()){
        if (p){
            s.push(p);
            p = p -> left;
        }
        else{
            p = s.top();
            s.pop();
            cout << p ->val << " ";   // 注意与前序遍历只有一行代码的不同
            p = p -> right;
        }
    }
}

后序非递归：

用一个bool变量标识结点p的右子树的遍历的状态。不太理解为什么要标记右子树的状态？

void postorder(TreeNode* root){
    stack<pair<TreeNode*, bool> s;
    TreeNode* p = root;
    while (p || s.empty()){
        if (p){
            s.push(make_pair(p, false));   // false 表示右子树未被访问
            p = p -> left;
        }
        else {
            if (s.top().second == false){  // 表示根节点的右子树还未访问
                s.top().second = true;
                p = s.top().first -> right;     // 去遍历右子树
            }
            else{   // 右子树已经访问
                cout << s.top().first -> val << " ";  // 输出根节点的值
                s.pop();                              // 根结点退栈
            }
        }
    }
}

二叉树的遍历方式（递归、非递归）

相关推荐