精华内容
下载资源
问答
  • 前序遍历+中序遍历=后序遍历 中序遍历+后序遍历=前序遍历

    前序 = 根 左 右 PreOrder
    后序 = 左 右 根 PostOrder
    中序 = 左 根 右 InOrder

    前序遍历+中序遍历=后序遍历
    @UVa536 Tree Recovery

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    const int maxn = 30;
    char pre[maxn], in[maxn];
    void Build_PostTree(char *in, char *pre, int len)
    {
        if(!len) return;
        int i = 0;
        for( ; i < len; i++)
            if(in[i] == *pre) break;
        Build_PostTree(in, pre+1, i); //Left
        Build_PostTree(in + i + 1, pre + i + 1, len - i - 1); // Right
        cout << *pre;
        return;
    }
    int main()
    {
        //freopen("in.txt","r",stdin);
        while(scanf("%s %s", pre, in) != EOF){
            int len = strlen(pre);
            Build_PostTree(in, pre, len);
            cout << endl;
        }
        return 0;
    }
    #define RUN
    #ifdef RUN
    
    
    #include<stdio.h>
    #include<string.h>
    const int MAXN = 30;
    
    //因为先序遍历的第一个字符就是根,所以只需在中序遍历中找到它的位置,
    //就能递归遍历其左右子树
    //根据长度为n的先序序列s1和中序序列s2,构造一个长度为n的后序序列
    void build(int n, char* s1, char* s2, char* s) {
      if(n <= 0) return;
      //找到根结点在中序遍历中的位置
      int p = strchr(s2, s1[0]) - s2;
      //递归构造左子树的后序遍历
      build(p, s1+1, s2, s);
      //递归构造右子树的后序遍历
      build(n-p-1, s1+p+1, s2+p+1, s+p);
      //把根节点添加到最后
      s[n-1] = s1[0];
    }
    
    int main() {
    
    #ifndef ONLINE_JUDGE
        freopen("536.in", "r", stdin);
        freopen("536.out", "w", stdout); 
    #endif
    
      char s1[MAXN], s2[MAXN], ans[MAXN];
      while(scanf("%s%s", s1, s2) == 2) {
        int n = strlen(s1);
        build(n, s1, s2, ans);
        ans[n] = '\0';
        printf("%s\n", ans);
      }
      return 0;
    }
    
    #endif

    中序遍历+后序遍历=前序遍历

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    typedef long long LL;
    const int maxn = 30;
    char in[maxn], post[maxn];
    void Build_PerTree(char *in, char *post, int len)
    {
        if(len == 0) return;
        cout << *(post + len - 1);
        int i = 0;
        for( ; i < len; i++)
            if(in[i] == *(post + len - 1)) break;
        Build_PerTree(in, post, i); //Left
        Build_PerTree(in + i + 1, post + i, len - i - 1); // Right
        return ;
    }
    int main()
    {
       // freopen("in.txt","r",stdin);
        while(scanf("%s %s", in, post) != EOF){
            int len = strlen(post);
            Build_PerTree(in, post, len);
            cout << endl;
        }
        return 0;
    }

    大神: http://blog.csdn.net/fightforyourdream/article/details/8638874/

    展开全文
  • 前序遍历: PreOrder = T_Root + PreOrder(T的左子树)+ PreOrder(T的右子树) ...后序遍历: PostOrder = PostOrder(T的左子树)+ PostOrder(T的右子树)+ T_Root 【dfs】后序遍历 HihoCoder -...

    前序遍历: PreOrder = T_Root + PreOrder(T的左子树)+ PreOrder(T的右子树)
    中序遍历: InOrder = InOrder(T的左子树)+ T_Root + InOrder(T的右子树)
    后序遍历: PostOrder = PostOrder(T的左子树)+ PostOrder(T的右子树)+ T_Root

    【dfs】后序遍历 HihoCoder - 1049 【已知前序和中序遍历,求后序遍历】

    时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB

    描述
    在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树!

    小Ho对这棵二叉树爱不释手,于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母,并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会,重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样,日子安稳的过了两天。

    这天,小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果,但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上,小球和木棍等零件散落了一地!

    小Ho损失了心爱的玩具,正要嚎啕大哭起来,所幸被小Hi发现了,劝说道:“别着急,这不是零件都还在么?拼起来不就是了?”

    “可是我忘记了二叉树长什么样子了!”小Ho沮丧道。

    “这个简单,你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么,利用这两个信息就可以还原出整棵二叉树来哦!”

    “这样么?!!”小Ho止住了泪水,问道:“那要怎么做呢?”

    没错!小Ho在这一周遇到的问题便是:给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。

    提示:分而治之——化大为小,化小为无

    “这可就要从头说起了,我们先找一棵二叉树作为例子吧!”小Hi在纸上画了画,递给了小Ho。
    这里写图片描述

    “不妨假设你的二叉树长成这个样子~”小Hi道。

    “可是我的二叉树并不是长成这个样子啊!虽然我读书少,但是你不要骗我好不好!”小Ho一脸气愤道。

    “我都说了是假设!是为了能让你明白如何通用的去解决这样的问题!”小Hi无奈道。

    “好吧……你接着说。”小Ho算是认可了这个说法。

    “那么对于这棵二叉树,你先来计算一下它的前序遍历和中序遍历的结果吧!”小Hi也是毫不含糊就开始下发任务。

    “唔……前序遍历是ABDEGHCFIJ,中序遍历……我想想啊……是DBGEHACIJF!”小Ho并没有花费多长时间就给出了答案。

    “你还记得前序遍历的递归定义么?”小Hi点了点头又继续问道。

    “是‘根节点’+‘左子树的前序遍历’+‘右子树的前序遍历’!”小Ho毫不犹豫的答道:“而在这里体现出来就是‘A’+‘BDEGH’+‘CFIJ’”。

    “那中序遍历呢?”小Hi继续问道。

    “是‘左子树的中序遍历’+‘根节点’+‘右子树的中序遍历’!在这里也就是‘DBGEH’+‘A’+‘CIJF’。”小Ho这次花的时间更少了。

    “还记得动态规划时候我们一般处理的方法么?我们这里也可以这样做哦,如果我们定义post_order(str1, str2)为一棵前序遍历的结果为str1,中序遍历的结果为str2的二叉树的后序遍历的结果的话,我们有没有办法把它化解成为子问题呢?”小Hi道。

    “让我想想……”小Ho拿出纸笔开始演算起来:“如果我要求解post-order(str1, str2)的话,首先不难发现,根据‘前序遍历’str1=‘根节点’+‘左子树的前序遍历’+‘右子树的前序遍历’,我可以知道这棵二叉树的根节点root便是str1的第一个字符!”小Ho道。

    “而我在知道了‘根节点’root之后,我便可以利用‘中序遍历’str2=‘左子树的中序遍历’+‘根节点’+‘右子树的中序遍历’,求解出‘左子树的中序遍历’str2L和‘右子树的中序遍历’str2R!”

    “接下来,由于一棵子树的前序遍历和中序遍历的长度相同,那么仍然是根据‘前序遍历’str1=‘根节点’+‘左子树的前序遍历’+‘右子树的前序遍历’,我可以知道从str1的第2个字符开始的str2L.length()个字符便是‘左子树的前序遍历’str1L,而这之后的部分便是‘右子树的前序遍历’str1R!”小Ho说到这里,顿了顿,希望从小Hi处得到些反馈。

    “没错!那你准备如何求解post_order(str1, str2)呢?”小Hi肯定道。

    “这只要根据之前求出的结果,和‘后序遍历’=‘左子树的后序遍历’+‘右子树的后序遍历’+‘根节点’,便可以知道——post_order(str1, str2)=post_order(str1l,str2l)+post_order(str1r, str2r)+root这样一个式子来!而这个问题的规模——也就是二叉树的大小,是一直在缩小的,所以是能够这样不断的划分做下去的!也就是说我之后可以将当前根节点的左子树又拆分成为两个问题来解决,一直到当前节点是叶子节点了为止!然后慢慢的将这些答案拼成上层的问题的答案,而这个过程只需要使用递归完成就可以了!

    “听起来很容易的样子呢!那你要不要赶紧去实现了算法,算出你的宝贝二叉树长什么样呢?”小Hi满意的点了点头,随即笑着问道。

    “那是自然!”

    输入
    每个测试点(输入文件)有且仅有一组测试数据。

    每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历的结果。

    每组测试数据的第二行为一个由大写英文字母组成的字符串,表示该二叉树的中序遍历的结果。

    对于100%的数据,满足二叉树的节点数小于等于26。

    输出
    对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果。

    样例输入
    AB
    BA

    样例输出
    BA

    思路:
    题目介绍的很清楚了,也就是前序遍历的第一个字符就是根,在中序遍历中找到它,就知道其左边是左子树的中序遍历,右边是右子树的中序遍历,然后左右子树的大小也知道了,就可以在前序遍历的第二个字符开始找到左子树的前序遍历和右子树的前序遍历,那么就可以找到二叉树了。

    AC代码:

    #include <iostream>
    #include <stdio.h>
    #include <math.h>
    #include <algorithm>
    #include <cstring>
    #include <string>
    
    using namespace std;
    
    void post_order(string s1, string s2)
    {
        if(s1.length() == 1)
        {
            printf("%c", s1[0]);
            return ;
        }
        else if(s1.length() == 0)
            return ;
        char root = s1[0];
        int pos = 0;
        while(s2[pos] != root)
            pos++;
        string s1l, s2l, s1r, s2r;
        s2l = s2.substr(0, pos);
        s2r = s2.substr(pos + 1);
        s1l = s1.substr(1, pos);
        s1r = s1.substr(pos + 1);
        post_order(s1l, s2l);
        post_order(s1r, s2r);
        printf("%c", root);
    }
    
    
    int main()
    {
        string str1, str2;
        while(cin>>str1>>str2)
        {
            post_order(str1, str2);
            printf("\n");
        }
        return 0;
    }
    
    展开全文
  • 二叉树的基本操作,例如前序遍历,中序遍历,后序遍历及层序遍历
  • 后序遍历

    2016-08-04 18:31:00
    后序遍历 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具——一棵由小球和...

    后序遍历

    时间限制:10000ms
    单点时限:1000ms
    内存限制:256MB

    描述

    在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具——一棵由小球和木棍连接起来的二叉树

    小Ho对这棵二叉树爱不释手,于是给它的每一个节点都标记了一个标号——一个属于A..Z的大写字母,并且没有任意两个节点的标号是一样的。小Hi也瞅准了这个机会,重新巩固了一下小Ho关于二叉树遍历的基础知识~就这样,日子安稳的过了两天。

    这天,小Ho正好在求解这棵二叉树的前序、中序和后序遍历的结果,但是却在求出前序遍历和中序遍历之后不小心把二叉树摔到了地上,小球和木棍等零件散落了一地!

    小Ho损失了心爱的玩具,正要嚎啕大哭起来,所幸被小Hi发现了,劝说道:“别着急,这不是零件都还在么?拼起来不就是了?”

    “可是我忘记了二叉树长什么样子了!”小Ho沮丧道。

    “这个简单,你不是刚刚求出了这棵二叉树的前序和中序遍历的结果么,利用这两个信息就可以还原出整棵二叉树来哦!”

    “这样么?!!”小Ho止住了泪水,问道:“那要怎么做呢?”

    没错!小Ho在这一周遇到的问题便是:给出一棵二叉树的前序和中序遍历的结果,还原这棵二叉树并输出其后序遍历的结果。

    提示:分而治之——化大为小,化小为无

    输入

    每个测试点(输入文件)有且仅有一组测试数据。

    每组测试数据的第一行为一个由大写英文字母组成的字符串,表示该二叉树的前序遍历的结果。

    每组测试数据的第二行为一个由大写英文字母组成的字符串,表示该二叉树的中序遍历的结果。

    对于100%的数据,满足二叉树的节点数小于等于26。

    输出

    对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果。

    样例输入
    AB
    BA
    样例输出
       BA
    分析:前序遍历的第一个字符是根,根据这个根可以将中序遍历的左子树,右子树找出来,    根据这些长度又可以把前序遍历左子树,右子树找出来,接下来继续递归就好了; 代码:
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <climits>
    #include <cstring>
    #include <string>
    #include <set>
    #include <map>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <list>
    #define rep(i,m,n) for(i=m;i<=n;i++)
    #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
    #define vi vector<int>
    #define pii pair<int,int>
    #define mod 1000000007
    #define inf 0x3f3f3f3f
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    #define ll long long
    #define pi acos(-1.0)
    const int maxn=1e5+10;
    const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
    using namespace std;
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
    int n,m;
    string a,b;
    string dfs(string p,string q)
    {
        int i,len=p.length();
        if(len<=2){reverse(p.begin(),p.end());return p;}
        string c,d,e,f;
        for(i=0;q[i]!=p[0];i++);
        d=q.substr(0,i),f=q.substr(i+1,len-i-1);
        c=p.substr(1,i),e=p.substr(i+1,len-i-1);
        return dfs(c,d)+dfs(e,f)+p[0];
    }
    int main()
    {
        int i,j,k,t;
        cin>>a>>b;
        cout<<dfs(a,b)<<endl;
        //system ("pause");
        return 0;
    }

     

    转载于:https://www.cnblogs.com/dyzll/p/5737867.html

    展开全文
  • 这三也是经典的二叉树的三种方法 二叉树的前序遍历 前序遍历就不写了,很简单,和深度优先一样,我不知道别人有用什么奇怪方法的,但是我用栈来实现深度优先,可以参考二叉树广度优先...二叉树的后序遍历 ...

    这三也是经典的二叉树的三种方法

    二叉树的前序遍历

    递归实现

    public class Main4 {
    	static ArrayList<TreeNode> list = new ArrayList<TreeNode>();
    	int QianXu(TreeNode t) {
    	//根,判定第一个节点(根)是否存在
    		if(t==null) {
    			return 0;
    		}	
    		list.add(t);
    		//左
    		if(t.left!=null) {			
    			HouXu(t.left);	
    		}	
    		//右
    		if(t.right!=null) {		
    			HouXu(t.right);
    		}
    		
    		return 0;
    		
    	}
    	
    	public static void main(String[] args) {
    
    		TreeNode tn1= new TreeNode(1);
    		TreeNode tn2= new TreeNode(2);
    		TreeNode tn3= new TreeNode(3);
    		TreeNode tn4= new TreeNode(4);
    		TreeNode tn5= new TreeNode(5);
    		TreeNode tn6= new TreeNode(6);
    		TreeNode tn7= new TreeNode(7);
    		tn1.left=tn2;
    		tn1.right=tn3;
    		tn2.left=tn4;
    		tn2.right=tn5;
    		tn3.left=tn6;
    		tn3.right=tn7;
    		new Main4().QianXu(tn1);
    		for(int i =0;i<list.size();i++) {
    			System.out.print(list.get(i).val);
    		}
    		
    	
    	}
    }
    

    这个没什么难理解的,顺序就是根,左,右节点,如果有左右节点就遍历,没有就不往左节点或右节点遍历了

    非递归实现

    前序遍历的非递归实现就不写了,很简单,和深度优先一样,我不知道别人有用什么奇怪方法的,但是我用栈来实现深度优先,可以参考二叉树广度优先搜索和深度优先搜索

    二叉树的中序遍历

    1、使用递归的方式实现

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
     }
    public class Main3 {
    	static ArrayList<TreeNode> list = new ArrayList<TreeNode>();
    	int ZhongXuBianLi(TreeNode tn) {
    		if(t==null) {  //判定第一个节点(根)是否存在
    			return 0;
    		}	
    		//左
    		if(tn.left!=null) {
    			ZhongXuBianLi(tn.left);
    		}	
    		//根
    		list.add(tn);
    		//右
    		if(tn.right!=null) {
    			ZhongXuBianLi(tn.right);		
    		}	
    		return 0;
    	}	
    	public static void main(String[] args) {
    		TreeNode tn1= new TreeNode(1);
    		TreeNode tn2= new TreeNode(2);
    		TreeNode tn3= new TreeNode(3);
    		TreeNode tn4= new TreeNode(4);
    		TreeNode tn5= new TreeNode(5);
    		TreeNode tn6= new TreeNode(6);
    		TreeNode tn7= new TreeNode(7);
    		tn1.left=tn2;
    		tn1.right=tn3;
    		tn2.left=tn4;
    		tn2.right=tn5;
    		tn3.left=tn6;
    		tn3.right=tn7;
    		new Main3().ZhongXuBianLi(tn1);
    		for(int i =0;i<list.size();i++) {
    			System.out.print(list.get(i).val);
    		}
    		
    	}
    }
    
    

    结果:
    在这里插入图片描述
    使用的例子示例图
    在这里插入图片描述
    分析这个可能有点眼花缭乱,那就先看小的部分
    在这里插入图片描述
    这个怎么能成中序遍历呢?
    肯定是213吧,那是不是先把2节点放进去,再把1节点放进去,再把三节点放进去呢!肯定的
    那给的节点肯定是1节点了,那访问的顺序肯定就是先从1到2,再经过1到3。
    而这个顺序正好有一个中序遍历的顺序,那就是213,所以就从2节点开始放,那怎么知道到2了呢?
    那就找左子树是null的节点就行,添加完2肯定就是返回,返回到根节点添加1,再通过右子树为null找到3,添加进去,就完成了。
    再经过递归就可以成大的了、

    2、使用非递归的方式实现(使用栈)

    TreeNode是二叉树的节点,上个程序有,这就不添加上了

    	//非递归
    	int ZhongXuBianLi1(TreeNode tn) {
    		//根不存在
    		if(tn==null) {
    			return 0;
    		}	
    		Stack<TreeNode> stack = new Stack<TreeNode>();	
    		stack.add(tn);
    		//isEmpty只有当size==0时才返回true
    		while(stack.isEmpty()==false) {		 //第一步
    			if(tn!=null) {						//第二步
    				stack.add(tn);
    				tn = tn.left;			
    			}else {									//第三步
    				tn = stack.pop();
    				list.add(tn);			
    				if(stack.isEmpty()==false) {			//第四步
    					tn = stack.pop();
    					list.add(tn);				
    				}
    				tn = tn.right;			
    			}			
    		}		
    		return 0;
    		}	
    	public static void main(String[] args) {
    		TreeNode tn1= new TreeNode(1);
    		TreeNode tn2= new TreeNode(2);
    		TreeNode tn3= new TreeNode(3);
    		TreeNode tn4= new TreeNode(4);
    		TreeNode tn5= new TreeNode(5);
    		TreeNode tn6= new TreeNode(6);
    		TreeNode tn7= new TreeNode(7);
    		tn1.left=tn2;
    		tn1.right=tn3;
    		tn2.left=tn4;
    		tn2.right=tn5;
    		tn3.left=tn6;
    		tn3.right=tn7;
    		new Main3().ZhongXuBianLi1(tn1);
    		for(int i =0;i<list.size();i++) {
    			System.out.print(list.get(i).val);
    		}
    		
    	}
    

    这个的例子也是用的
    在这里插入图片描述
    因为不是用递归实现,所以就需要用while或者for来代替递归了,说实话递归的确好理解

    一步一步的来分析分析怎么用栈来解决的,用栈怎么实现的。
    首先看一张图
    在这里插入图片描述
    不知道你能不能看懂,一开始我也看不懂,经过自己写这个过程就会了,
    这些不同颜色的实线箭头 就是进栈的顺序(这些箭头是不可以打断的,比如1,2,4必须进栈是1、2、4,不能在4之前插入一个)
    当然出栈的没写,根据入栈的顺序,和中序遍历的顺序结合,其实就能写出 出栈的顺序。

    按这个思路,首先你需要while循环一下把1、2、4都添加进去吧,之后出4,2,再把5进栈
    之后5,1出栈,3、6进栈,再3、6出栈,7入栈,再7出栈,就构成了中序遍历
    在这里插入图片描述
    上面的思路好理解,但是实现有点困难,看程序,
    1、首先解决的是while的判定条件,因为这个过程中栈空代表着么有没有节点了,所以结束了,
    2、之后是怎么一口气把像1、2、4这样的节点入栈
    3、什么情况下开始出栈,出栈几个(要考虑到有可能连着的父节点,祖父节点等没有右节点),
    4、考虑到出栈到根节点的情况
    上面的4个正好对应程序中关键的四步

    二叉树的后序遍历

    递归实现

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
     }
    public class Main4 {
    	static ArrayList<TreeNode> list = new ArrayList<TreeNode>();
    	int HouXu(TreeNode t) {
    		if(t==null) {  //判定第一个节点(根)是否存在
    			return 0;
    		}	
    		//左
    		if(t.left!=null) {			
    			HouXu(t.left);	
    		}		
    		//右
    		if(t.right!=null) {		
    			HouXu(t.right);
    		}
    		list.add(t);	
    		return 0;
    		
    	}
    	
    	public static void main(String[] args) {
    
    		TreeNode tn1= new TreeNode(1);
    		TreeNode tn2= new TreeNode(2);
    		TreeNode tn3= new TreeNode(3);
    		TreeNode tn4= new TreeNode(4);
    		TreeNode tn5= new TreeNode(5);
    		TreeNode tn6= new TreeNode(6);
    		TreeNode tn7= new TreeNode(7);
    		tn1.left=tn2;
    		tn1.right=tn3;
    		tn2.left=tn4;
    		tn2.right=tn5;
    		tn3.left=tn6;
    		tn3.right=tn7;
    		new Main4().HouXu(tn1);
    		for(int i =0;i<list.size();i++) {
    			System.out.print(list.get(i).val);
    		}
    		
    	
    	}
    }
    

    非递归实现

    用两个栈来实现,当压入第一个栈是1,取出来把它左右都压进栈,再把1压入另一个栈,这样循环下去,第二个栈的出栈顺序就是后续遍历

    int HouXu1(TreeNode t) {
    		if(t==null) {
    			return 0;
    		}
    		Stack<TreeNode> stack1=new Stack<TreeNode>();
    		Stack<TreeNode> stack2=new Stack<TreeNode>();
    		stack1.add(t);
    		while(!stack1.isEmpty()) {
    			t =stack1.pop();
    			if(t.left!=null) {
    				stack1.add(t.left);
    			}
    			if(t.right!=null) {
    				stack1.add(t.right);
    			}
    			stack2.add(t);
    		}
    		while(!stack2.isEmpty()) {
    			list.add(stack2.pop());
    		}
    		return 0;
    	}
    	
    	public static void main(String[] args) {
    
    		TreeNode tn1= new TreeNode(1);
    		TreeNode tn2= new TreeNode(2);
    		TreeNode tn3= new TreeNode(3);
    		TreeNode tn4= new TreeNode(4);
    		TreeNode tn5= new TreeNode(5);
    		TreeNode tn6= new TreeNode(6);
    		TreeNode tn7= new TreeNode(7);
    		tn1.left=tn2;
    		tn1.right=tn3;
    		tn2.left=tn4;
    		tn2.right=tn5;
    		tn3.left=tn6;
    		tn3.right=tn7;
    		new Main4().HouXu1(tn1);
    		for(int i =0;i<list.size();i++) {
    			System.out.print(list.get(i).val);
    		}
    		
    	
    	}
    

    分析分析这三种遍历中递归的区别(非递归联系不是很大)

    自己整理完这三种遍历的算法,感觉也就那样,尤其是递归的,更没什么

    		if(t==null) {		//这个必须排第一个
    			return 0;
    		}								
    		list.add(t);		//第一部分
    		//左
    		if(t.left!=null) {			//第二部分
    			HouXu(t.left);	
    		}	
    		//右
    		if(t.right!=null) {		 //第三部分
    			HouXu(t.right);
    		}
    		return 0;
    

    前序遍历、中序遍历、后序遍历也就是上面三部分根据前面序列的规则排序而已。
    举个例子:
    前序要求根节点,左节点,右节点。那上面排序的规则就是第一部分(根)、第二部分(左)、第三部分(右)

    很简单。看别人千万遍不如自己写一遍,总结一遍啊。

    展开全文
  • DLR--先序遍历(根在前,从左往右,一棵树的根永远在左子树前面,左子树又永远...LRD--后序遍历(根在后,从左往右,一棵树的左子树永远在右子树前面,右子树永远在根前面) 左-右-根(从下往上,一层一层) ...
  • 二叉树简介 ...二叉树的遍历有4种方式,先序遍历,中序遍历,后序遍历,层次遍历,前三者均属于深度优先遍历,先序、中序、后序指的是遍历时根节点相对于左右孩子的次序,先序遍历的顺序为根节点->左子树->
  • 问题描述  给定一棵二叉树的前序... 应输出的后序遍历序列为ACBMXZPD 输入格式  两行两个大写字母字符串,分别代表前序和中序遍历 输入格式  一行表示后序遍历 样例输入 DBACPMZX ABCDMPXZ 样例输出 .
  • 前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal) 1. 前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal) 遍历的...
  • #1049后序遍历

    2017-12-07 19:39:28
    题目:hihocoder #1049 输入每个测试点(输入文件)有且仅有一组测试数据。每组测试数据的第一行为一个由大写英文...输出对于每组测试数据,输出一个由大写英文字母组成的字符串,表示还原出的二叉树的后序遍历的结果
  • 出题:输入一个整数数组,判断该数组是否符合一个二元查找树的后序遍历(给定整数数组,判定其是否满足某二元查找树的后序遍历); 分析:利用后序遍历对应到二元查找树的性质(序列最后一个元素必定是根节点,从...
  • 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的数据决定是否产生该结点从而实现创建该二叉树的...
  • 输出利用先序遍历创建的二叉树的后序遍历序列 利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据接收的...
  • 输出利用先序遍历创建的二叉树的后序遍历序列(0979)利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对二叉树结点的抽象访问具体化为根据...
  • 关于二叉树的问题1-已知前序,中序求后序遍历 对于一棵二叉树而言,可以由其前序和中序或者中序和后序的遍历序列,确定一棵二叉树。 那么对于已知前序和中序序列,求后序序列也就是先还原二叉树,然后对...
  • #1049 : 后序遍历 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具...
  • 给出一棵二叉树,分别输出先序、中序、后序遍历结果。 输入 第一行:结点数n(1 以下n行,每行3个整数,分别表示父结点、左孩子、右孩子。若没有孩子,对应的整数为0. 输出 第1行:树根 第2行:先序遍历结果,...
  • 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 中序遍历 inorder =[9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 2、代码详解 相同题:105. 从前序与中序遍历序列...
  • 输出利用先序遍历创建的二叉树的后序遍历序列 1000(ms) 10000(kb) 2473 / 3692利用先序递归遍历算法创建二叉树并输出该二叉树的后序遍历序列。先序递归遍历建立二叉树的方法为:按照先序递归遍历的思想将对...
  • hihocoder 1049 后序遍历

    2016-09-04 14:06:57
    #1049 : 后序遍历 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具...
  • #1049 : 后序遍历

    2016-04-03 15:01:39
    #1049 : 后序遍历 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 在参与过了美食节之后,小Hi和小Ho在别的地方又玩耍了一阵子,在这个过程中,小Ho得到了一个非常有意思的玩具...
  • 前序遍历中序遍历后序遍历

    千次阅读 2019-07-02 22:32:33
  • 二叉树的后序遍历题目描述代码实现 题目描述 代码实现 左子树—右子树—根节点 class Solution { public: void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; traversal...
  • 二叉树前序遍历规则是:根、左子树、右子树;中序遍历规则是:左子树、根、右子树;后序遍历规则是:左子树、右子树、根。
  • 也就在大二学数据结构的时候知道了树的前序遍历、后序遍历、中序遍历。之后就忘了,在之后就是大四研究生老师考我,我当时还不知道,真够丢人的。自此之后,知道了如何通过其中两个得到第三个,但是也没有编程实现过...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,326
精华内容 1,730
关键字:

后序遍历英文