精华内容
下载资源
问答
  • 已知前序和中序求后序

    千次阅读 2019-05-19 21:27:12
    1 public TreeNode createTree(String preOrder,String inOrder) { if(preOrder.isEmpty()) { return null; } char rootValue = preOrder.charAt(0);... int rootIndex = inOrder.indexOf(rootValue);...

    1

    public TreeNode createTree(String preOrder,String inOrder)
    {
    	if(preOrder.isEmpty())
    	{
    		return null;
    	}
    	
    	char rootValue = preOrder.charAt(0);
    	int rootIndex = inOrder.indexOf(rootValue);
    	
    	TreeNode root = new TreeNode(rootValue);
    	
    	root.setLeft(
    		createTree(
    			preOrder.substring(1,1+rootIndex),
    			inOrder.substring(0,rootIndex)
    		)
    	);
    	
    	root.setRight(
    		createTree(
    			preOrder.substring(1+rootIndex),
    			inOrder.substring(1+rootIndex)
    		)
    	);
    	
    	return root;
    }
    

    2

    public String postOrder(String preOrder , String inOrder)
    {
    	if(preOrder.isEmpty())
    	{
    		return "";
    	}
    	
    	char rootValue = preOrder.charAt(0);
    	int rootIndex = inOrder.indexOf(rootValue);
    	
    	return preOrder(
    		preOrder.substring(1,1+rootIndex),
    		inOrder.substring(0,rootIndex)
    	)+preOrder(
    		preOrder.substring(1+rootIndex),
    		inOrder.substring(1+rootIndex)
    	)+rootValue;
    	
    }
    
    
    
    展开全文
  • 二叉树已知前序和中序求后序序列(C语言)题目大体思路代码 题目 已知二叉树前序为 ABDFGCEH 后序序列为 BFDGACEH ,要求输出后序遍历为 FGDBHECA 大体思路 又先序得出根,先序的根后为左树一部分,我们再在中序序列...

    二叉树已知前序和中序求后序序列(C语言)

    题目

    已知二叉树前序为 ABDFGCEH 后序序列为 BFDGACEH ,要求输出后序遍历为 FGDBHECA

    大体思路

    又先序得出根,先序的根后为左树一部分,我们再在中序序列里找到先序的根,此处之前即为左树(可以画图好好理解下),此处之后为右树。然后就是不断递归即可。

    代码

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define MAX 100
    
    typedef struct Node{
    char data;
    struct Node *Lchild;
    struct Node *Rchild;
    }BiTNode,*Bitree;
    
    void PreTree(Bitree T)  //后序输出树
    {   if(T==NULL) return;
    
         PreTree(T->Lchild);
         PreTree(T->Rchild);
         printf("%c",T->data);
    
    }
    char pre[MAX];
    char mid[MAX];
    
    int MidFind(int left,int right,char MID)  
    {
        for(int i=left;i<=right;i++)
        {
            if(mid[i]==MID) return i;
        }
        return 0;
    }
    
    void Create(int left,int right,int *i,BiTNode **T)  //此题建立树得先将孩子结点赋NULL,因为没有用户输入以确定什么时候把某个具体的结点赋为NULL
    {//这是第一种创建二叉树的写法(二级指针法)
    //这种感觉是把指针送进函数处理
        *T=(Bitree)malloc(sizeof(BiTNode));
        (*T)->data=pre[*i];
        (*T)->Lchild=NULL; 
        (*T)->Rchild=NULL;
        (*i)++;
        int midnumber =  MidFind(left,right,(*T)->data);
        if(midnumber>left)
        {
            Create(left,midnumber-1,i,(&((*T)->Lchild)));
        }
        if(midnumber<right)
        {
            Create(midnumber+1,right,i,(&((*T)->Rchild)));
        }
    
    }
    
    BiTNode* Create2(int left,int right,int *i)
    {//第二中创建方式(注意返回!!!)  
    //这种感觉是把指针让函数处理(自己不进去)
    BiTNode *T;
        T=(Bitree)malloc(sizeof(BiTNode));
        T->data=pre[*i];
        T->Lchild=NULL;
        T->Rchild=NULL;
        (*i)++;
        int midnumber =  MidFind(left,right,T->data);
        if(midnumber>left)
        {
            T->Lchild = Create2(left,midnumber-1,i);
        }
        if(midnumber<right)
        {
            T->Rchild = Create2(midnumber+1,right,i);
        }
        return T;
    
    }
    int main()
    {
        memset(pre,0,MAX);
         memset(mid,0,MAX);
         gets(pre);
         gets(mid);
         int left,right,len,i=0;
         len=strlen(pre);
         left=0;
         right=len-1;
    
         BiTNode *T=(Bitree)malloc(sizeof(BiTNode));   //这里可以不用分配空间,因为在函数里会进行分配
         Create(left,right,&i,&T);
    
         PreTree(T);
         return 0;
    }
    
    
    展开全文
  • 已知前序和中序求后序 前序:ABCDEFGHIJ 中序:CBAEFDIHJG 解题思路: ||逻辑: 1. 前序的第一个结点A是根结点,是后续的最后一个结点 2. 中序 根结点A左侧为左子树(CB)A右侧为右子树(EFDIHJG)...

    一点点都不难~

    已知:前序和中序,求后序
    前序:ABCDEFGHIJ
    中序:CBAEFDIHJG


    解题思路:

         		
    	||逻辑:好好理解这3句话就够了,无非是用前序判断根结点,用中序判断左右子树。So easy!
    
    	 1. 前序:第一个结点A是根结点,是后序的最后一个结点
    	 2. 前序:子树的第一个结点为子树根结点
    	 3. 中序:根据前序的根节点,判断是否有左右子树。
    	 
    	 例如:根结点A,在中序中判断有左右子树,左侧为左子树(CB)A右侧为右子树(EFDIHJG)
    	 左子树CB 在前序中的顺序为BC,所以按性质2,B为子树根结点,性质3,B根结点只有左子树C。
    
    

    解决方案:

    前序:ABCDEFGHIJ
    中序:CBAEFDIHJG
    在这里插入图片描述

    后序:

    后序:CBFEIJHGDA

    展开全文
  • 二叉树已知前序和中序遍历,求后序遍历,C++代码已编译通过,可直接运行
  • 二叉树的遍历(前序中序后序已知中序求后序已知后序求前序) 之前的一篇随笔(二叉树、前序遍历、中序遍历、后序遍历)只对二叉树的遍历进行了笼统的描述,这篇随笔重点对前、中、后序的遍历顺序...

    二叉树的遍历(前序、中序、后序、已知前中序求后序、已知中后序求前序)

     

    之前的一篇随笔(二叉树、前序遍历、中序遍历、后序遍历)只对二叉树的遍历进行了笼统的描述,这篇随笔重点对前、中、后序的遍历顺序进行分析

    二叉树的遍历

    二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历,这三种遍历可以用递归实现(本篇随笔主要分析递归实现),也可使用非递归实现的

     

    前序遍历:根节点->左子树->右子树(根->左->右)

    中序遍历:左子树->根节点->右子树(左->根->右)

    后序遍历:左子树->右子树->根节点(左->右->根)

    在进行已知两种遍历顺序求另一种遍历顺序前,先看一下不同遍历顺序对应的代码

     

    前序遍历

    复制代码

     1 /* 以递归方式 前序遍历二叉树 */
     2 void PreOrderTraverse(BiTree t, int level)
     3 {
     4     if (t == NULL)    
     5     {
     6         return ;
     7     }
     8     printf("data = %c level = %d\n ", t->data, level);
     9     PreOrderTraverse(t->lchild, level + 1);
    10     PreOrderTraverse(t->rchild, level + 1);
    11 }

    复制代码

     

    中序遍历

    复制代码

     1 /* 以递归方式 中序遍历二叉树 */
     2 void PreOrderTraverse(BiTree t, int level)
     3 {
     4     if (t == NULL)    
     5     {
     6         return ;
     7     }
     8     PreOrderTraverse(t->lchild, level + 1);
     9     printf("data = %c level = %d\n ", t->data, level);
    10     PreOrderTraverse(t->rchild, level + 1);
    11 }

    复制代码

     

    后序遍历

    复制代码

     1 /* 以递归方式 后序遍历二叉树 */
     2 void PreOrderTraverse(BiTree t, int level)
     3 {
     4     if (t == NULL)    
     5     {
     6         return ;
     7     }
     8     PreOrderTraverse(t->lchild, level + 1);
     9     PreOrderTraverse(t->rchild, level + 1);
    10     printf("data = %c level = %d\n ", t->data, level);
    11 }

    复制代码

     

     三种遍历方式对应的代码几乎相同,只是一条语句的位置发生了变化

    printf("data = %c level = %d\n ", t->data, level);

     只看文字和代码来理解遍历的过程是比较困难的,建议读者亲自去遍历,为了理清遍历的过程下面上题

     

    (图片来源:https://www.cnblogs.com/xinchrome/p/4905608.html

    前序遍历

    前序的遍历的特点,根节点->左子树->右子树,注意看前序的遍历的代码printf语句是放在两条递归语句之前的,所以先访问根节点G,打印G,然后访问左子树D,此时左子树D又作为根节点,打印D,再访问D的左子树A

    A又作为根节点,打印A,A没有左子树或者右子树,函数调用结束返回到D节点(此时已经打印出来的有:GDA)D节点的左子树已经递归完成,现在递归访问右子树F,F作为根节点,打印F,F有左子树访问左子树E,E作为

    根节点,打印E,(此时已经打印出来的有:GDAFE),E没有左子树和右子树,函数递归结束返回F节点,F的左子树已经递归完成了,但没有右子树,所以函数递归结束,返回D节点,D节点的左子树和右子树递归全部完成,

    函数递归结束返回G节点,访问G节点的右子树M,M作为根节点,打印M,访问M的左子树H,H作为根节点,打印H,(此时已经打印出来的有:GDAFEMH)H没有左子树和右子树,函数递归结束,返回M节点,M节点的左子树已经

    递归完成,访问右子树Z,Z作为根节点,打印Z,Z没有左子树和右子树,函数递归结束,返回M节点,M节点的左子树右子树递归全部完成,函数递归结束,返回G节点,G节点的左右子树递归全部完成,整个二叉树的遍历就结束了

    (MGJ,终于打完了··)

    前序遍历结果:GDAFEMHZ

     

    总结一下前序遍历步骤

    第一步:打印该节点(再三考虑还是把访问根节点这句话去掉了)

    第二步:访问左子树,返回到第一步(注意:返回到第一步的意思是将根节点的左子树作为新的根节点,就好比图中D是G的左子树但是D也是A节点和F节点的根节点)

    第三步:访问右子树,返回到第一步

    第四步:结束递归,返回到上一个节点

     前序遍历的另一种表述:

    (1)访问根节点

    (2)前序遍历左子树

    (3)前序遍历右子树

    (在完成第2,3步的时候,也是要按照前序遍历二叉树的规则完成)

    前序遍历结果:GDAFEMHZ

     

    中序遍历(详细遍历过程就不再赘述了,(┬_┬))

    中序遍历步骤

    第一步:访问该节点左子树

    第二步:若该节点有左子树,则返回第一步,否则打印该节点

    第三步:若该节点有右子树,则返回第一步,否则结束递归并返回上一节点

    (按我自己理解的中序就是:先左到底,左到不能在左了就停下来并打印该节点,然后返回到该节点的上一节点,并打印该节点,然后再访问该节点的右子树,再左到不能再左了就停下来)

    中序遍历的另一种表述:

    (1)中序遍历左子树

    (2)访问根节点

    (3)中序遍历右子树

    (在完成第1,3步的时候,要按照中序遍历的规则来完成)

    所以该图的中序遍历为:ADEFGHMZ

     

    后序遍历步骤

    第一步:访问左子树

    第二步:若该节点有左子树,返回第一步

    第三步:若该节点有右子树,返回第一步,否则打印该节点并返回上一节点

     后序遍历的另一种表述:

    (1)后序遍历左子树

    (2)后序遍历右子树

    (3)访问根节点

    (在完成1,2步的时候,依然要按照后序遍历的规则来完成)

    该图的后序遍历为:AEFDHZMG

     (读者如果在纸上遍历二叉树的时候,仍然容易将顺序搞错建议再回去看一下三种不同遍历对应的代码)

     

    进入正题,已知两种遍历结果求另一种遍历结果(其实就是重构二叉树)

    第一种:已知前序遍历、中序遍历求后序遍历

    前序遍历:ABCDEF

    中序遍历:CBDAEF

    在进行分析前读者需要知道不同遍历结果的特点

    1、前序遍历的第一元素是整个二叉树的根节点

    2、中序遍历中根节点的左边的元素是左子树,根节点右边的元素是右子树

    3、后序遍历的最后一个元素是整个二叉树的根节点

    (如果读者不明白上述三个特点,建议再回去看一下三种不同遍历对应的代码,并在纸上写出一个简单的二叉树的三种不同的遍历结果,以加深对三种不同遍历的理解)

    用上面这些特点来分析遍历结果,

    第一步:先看前序遍历A肯定是根节点

    第二步:确认了根节点,再来看中序遍历,中序遍历中根节点A的左边是CBD,右边是EF,所有可以确定二叉树既有左子树又有右子树

    第三步:先来分析左子树CBD,那么CBD谁来做A的左子树呢?这个时候不能直接用中序遍历的特点(左->根->右)得出左子树应该是这个样子

    因为有两种情况都满足中序遍历为CBD无法直接根据中序遍历来直接得出左子树的结构,这个时候就要返回到前序遍历中去

    观察前序遍历ABCDEF,左子树CBD在前序遍历中的顺序是BCD,意味着B是左子树的根节点(这么说可能不太好理解,换个说法就是B是A的左子树),得出这个结果是因为如果一个二叉树的根节点有左子树,那么

    这个左子树一定在前序遍历中一定紧跟着根节点(这个是用前序遍历的特点(根->左->右)得出的),到这里就可以确认B是左子树的根节点

    第四步:再观察中序遍历CBDAEF,B元素左边是C右边是D,说明B节点既有左子树又有右子树,左右子树只有一个元素就可以直接确定了,不用再返回去观察前序遍历

    第五步:到这里左子树的重建就已经完成了,现在重建右子树,因为重建右子树的过程和左子树的过程一模一样,步骤就不像上面写这么细了((┬_┬)),观察中序遍历右子树为EF,再观察前序遍历ABCDEF中右子树

    的顺序为EF,所以E为A的右子树,再观察中序便利中E只有右边有F,所有F为E的右子树,最后得到的二叉树是这个样子的

    所有求得的后序遍历为:CDBFEA

     

    总结一下上述步骤: 先观察前序遍历找到根节点->观察中序遍历将根节点左边归为左子树元素,右边归为右子树元素(可能会出现只有左子树或者右子树的情况)->观察前序遍历中左\右子树几个元素的顺序,最靠前的为左\右子树的根节点->重复前面的步骤

    第二种:已知中序遍历、后序遍历求前序遍历(题还是上面这道)

    中序遍历:CBDAEF

    后序遍历为:CDBFEA

    仍然是根据不同遍历方式结果的特点来重构二叉树,过程很相似这里就不详细说了,后序遍历的最后一个元素A是根节点,在中序遍历中以根节点A作为分界将元素分为左子树(CBD)和右子树(EF),再观察后序遍历中左子树的顺序是CDB

    ,可以判断出B是左子树的根节点(因为后序遍历是:左->右->根),再观察中序遍历,B元素左边是C右边是D,说明B节点既有左子树又有右子树,左右子树只有一个元素就可以直接确定了,不用再返回去观察后序遍历,左子树重建完成,

    现在来看右子树,右子树有两个元素EF,观察后序遍历E在F的后面,所以E是右子树的根节点,然后看中序遍历中E只有右边一个F元素了,即F是E的右子树,此时整个二叉树重构完成

     

    总结一下上述步骤:先观察后序遍历找到根节点->观察中序遍历将根节点左边归为左子树元素,右边归为右子树元素(可能会出现只有左子树或者右子树的情况)->观察后序遍历中左\右子树几个元素的顺序,最靠后的为左\右子树的根节点->重复前面的步骤

     

    注意:已知前序遍历、后序遍历无法求出中序遍历(因为由前序后序重构出来的二叉树不止一种)

    举个栗子左图这两种二叉树前序(BEFA)和后序(AFEB)一样,但对应的中序遍历结果不一样(左边的是AFEB右边的是BEFA),所以仅靠前序后序是

    重构出唯一的二叉树

     

    展开全文
  • 二叉树中已知前序和中序,画图求后序(超简单) 1.了解什么是前序遍历,中序遍历,后序遍历? 其实这个顺序就是表示根节点所在的位置,左子树右子树的顺序是固定的,都是先左后右。 所以根结点与左右子树的关系就...
  • 已知二叉树的前序和中序后序 例:前序(A B D G H C E I F J ) 中序(G D H B A E I C J F) 其后序为:G H D B I E J F C A 思路:先序的遍历规则为根—左—右,中序的遍历规则为左—根—右,所以我们在中序...
  • 传入前序遍历序列中序遍历序列,后划分为左子树的前序中序遍历序列右子树前序中序遍历序列,符合递归的思想,而后序遍历的遍历为:左->右->根,所以先递归左子树序列,后递归右子树序列,再输出根节点 ...
  • 今天来总结下二叉树前序中序后序遍历相互法,即如果知道两个的遍历,如何第三种遍历方法,比较笨的方法是画出来二叉树,然后根据各种遍历不同的特性来,也可以编程出,下面我们分别说明。 首先,我们看...
  • 我就不板门弄斧了求后序 class Tree(): def __init__(self,x): self.value=x self.left=None self.right=None class Solution(): def resolution(self,preorder,inorder): if no...
  • 这个问题在面试中很常见,本人就碰到过一次,已经吃过一次亏了。。。。 /* *程序说明:已知二叉树的前序序列和中序序列,写一个算法... 如果在右,那么就是右节点,已知中序和后序求前序是一样的道理。 */ #include
  • 1、先说根据前序中序求后序,前序总是沿着根往树的左边一直跑,所以前序遍历的前面肯定是根节点 中序则是按照:左—–根—–右 的顺序排列,其中左,右子树按照同样的结构,所以我们可以从前序遍历的根节点入手,...
  • 问题描述 在一个二叉树中,前序遍历结果为:ABDGCEFH, 中序遍历结果为DGBAECHF,求后序遍历结果二叉树的遍历 前序遍历方式:根左右 中序遍历方式:左根右 后序遍历方式:左右根 所以,前序遍历中的第一个结点...
  • 只知道中序和后序怎么知道二叉树呢?? 现在我们来了解一下基础的原理: 先知道概念噢!qwq~~~ 前序遍历:先访问当前节点,再访问当前节点的左子树,最后访问当前节点的右子树。对于二叉树,深度遍历与此同。规律:...
  • 我们知道,二叉树的遍历有三种,分别是前序遍历、中序遍历和后序遍历,我们来看看这三种遍历的特性: 前序遍历(根-->左-->右) 1.访问根节点 2.前序遍历左子树 3.前序遍历右子树 中序遍历(左-->...
  • 根据先序 中序求后序

    2016-05-23 11:24:20
    使用数组求解已知树的先序和中序求解后序的问题
  • 平时做笔试题目时,都是先拿前序的首字母,去和中序的字母比较,然后把中序的分成两段,不停的遍历,直到长度等于一(即叶子节点)。 例题 二叉树是一种常用的数据结构。我们可以用大写的英文字母表示二叉树的节点。...
  • /** * @author: haijiao12138 ... * 前序遍历:GDAFEMHZ * 中序遍历:ADEFGHMZ * 后续遍历 * @date: 2021/8/31 11:14 */ public class Tree { public static void main(String[] args) { .
  • 树的三种遍历方式的遍历顺序: 先序遍历:根、左子树、右子树(特点:第一个元素为根) 中序遍历:左子树、根、右子树(特点:...1、已知先序和中序求后序 先序遍历的第一个字符为根,因此只需在中序遍历中找到它,
  • 题目描述 二叉树的前序中序后序遍历的定义: ...给定一棵二叉树的前序遍历和中序遍历,后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。 输入 两个字符串,其长度n均小...
  • 导言 ...比如,仅仅有前序遍历的结果信息,我们知道A是二叉树的根节点,但是除此之外,就不知道了,比如下面这棵二叉树,其前序遍历的结果,上面的二叉树前序遍历结果是一样的: 因此,仅仅根据前
  • 层序遍历6.8.3 前序遍历算法6.8.4 中序遍历算法6.8.5 后序遍历算法6.8.6 推导遍历结果 6.8 遍历二叉树 6.8.1 二叉树遍历原理 假设,我手头有20张100元的2000张1元的奖券,同时洒向了空中,大家比赛看谁最终...
  • 快速学会并掌握二叉树的前序中序后序遍历
  • 1、已知前序遍历和中序遍历 2、已知中序遍历和后序遍历 3、已知前序遍历和后序遍历,无法确定一颗唯一的二叉树 参考文献   二叉树的遍历方法 前序遍历:根左右。先打印,再遍历左子树,再遍历右子树; 中序...
  • * 已知二叉树前序和中序求后序 * @param pre * @param mid * @param last * @param i */ public static int i =0;//i:表示要插入后序序列的位置对于生成的后序序列,应该从最后位置开始写, // 所以...
  • 前序表达式 中序表达式 后序表达式

    千次阅读 2019-04-19 19:29:50
    中序表达式: ...一种逻辑、算术代数表示方法,其特点是操作符置于操作数的前面,如果操作符的元数(arity)是固定的,则语法上不需要括号仍然能被无歧义地解析,不需要括号来改变优先级,未推广使用...
  • 二、已知二叉树的前序遍历和中序遍历,如何得到它的后序遍历?三、程序实现总结 前言 最近复习题中看到二叉树,对于它的前序中序后序遍历的判断有些模糊,后经查阅资料,将学习过程记录在博客中。 提示:以下...
  • 树的三种遍历方式的遍历顺序: 先序遍历:根、左子树、右子树(特点:第一个元素为根) 中序遍历:左子树、根、右子...1、已知先序和中序求后序 先序遍历的第一个字符为根,因此只需在中序遍历中找到它,就可以把根...
  • 前序遍历:根节点->左子树->右子树(根->左->右) 中序遍历:左子树->根节点->右子树(左->根->右) 后序遍历:左子树->右子树->根节点(左->右->根) 技巧:看根节点打印的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,257
精华内容 2,502
关键字:

已知前序和中序求后序