精华内容
下载资源
问答
  • 关于二叉树前中后序遍历的常见问题
    千次阅读
    2019-09-19 15:14:45

    尊敬的读者您好:笔者很高兴自己的文章能被阅读,但原创与编辑均不易,所以转载请必须注明本文出处并附上本文地址超链接以及博主博客地址:https://blog.csdn.net/vensmallzeng。若觉得本文对您有益处还请帮忙点个赞鼓励一下,笔者在此感谢每一位读者,如需联系笔者,请记下邮箱:zengzenghe@gmail.com,谢谢合作!

     

     

     

    最近不论是笔试还是面试,都经常性的遇到这样的问题:“给定某一二叉树的前序遍历与中序遍历,请返回它的后序遍历”,“给定某一二叉树的后序遍历与中序遍历,请返回它的前序遍历”。为了后面不犯错误,下面就来好好总结一下。

     

    一、给定二叉树的前序遍历为“ABCDEFGH”与中序遍历“BDCEAFHG”,请返回它的后序遍历?

    前序遍历的原则是“根-左-右”,所以前序遍历的第一个节点必然为根节点,然后在中序遍历找到这个根节点,该根节点的左边即为二叉树的左子树所有节点,右边即为二叉树的右子树所有节点,再分别将前序遍历与中序遍历分别拆成两部分,构成两个子树的前序遍历与中序遍历,即左子树前序:BCDE、中序:BDCE,右子树前序:FGH、中序:FHG,通过递归的方法不断划分下去,最终即可求解。

    解题代码如下:

    #include<iostream>
    #include<string>
    
    using namespace std;
    //递归实现后序遍历
    void findpostorder(string s1,string s2){
        if(s1.length()==0) return;
        if(s1.length()==1){
            printf("%c",s1[0]);
            return;
        }
        //访问索引(从0开始)
        int pos=s2.find(s1[0]);
        // 构成左子树的前序遍历与中序遍历
        findpostorder(s1.substr(1,pos),s2.substr(0,pos));//后序遍历左子树
        // 构成右子树的前序遍历与中序遍历
        findpostorder(s1.substr(pos+1,s1.length()-pos-1),s2.substr(pos+1,s2.length()-pos-1));
        // 此处输出则为前序遍历
        printf("%c",s1[0]);
    }
    
    
    int main(){
        string s1,s2;
        while(cin>>s1>>s2){
            // 输入二叉树的前序遍历与中序遍历
            findpostorder(s1,s2);
            printf("\n");
        }
    }
    

     

    二、给定二叉树的后序遍历为“DECBHGFA”与中序遍历“BDCEAFHG”,请返回它的前序遍历?

    #include<iostream>
    #include<string>
    
    using namespace std;
    //递归实现前序遍历
    void findpreorder(string s1,string s2){
        if(s1.length()==0) return;
        if(s1.length()==1){
            printf("%c",s1[s1.length()-1]);
            return;
        }
        //访问索引(从0开始)
        int pos=s2.find(s1[s1.length()-1]);
        // 此处输出则为前序遍历
        printf("%c",s1[s1.length()-1]);
        // 构成左子树的后序遍历与中序遍历
        findpreorder(s1.substr(0,pos),s2.substr(0,pos));
        // 构成右子树的后序遍历与中序遍历
        findpreorder(s1.substr(pos,s1.length()-pos-1),s2.substr(pos+1,s2.length()-pos-1));
    
    }
    
    
    int main(){
        string s1,s2;
        while(cin>>s1>>s2){
            // 输入二叉树的后序遍历与中序遍历
            findpreorder(s1,s2);
            printf("\n");
        }
    }

     

     

     

     日积月累,与君共进,增增小结,未完待续。

    更多相关内容
  • 基于C++的数据结构:二叉树前中后序遍历+重建+输出 以前课程作业写的代码
  • 用非递归后序遍历二叉树的方式实现的表达式计算,进行了精细的表达式逻辑判断和处理,可进行加减乘除、括号、小数的计算。项目结构清晰,基本都有代码注释,可用于数据结构实验。同为学习人,能力有限,不足之处还请...
  • 二叉树前中后序遍历1.二叉树前中后序遍历简介2.递归的方法去实现3.递推的方式去实现4.练手题目(leetcode) 1.二叉树前中后序遍历简介 前序遍历:先访问根节点,再访问左节点,最后访问右节点 中序遍历:先访问左...

    1.二叉树前中后序遍历简介

    前序遍历:先访问根节点,再访问左节点,最后访问右节点
    中序遍历:先访问左节点,再访问根节点,最后访问右节点
    后续遍历:先访问左节点,再访问右节点,最后访问根节点

    2.递归的方法去实现

    深度搜索二叉树的方法:先遍历左子树再遍历右子树

    void dfs(TreeNode* root)
     {
            if(root->left)
            dfs(root->left);
            if(root->right)
            dfs(root->right);
      }
    

    那么遍历的顺序确定了,每种遍历方式其实就是访问的位置在哪了(我们只需要关系根节点的访问顺序)
    前序遍历:先访问根节点,所以在遍历前访问即可:

    void dfs(TreeNode* root)
     {
            cout<<root->val<<endl;//访问
            if(root->left)
            dfs(root->left);
            if(root->right)
            dfs(root->right);
     }
    

    中序遍历:先访问左节点,所以在左节点遍历后访问即可:

    void dfs(TreeNode* root)
     {
            if(root->left)
            dfs(root->left); 
    		cout<<root->val<<endl;//访问
            if(root->right)
            dfs(root->right);
     }
    

    后序遍历:先访问左节点,再访问右节点,所以在左右节点遍历后访问即可

    void dfs(TreeNode* root)
    {
            if(root->left)
            dfs(root->left);
            if(root->right)
            dfs(root->right);
    		cout<<root->val<<endl;//访问
    }
    

    3.递推的方式去实现

    其实一般用递归写的都能递推去实现;
    递推的话就用栈去模拟函数开辟子函数的过程,只有当子函数全部执行结束,父函数才会继续执行;这符合栈的后进先出的道理。那么我们将进栈当作遍历左右子树的过程,再确定访问顺序即可。
    栈用来存储根节点和左节点。
    前序遍历:先访问根节点,再访问左节点,所以在遍历前访问即可;用递推的话就是在其进栈前访问

    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            vector<int> nums;
            stack<TreeNode*> s;
            while(root||!s.empty())
            {
                if(!root)
                {
                    root=s.top();
                    s.pop();
                    root=root->right;//遍历右子树
                }
                else
                {
                    while(root)
                    {
                        nums.push_back(root->val);//访问
                        s.push(root);
                        root=root->left;//遍历左子树
                    }
                }
            }
            return nums;
        }
    };
    

    中序遍历:先访问左节点,再访问根节点,所以在左节点遍历后访问即可;用递推的话就是出栈时访问

    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
             vector<int> nums;
            stack<TreeNode*> s;
            while(root||!s.empty())
            {
                if(!root)
                {
                    root=s.top();
                    s.pop();
                    nums.push_back(root->val);
                    root=root->right;
                }
                else
                {
                    while(root)
                    { 
                        s.push(root);
                        root=root->left;
                    }
                }
            }
            return nums;
        }
    };
    

    后序遍历:先访问左节点,再访问右节点,所以在左右节点遍历后访问即可;递推就要为其加一个判断条件,判断其右节点是否访问过,记录上一个访问节点即可(该节点的上一个访问节点必然是其右节点(存在,不存在就是NULL));

    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
           vector<int> nums;
            stack<TreeNode*> s;
            TreeNode *pre=nullptr;//记录上一个访问的节点
            while(root||!s.empty())
            {
                if(!root)
                {
                    root=s.top();
                    s.pop(); 
                    if(!root->right||root->right==pre)//没有右节点或者右节点访问过
                    {
                        nums.push_back(root->val);
                        pre=root;
                        root=nullptr;
                    }
                    else
                    {
                        s.push(root);//右节点没访问回到栈中
                        root=root->right;
                    }
                }
                else
                {
                    while(root)
                    { 
                        s.push(root);
                        root=root->left; 
                    }
                }
            }
            return nums;
        }
    };
    

    4.练手题目(leetcode)

    144. 二叉树的前序遍历
    94. 二叉树的中序遍历
    145. 二叉树的后序遍历

    展开全文
  • 二叉树递归实现前中后序遍历非常的简单,只需要调整处理语句出现的位置即可。 void order(TreeNode* root) { if (!root) return; //前序 order(root->left); //中序 order(root->right); //后序 } ...

    二叉树前中后序递归的本质



    二叉树递归实现前中后序遍历非常的简单,只需要调整处理语句出现的位置即可。

    void order(TreeNode* root)
    {
    	if (!root)	
    		return;
    
    	//前序
    	order(root->left);
    	//中序
    	order(root->right);
    	//后序
    }
    

    二叉树每个节点都会被经过三次,我们使其每个位置都打印节点。

    void order(TreeNode* root)
    {
    	if (!root)
    		return;
    
    	cout << root->val << " ";
    	order(root->left);
    	cout << root->val << " ";
    	order(root->right);
    	cout << root->val << " ";
    }
    

    如果只取第一次出现的节点,那就是前序遍历,只取第二次出现的节点那就是中序遍历,只取第三次出现的节点就是后序遍历。这种遍历序列可以称为递归序。

    在这里插入图片描述



    非递归实现前中后序


    前序遍历

    前序遍历非递归比较好理解,需要利用到一个栈来模拟递归过程。

    在这里插入图片描述

    代码示例:

    
    void prevOrderNonR(TreeNode* root)
    {
    	if (!root)	return;
    
    	stack<TreeNode*> st;
    	st.push(root);
    	while (!st.empty())
    	{
    		TreeNode* cur = st.top();
    		st.pop();
    		cout << cur->_val << " ";
    		
    		if (cur->_right)
    			st.push(cur->_right);
    		if (cur->_left)
    			st.push(cur->_left);
    	}
    
    }
    


    后续遍历:

    上面使用栈实现了二叉树的前序遍历,在此基础上稍作修改就可以实现后续遍历。
    众所周知,二叉树的前序遍历顺序为 根 左子树 右子树

    我们改变前序遍历的压入节点的顺序,原先为先push右子树,再push左子树。现在改变其顺序,先压左,在压右。
    此时前序遍历的顺序变为 根 右子树 左子树

    后序遍历的顺序为 左子树 右子树 根,有没有发现,后序遍历序列的顺序就是上述变形序列的逆序。

    在这里插入图片描述

    代码示例:

     vector<int> postorderTraversal(TreeNode* root) {
            vector<int> ret;
            if(!root)   return ret;
    
            stack<TreeNode*> helper;
            stack<TreeNode*> post;
            helper.push(root);
    
            while(!helper.empty())
            {
                TreeNode* node = helper.top();
                helper.pop();
                post.push(node); // 并不直接处理,存入一个栈中
    
                if(node->left)
                    helper.push(node->left);  //改变节点入栈顺序,先压左 
                if(node->right)
                    helper.push(node->right);//再压右
            }
    		//此时这个栈的弹出序列就为后序遍历序列
            while(!post.empty())
            {
                ret.push_back(post.top()->val);
                post.pop();
            }
    
            return ret;
        }
    


    中序遍历:

    在这里插入图片描述

    代码示例:

    void inOrderNonR(TreeNode* root)
    {
    	if (!root)	return;
    
    	stack<TreeNode*> st;
    	TreeNode* cur = root;
    	while (cur || !st.empty())
    	{
    		if (cur != nullptr)
    		{
    			st.push(cur);
    			cur = cur->_left;
    		}
    		else
    		{
    			cur = st.top();
    			st.pop();
    			cout << cur->_val << ' ';
    			cur = cur->_right;
    		}
    	}
    }
    
    展开全文
  • 主要介绍了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作,涉及Python基于先序遍历和中序遍历构造二叉树,再后序遍历输出相关操作技巧,需要的朋友可以参考下
  • 后序遍历:左右根 前序遍历:ABDEGCF 中序遍历:DBGEACF 后序遍历:DGEBFCA 经常会遇到给出其中两个遍历顺序求出另一个顺序题? 解题思路: (1)前序遍历第一个节点为根节点 (2)中序遍历特性中间为根,...

    二叉树的遍历



    二叉树的遍历

    口诀:

    • 前序遍历:根左右

    • 中序遍历:左根右

    • 后序遍历:左右根


    在这里插入图片描述


    前序遍历:ABDEGCF

    中序遍历:DBGEACF

    后序遍历:DGEBFCA


    经常会遇到给出其中两个遍历顺序求出另一个顺序题?


    解题思路:

    (1)前序遍历第一个节点为根节点
    (2)中序遍历特性中间为根,左侧为左子树,右侧为右子树
    (3)后序遍历最后一个节点为根节点


    比如:

    前序:ABDEC

    中序:DBEAC

    求后序?


    解:


    第一步:根据前序遍历第一个节点为根节点得知,A为根

    第二步:根据中序DBEAC得知,A前面的是左子树,说明 DBE在 A左侧,C在右侧,目前可以得出AC的位置

    第三步:根据剩下的前序 BDEC 得知,B为根

    第四步:根据剩下的中序 DBE 得知,D在B左侧,E在B右侧,所以可以画出整个二叉树图

    在这里插入图片描述

    第五步:输出后序遍历结果,DEBCA


    方法就是参考前中后序遍历特性,依次类推,循环查找下去



    欢迎关注,谢谢!


    刚开始写微信公众号,请多多关注,欢迎,多谢!

    微信公众号:《Java学习积累》
    请关注一下,多谢!!!
    微信公众号:Java学习积累

    展开全文
  • 之前的一篇随笔(二叉树、前序遍历、中序遍历、后序遍历)只对二叉树的遍历进行了笼统的描述,这篇随笔重点对、后序的遍历顺序进行分析 二叉树的遍历 二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序...
  • js代码-二叉树迭代法后序遍历
  • //C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include “stdafx.h”#include<iostream>#include<string>#include <stack>using namespace std;template<class>struct BiNode{ T data; struct...
  • 前序遍历:根在,根左右 中序遍历:根在中,左根右 后序遍历:根在后,左右根
  • 1.输入前序和中序遍历结果,建立二叉树 2.实现二叉树的三种递归遍历算方法 3.实现二叉树的三种非递归遍历算法 4.实现二叉树的旋转90°后的打印,直观树形结构
  • NULL 博文链接:https://128kj.iteye.com/blog/1692248
  • 数据结构试验报告用先序中序建立二叉树后序遍历非递归.pdf
  • 首先回忆一下前中后序遍历的概念 前序遍历首先访问根结点...已知二叉树的结构,快速推算前中后序遍历 二叉树如图 中序遍历 根据中序遍历定义 第一步:2(左)4(根)6(右) 第二步:遍历第一步的非根节点,还是按照中序遍历
  • 主要介绍了Python二叉树的遍历操作,结合实例形式分析了Python针对二叉树的前序遍历,中序遍历,后序遍历,层序遍历等相关操作实现技巧,需要的朋友可以参考下
  • 二叉树前中后序遍历简介 ​ 前序遍历、中序遍历和后序遍历是三种利用深度优先搜索遍历二叉树的方式。它们是在对节点访问的顺序有一点不同,其它完全相同。例如层次遍历得到的二叉数为 [1,2,3,4,5,6,7] ​ NLR 其前序...
  • 数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
  • 二叉树前中后序遍历

    2020-09-17 23:02:28
    首先理解前中后序遍历。 他们是相对根节点的遍历前后来决定的; 也就是遍历顺序如果是前序遍历 : 就是按先遍历根节点,在遍历左节点,再遍历右节点; 从下面的二叉树体会一下: 前序遍历结果是:ABDEGCFH 中序遍历...
  • 二叉树中已知中序遍历和前序遍历(后序遍历),求后序遍历(前序遍历)(C++)
  • 使用递归实现二叉树前中后序遍历很简单,写法基本相同。但用迭代稍有不同,较递归稍难理解和记忆,但迭代效率更高。下面是用迭代实现二叉树前中后序遍历的代码示例。 #include <iostream> #include <...
  • 前序、中序、后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中。方法有很多,这里只举一种,先定义栈结点的数据结构 代码如下:typedef struct{...
  • [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
  • 用C语言实现数据结构中二叉树的前序中序后序遍历 int main()//主函数部分 { BiTree T=NULL; int Layer=0; int LayerT=0; printf("请输入二叉树:\n"); CreatBiTree(&T);printf("你输入的二叉树为:(竖型树状...
  • Python基础算法篇-二叉树前中后序遍历
  • 就是一个 简单的 二叉树的建立及前中后序遍历的 代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 94,226
精华内容 37,690
关键字:

二叉树的前中后序遍历

友情链接: WRFV3.1.TAR.gz