已知前序遍历和中序遍历求二叉树[通俗易懂]

已知前序遍历和中序遍历求二叉树[通俗易懂]描述输入某二叉树的前序遍历和中序遍历的结果,请输出后序遍历序列。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},重建二叉树并返回后序遍历序列输入输入某二叉树的前序遍历和中序遍历的结果输出输出后序遍历序列输入样例1 12473568…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

描述

输入某二叉树的前序遍历和中序遍历的结果,请输出后序遍历序列。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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

7 4 2 5 8 6 3 1

 题意:

前序遍历即先访问根节点,然后是左子树,右子树

中序遍历为先访问左子树,然后是根节点,右子树

所以通过前序遍历不断地找到根节点,然后中序遍历找到其左子树和右子树

已知前序遍历和中序遍历求二叉树[通俗易懂]

已知前序遍历和中序遍历求二叉树[通俗易懂]

已知前序遍历和中序遍历求二叉树[通俗易懂]

已知前序遍历和中序遍历求二叉树[通俗易懂]

已知前序遍历和中序遍历求二叉树[通俗易懂]

已知前序遍历和中序遍历求二叉树[通俗易懂]

最后就可以得到这棵二叉树,后序遍历即为 7 4 2 5 8 6 3 1

实现代码:

#include<stdio.h>
#include<stdlib.h> 
#include<string.h> 
typedef struct node* BinTree; 
struct node{
	int date;
	BinTree left;
	BinTree right;
};
BinTree Build(int pre[] ,int in[] ,int size)
{
	if(size<=0)return NULL;
	//先在中序中找到根节点
	int i;
	for(i=0;i<size;i++)
	{
		if(in[i]==pre[0])break;
	} 
	BinTree tree=(BinTree)malloc(sizeof(struct node));
	tree->date=pre[0];
	tree->left=Build(pre+1,in,i);
	tree->right=Build(pre+i+1,in+i+1,size-1-i);
	return tree;
} 
void postorder(BinTree T)  //后序遍历 
{
	if(T==NULL)return;
	else{
		postorder(T->left);
		postorder(T->right);
	    printf("%d ",T->date);
	}
	
} 
int main()
{
	char pree[800],inn[800];  
	gets(pree);
	gets(inn);  
	int size=strlen(pree);  
	int pre[800],in[800];
	int precount=0; 
	int i;
	for(i=0;i<size;i++)
	{
		if(i==0)
		{
			pre[precount]=pree[i]-'0';
		}
		else
		{
			if(pree[i]>='0'&&pree[i]<='9')
			{
				//此if-else 用来转换多位数为int类型 
				if(pree[i-1]==' ')  //如果前一个元素为空格 
				{
					precount++;
				    pre[precount]=pree[i]-'0';
				}
				
				else  //如果前一个元素不是空格,那么说明与前一个元素一同构成的数  例如:10 
				{
					pre[precount]=pre[precount]*10+(pree[i]-'0');
				}
			}
			
		}
		
	}
	int incount=0;
	for(i=0;i<size;i++)
	{
		if(i==0)
		{
			in[incount]=inn[i]-'0'; 
		}
		else
		{
			if(inn[i]>='0'&&inn[i]<='9')
			{
				if(inn[i-1]==' ')
				{
					incount++;
				    in[incount]=inn[i]-'0';
				}
				
				else
				{
					in[incount]=in[incount]*10+(inn[i]-'0');
				}
			}
			
		}
		
	}  
    //如果前序遍历的结点数与中序遍历的结点数相同且不为0,那么可以找到对应二叉树 
    if(precount==incount&&precount!=0)  
    {
    	BinTree T;
		T=Build(pre,in,precount+1);
		postorder(T);
	}
	
    
	return 0;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195213.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号