美文网首页
二叉树的前序、中序、后序遍历

二叉树的前序、中序、后序遍历

作者: darkness605 | 来源:发表于2020-09-27 16:24 被阅读0次

    二叉树的遍历整体上是分成两种的,一种是递归的方式,一种是非递归的方式。

    前序遍历的递归方式:

          根据每个节点的步骤来,先输出当前节点的值,再去管左子节点、最后再管右子节点。
          递归的方法有个特点就是,只需要考虑当前步骤该做什么,下一步应该往哪走,即可。
    
        void Pre(TreeNode* root){
            if(root!=nullptr)
            {
                cout <<root->val;
                Pre(root->left);
                Pre(root->right);
            }
        }
    

    前序遍历的非递归方式:

          前序遍历的非递归方式是相对比较简单的,因为是从根节点开始,优先输出当前节点的值,再去管左子节点和右子节点。
          这里我们取一个栈,将root节点先存入初始化的栈中,然后设定循环条件是,栈不为空,每次取栈顶节点的值,再将栈顶节点的右子节点和左子节点依次压入栈中。
         (这里考虑非空并且由于栈的后入先出特性)
    
    void Pre(TreeNode* root){
            stack<TreeNode*> res;
            res.push(root);
            while(!res.empty()){
                TreeNode* temp = res.top();
                res.pop();
                cout << temp->val;
                if(temp->right)
                    res.push(temp->right);
                if(temp->left)
                    res.push(temp->left);
            }
        }
    

    中序遍历的递归方式:

           递归的方式总的来说大同小异,只是每个步骤的逻辑处理顺序不一样。
    
     void Ord(TreeNode* root){
            if(root!=nullptr)
            {
                Ord(root->left);
                cout << root->val;
                Ord(root->right);
            }
        }
    

    中序遍历的非递归方式:

          这里其实就比较复杂了,因为我们在当前节点的处理,是优先当前节点的左子节点。不用递归的话,我们怎么样才能实现每个节点处理时,都优先处理
          左子节点呢?优先输出左子节点,那就把从根节点开始左子节点依次入栈,那这样压栈完毕后,出栈的第一个必定是根节点左子树的最深的左子节点。
          接着我们在查看当前出栈的右子节点是否为空,如果不为空便在输出当前节点的值之后将其入栈。整体代码如下。
    
    void Ord(TreeNode* root){
            stack<TreeNode*> res;
            TreeNode* temp = root;
            while(temp||!res.empty()){
                while(temp)
                {
                    res.push(temp);
                    temp = temp->left;
                }
                if(!res.empty())
                {
                    temp = res.top();
                    res.pop();
                    cout << temp->val ;
                    temp = temp->right;
                }
            }
        }
    

    后序遍历的递归方式:

      同上递归。
    
    void Post(TreeNode* root){
            if(root!=nullptr)
            {
                Post(root->left);
                Post(root->right);
                cout << root->val;
            }
        }
    

    后序遍历的非递归方式:

            取一个栈作为临时存储栈,由于栈的先进后出特性,所以得先把当前节点的右子节点先入栈,再将左子节点再入栈。
    
    void Post(TreeNode* root){
            TreeNode* temp = root;
            stack<TreeNode*> res;
            stack<TreeNode*> tempres;
            while (temp || !tempres.empty()) {
                if (temp) {
                    tempres.push(temp);//
                    res.push(temp);
                    temp = temp->right;
                }
                else {                  
                        temp = tempres.top();
                        tempres.pop();
                        temp = temp->left;
                    }
                }
            while(!res.empty()){
                        post.push_back(res.top()->val);
                        res.pop();
            }
    }
    

    相关文章

      网友评论

          本文标题:二叉树的前序、中序、后序遍历

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