美文网首页04 计算机基础
用栈实现二叉树的遍历

用栈实现二叉树的遍历

作者: 阿雀雀雀雀雀雀 | 来源:发表于2017-06-19 15:13 被阅读420次
    用栈实现二叉树的遍历不如用递归实现的简单,需要一些技巧。
    用递归实现三种遍历方式只需改变递归顺序就可以依次完成前序、中序、后序的遍历了。
    水平有限,如有错误望指正
    

    栈实现前序遍历

    栈实现前序遍历较简单,由于每次先输出根节点,再输出左节点随后是右节点。因此我的处理逻辑是:

    1、若栈非空输出根节点,并出栈
    2、将右节点压栈(如果存在)
    3、将左节点压栈(如果存在)
    4、重复第1步直到栈空

    注意:之所以先压右节点是考虑了栈的特性,这样在迭代过程中可以先拿到左节点处理

    以下是代码:

    void preTraversal(TreeNode* root){
        if(root==NULL)return;
        TreeNode*cur=root;
        stack<TreeNode*>S;
        S.push(cur);
        while(!S.empty()){
            cur = S.top();
            cout<<cur->val<<" ";
            S.pop();
            if(cur->right!=NULL)S.push(cur->right);
            if(cur->left!=NULL)S.push(cur->left);
        }
        cout<<endl;
    }
    

    栈的中序遍历

    栈的中序遍历需要套两层循环,由于需要先输出左节点,因此必须向下查找直到左节点为空才能输出。处理逻辑如下:

    1、如果栈顶元素非空且左节点存在,将其入栈,重复该过程。若不存在则进入第2步
    2、若栈非空,输出栈顶元素并出栈。判断刚出栈的元素的右节点是否存在,不存在重复第2步,存在则将右节点入栈,跳至第1步

    代码如下:

    void inorderTraversal(TreeNode *root){
        if(root==NULL)return;
        stack<TreeNode *>S;
        S.push(root);
        while(!S.empty()){
            //该过程一直找到没有左节点的节点才停止
            while(S.top()->left!=NULL){
                S.push(S.top()->left);
            }
            //此时的S.top()是一个没有left的节点,按照中序遍历的特性,可以将其直接输出。
            //while循环会一直将栈顶输出,直到遇到有右节点的节点,这样能保证栈中元素不会重复寻找左孩子
            while(!S.empty()){
                TreeNode *cur = S.top();
                cout<<cur>val<<" ";
                S.pop();
                
                if(cur>right!=NULL){
                    S.push(cur->right);
                    break;
                }
            }
        }
        cout<<endl;
    }
    

    栈的后序遍历

    后序遍历在中序的双层循环的基础上需要加入一个记录,专门记录上一次出栈的节点。步骤如下:

    1、如果栈顶元素非空且左节点存在,将其入栈,重复该过程。若不存在则进入第2步(该过程和中序遍历一致)
    2、判断上一次出栈节点是否当前节点的右节点,或者当前节点是否存在右节点,满足任一条件,将当前节点输出,并出栈。否则将右节点压栈。跳至第1步

    void postTraversal(TreeNode* root){
        if(root==NULL)return;
        stack<TreeNode*>S;
        S.push(root);
        TreeNode* lastPopNode=NULL;
        while(!S.empty()){
            while(S.top()->left!=NULL){
                S.push(S.top()->left);
            }
            while(!S.empty()){
                if(lastPopNode==S.top()->right||S.top()->right==NULL){
                    cout<<S.top()->val<<" ";
                    lastPopNode=S.top();
                    S.pop();
                }
                else if(S.top()->right!=NULL){
                    S.push(S.top()->right);
                    break;
                }
            }
        }
        cout<<endl;
    }

    相关文章

      网友评论

        本文标题:用栈实现二叉树的遍历

        本文链接:https://www.haomeiwen.com/subject/hcggqxtx.html