精华内容
下载资源
问答
  • Q:已知二叉树的先序和中序遍历,求后序遍历= = 分析:先举个栗子,比如我们知道某二叉树的先序遍历和后序遍历分别为 DBACEGF ABCDEFG,辣么如果要求后序遍历的话,应该现在先序遍历中找出二叉树的根节点(也就是...

    Q:已知二叉树的先序和中序遍历,求后序遍历= =

    分析:先举个栗子,比如我们知道某二叉树的先序遍历和后序遍历分别为  DBACEGF ABCDEFG,辣么如果要求后序遍历的话,应该现在先序遍历中找出二叉树的根节点(也就是先序中的第一个值D),然后在去中序遍历中找到根节点,那么就很明确的知道中序中,根节点的左边为左子树,右边为右子树,然后找出左子树的后序遍历和右子树的后序遍历,最终拼接在一起就OK了= =

    参考代码:

    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<iostream>
    
    using namespace std;
    const int maxn = 1000+10;
    char pre[maxn],in[maxn];
    char post[maxn];//结果串
    int cur;
    
    void topost( char pre[], char in[],char post[], int l)
    {
        if( l <= 0)
            return;
        int i;
        for( i = 0; i < l; i++)
            if( in[i] == pre[0])//先序遍历的第1个点(根节点) 与 中序遍历第i+1个点的值相等
                break;
        //所得的i为根节点在中序遍历中的位置 同时也为后序遍历中的最后一个
        post[l-1] = pre[0];
        topost( pre+1,in,post,i);//左子树后序遍历的转化
        topost( pre+1+i,in+i+1,post+i,l-1-i);
    }
    
    int main()
    {
        while( ~scanf("%s%s",pre,in))//输入先序 和中序遍历
        {
            //printf("%s %s\n",str1,str2);
            int len =  strlen(pre);//计算计算二叉树结点数
            topost( pre,in,post,len);//转化后序遍历
            for( int i = 0; i < len; i++)//输出后序遍历
                putchar(post[i]);
            putchar(10);
        }
    
        return 0;
    }
    


    展开全文
  • #include #include typedef struct node { int value; struct node *left;... *根据二叉树的先序遍历和中序遍历,还原二叉树 *先序:1,2,4,7,3,5,6,8;中序:4,7,2,1,5,3,8,6 */ pNode BuildTree(int p
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node
    {
    	int value;
    	struct node *left;
    	struct node *right;
    }Node,*pNode;
    
    /*
     *根据二叉树的先序遍历和中序遍历,还原二叉树
     *先序:1,2,4,7,3,5,6,8;中序:4,7,2,1,5,3,8,6
    */
    
    pNode BuildTree(int pre[],int mid[],int len)
    {
    	if(len<=0)
    	{
    		return NULL;
    	}
    	pNode root=(pNode)malloc(sizeof(Node));
    	root->value=pre[0];                    //先序的第一个节点一定是根节点
    	int left_len=0;
    	int right_len=0;
    	int root_value=pre[0];
    	int i=0;
    	while(mid[i]!=root_value)              //获取左子树长度
    	{
    		i++;
    		left_len++;
    	}
    	right_len=len-left_len-1;              //获取右子树长度
    	//printf("left_len is %d\n",left_len);
    	//printf("right_len is %d\n",right_len);
    	root->left=BuildTree(pre+1,mid,left_len);     //递归还原左子树
    	root->right=BuildTree(pre+1+left_len,mid+1+left_len,right_len);  //递归还原右子树
    	return root;
    }

    展开全文
  • 如何分割先序和后序方法可以看我输出后序遍历那篇博客,这里只谈谈分割后怎么递归能得到层次遍历的方法。 当然方法有很多,我这里提供一种暴力一点,通用一点方法。 我给这种方法起了个名字叫标签绑定法。 所谓...

    写一下我的一个思路,coding就不贴了。

    如何分割先序和后序的方法可以看我输出后序遍历那篇博客,这里只谈谈分割后怎么递归能得到层次遍历的方法。

    当然方法有很多,我这里提供一种暴力一点,通用一点的方法。

    我给这种方法起了个名字叫标签绑定法。

    所谓标签绑定,就是我在把元素添加到result列表的时候,不是直接添加元素,而是添加一个二元列表(或者二元组),如[level,元素],每次递归level加一,要注意level放在前面方便排序。

    最后只要把result排个序,然后用列表生成。

    result = [y for [x, y] in result]

    就能得到想要的结果。

    这种方法应用性很广,对于那些自己定义的类型,放到二元组里怎么排序呢?

    只需要在类里添加def lt(self, other): def gt(self, other):,告诉python你打算怎么比较这个类与其他元素(包括其他类型的元素)比较大小即可直接使用现有的sort方法。

    如果有其他的方法,欢迎在评论区留言以供交流。

    展开全文
  • 先序序列和中序序列可以唯一确定一棵二叉树,算法实现步骤如下: 1)根据先序序列确定树的根结点 2)根据根结点在中序序列中的位置划分出二叉树的左右子树包含哪些结点。 然后根据左、右字数结点在先序序列中...

        新手,摸索着前进.......

    由先序序列和中序序列可以唯一确定一棵二叉树,算法实现步骤如下:

    1)根据先序序列确定树的根结点

    2)根据根结点在中序序列中的位置划分出二叉树的左右子树包含哪些结点。

        然后根据左、右字数结点在先序序列中的次序可以确定子树的根结点,即回到步骤 1)。

    如此重复上述步骤,直到每棵子树仅有一个结点(该子树的根结点)为止。

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define OVERFLOW 0
    typedef struct Node
    {
        char data;
        struct Node *lchild,*rchild;
        //Node(){data = 0;lchild = rchild = NULL;}
    }Node,*BiTree;
    
    char PreString[30],InString[30];//先序和中序遍历字符串
    
    BiTree Build(char *PreString,char *InString,int s1,int e1,int s2,int e2)
    {
    //    BiTree T = (BiTree)malloc(sizeof(Node));
    //    if(T == NULL)
    //    {
    //        exit(OVERFLOW);
    //    }
        BiTree T = new Node();
        T -> data = PreString[s1];
        int rootIdx;//根结点所在序号
        for(int i = s2;i <= e2;i++)
        {
            if(PreString[s1] == InString[i])
            {
                rootIdx = i;
                break;
            }
        }
        int llen = rootIdx - s2;
        int rlen = e2 - rootIdx;
        if(llen != 0)
        {
            T -> lchild = new Node();
            T -> lchild = Build(PreString,InString,s1 + 1,s1 + llen,s2,s2 + llen - 1);
        }
        else
            T -> lchild = NULL;
        if(rlen != 0)
        {
            T -> rchild = new Node();
            T -> rchild = Build(PreString,InString,e1 - rlen + 1,e1,e2 - rlen + 1,e2);
        }
        else
        {
            T -> rchild = NULL;
        }
        return T;
    }
    
    void PostOrder(BiTree T)//后序遍历
    {
        if(T != NULL)
        {
            PostOrder(T -> lchild);
            PostOrder(T -> rchild);
            printf("%c",T -> data);
        }
    }
    
    int main()
    {
        printf("请输入先序遍历字符串:");
        scanf("%s",PreString);
        printf("请输入中序遍历字符串:");
        scanf("%s",InString);
        BiTree T = NULL;
        T = Build(PreString,InString,0,strlen(PreString)-1,0,strlen(InString)-1);
        printf("此二叉树的后序遍历为:");
        PostOrder(T);
        printf("\n");
        return 0;
    }
    

    展开全文
  • 根据二叉树先序遍历和中序遍历构建二叉树

    万次阅读 多人点赞 2019-04-24 21:20:37
    对于本题,根据二叉树先序遍历和中序遍历构建二叉树,思路: 我们可以求得根节点左子树的先序和中序序列,以及右子树的先序和中序序列 此问题变成了根据左子树的先序和序列构建左子树的二叉树,根据右子树的先序和...
  • 该文对剑指Offer的第四题根据二叉树的先序和中序遍历构造二叉树 题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历...
  • 重建二叉树
  • 问题:根据二叉树的先序和中序构建二叉树 思路:每次根据先序和中序顺序确定根节点和相应的左右子树,再分别对左右子树进行递归确定 程序实现: #include &lt;iostream&gt; using namespace std; ...
  • 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果,输出该树的先序遍历结果。 输入格式: 第一行给出正整数N(≤30),是树中结点的个数。随后两行,每行给出N个整数,分别对应后序遍历和中序遍历结果,数字间以...
  • 在知道先序和中序遍历的原理之后,我们便可以反推出一颗树。思路: 1)先序遍历的第一位即是二叉树的根节点。 2)然后再中序遍历找到根结点,根节点左边的所有序列便是左子树的中序遍历结果,右边的所有序列便是右...
  • 对于二叉树的先序遍历和中序遍历,由于在先序遍历中第一个访问的总是根节点,因此可以根据先序遍历中的第一个元素,将中序遍历看成是**“左子树中序遍历+根节点+右子树中序遍历”**,根据左右子树中序遍历的节点个数...
  • 先序和中序遍历序列来确定一棵二叉树 【分析】 ◆根据先序遍历序列第一个结点确定根结点; ◆根据根结点在中序遍历序列中分割出左右两个子序列 ◆对左子树和右子树分别递归使用相同方法继续分解。 ...
  • poj2255根据任意二叉树的先序遍历和中序遍历求解后序遍历
  • 首先我们要明白先中后序遍历特点: 先序遍历中 第一个一定是根结点。 中序遍历中 根结点左子树...根据先序遍历和中序遍历构建二叉树 解题细想: 设置变量inedx 方便从preorder数组中获取元素构建结点。 判断i...
  • 根据二叉树的先序和中序序列画出二叉树的方法

    万次阅读 多人点赞 2018-04-03 18:54:21
    已知二叉树的先序和中序序列如下: 先序序列:1 2 4 6 3 5 7 8 中序序列:2 6 4 1 7 5 8 3 请画出该二叉树。 答: 先序序列的遍历顺序是先根节点,后左孩子,最后右孩子 中序序列的遍历顺序是先左孩子,后根...
  • 根据二叉树的后序和中序遍历序列,用递归的方法创建出这棵树,然后用的自定义栈的先序和层次方法遍历。 输入: 7 2 3 1 5 7 6 4 1 ...
  • 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并...
  • 学过数据结构应该都知道,根据先序遍历和中序遍历可以唯一确定一颗二叉树二叉树是递归定义数据结构,所以一般操作都是递归完成,所以建树过程也不例外,先来看这样两道题 题目一 :...
  • 根据二叉树先序遍历和中序遍历的特点,采用递归的方法求解。 程序1(通过根节点的位置判断树的左右子树是否为空)://已知二叉树的中序和先序遍历,求二叉树的后续遍历 #include #include #include typedef struct ...
  • 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}, 则重建二叉树...
  • 给定一颗二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度,同时对该二叉树进行层序遍历并输出。 1.分析: 根据定义,二叉树的先序遍历是先访问根结点,其次,再按先序遍历方式遍历根结点的左子树,...
  • 中序和后序三种方式,并且根据遍历序列能确定一棵二叉树,要唯一确定一棵二叉树至少需要两种遍历序列 先序+中序 或 后序+中序,(先序+后序无法唯一确定) 现在给定你一棵二叉树的先序和中序序列,请你构造出这棵...
  • 假设输入的先序和中序遍历结果中不含重复数字。例如:输入先序遍历{1,2,4,7,3,5,6,8}和中序遍历{4,7,2,1,5,3,8,6},则重建出二叉树并输出它的头结点。分析:先序遍历的第一个结点就是二叉树的根结点,然后到中序遍历...
  • 通过输入先序和中序序列字符串,构建二叉树
  • 根据二叉树的先序遍历和中序遍历构造二叉树是非常经典的一道算法题目,但是在网上找到的资料绝大多数都是使用链接方式构造二叉树,感觉这样比较繁琐,因此自己写了一个数组实现的程序,当然,程序不算很完善,还望...
  • 题目:假设输入前序遍历和中序遍历的结果中都不含重复数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。牛客网剑指offer4 该题大题思路如下 通过图我们...
  • 二叉树先序遍历结果为aferpkwhjl, 中序遍历结果为repfwkajhl,那么后序遍历结果是什么呢? 先序遍历顺序是:根 -左子树 -右子树 中序遍历的顺序是:左子树 -根 -右子树 后序遍历顺序是:左子树 -右子树 -根 ...
  • 给定一个二叉树的前序遍历和中序遍历的序列,输出对应这个二叉树的后续遍历序列。 输入描述: 输入为一行。 两个字符串,分别表示二叉树的前序遍历和中序遍历结果,用空格分隔。保证数据合法 输出描述: 对应输出...

空空如也

空空如也

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

根据二叉树的先序和中序遍历