二叉树

二叉树

时间: 1ms        内存:128M

描述:

二叉树是一种常用的数据结构。我们可以用大写的英文字母表示二叉树的节点。

如下:

		    B   
		   /  \    
		  /    \    
                 C      A
		         \
		          \
		           D

对于二叉树,有前序、中序和后序三种遍历方式。 现在给你一棵二叉树的前序和中序遍历,请你求出这棵二叉树的后序遍历结果

输入:

输入数据有多组,每组数据一行。

每行由两个字符串组成(每个字符串长度最大为26)。表示一棵二叉树的前序和中序遍历结果。

题目保证前序和中序遍历是合法的(即肯定可以确定一棵二叉树)。

输出:

对于每组输入,输出对应的二叉树的后序遍历结果。

注意:本题输入输出都在控制台中,使用标准输入输出函数即可,不需要读写文件

示例输入:

BCAD CBAD
ABDGKLRVWSXCEHMNFIOTUJPYQZ KGVRWLSXDBAMHNECTOUIFPYJZQ

示例输出:

CDAB
KVWRXSLGDBMNHETUOIYPZQJFCA

提示:

参考答案(内存最优[752]):

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct BiTNod
{
    char data;
    struct BiTNod *lchild,*rchild;
}BTNode;
BTNode *creatBT(char *pre,char *in,int n)/*/pre[]存放先序序列,in[]存放中序序列,n为二叉树的节点数*/
{
    BTNode *s;
	char *p;
	int k;
	if(n<=0)
		return NULL;
	s=(BTNode *)malloc(sizeof(BTNode));/*/创建二叉树节点*s*/
    s->data =*pre;
	for(p=in;p<in+n;p++)
	{
	    if(*p==*pre)
			break;
	}
	k=p-in;
	s->lchild =creatBT(pre+1,in,k);
    s->rchild =creatBT(pre+k+1,p+1,n-k-1);
	return s;
}
int preorder_l(BTNode *T)/*后序输出*/
{
    if(T!=NULL)
	{
        preorder_l(T->lchild );
		preorder_l(T->rchild );
		printf("%c",T->data );
	}
	return 0;
}
int main()
{
    char pre[30],in[30];
	int n;
	while(scanf("%s%s",pre,in)!=EOF)
	{
		n=strlen(pre);
		preorder_l(creatBT(pre,in,n));
		printf("\n");
	}
	return 0;
}

参考答案(时间最优[0]):

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iomanip>
#include <algorithm>
#include <queue>
#define INF 100000000
#define MAX 550
#define MAXN 130
#define MOD 9
using namespace std;
char pre[30],in[30];
void solve(int preleft,int preright,int inleft,int inright)
{
    int root,leftsize,rightsize;
    for(root=inleft;root<=inright;root++)
        if(pre[preleft]==in[root])
        break;
    leftsize=root-inleft;
    rightsize=inright-root;
    if(leftsize>0)
        solve(preleft+1,preleft+leftsize,inleft,root-1);
    if(rightsize>0)
        solve(preleft+leftsize+1,preright,root+1,inright);
    printf("%c",in[root]);
}
int main()
{
    while(~scanf("%s%s",pre,in))
    {
        int n=strlen(pre);
        solve(0,n-1,0,n-1);
        printf("\n");
    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注