求先序遍历

  1. 云栖社区>
  2. 博客列表>
  3. 正文

求先序遍历

this_is_bill 2013-11-16 10:30:00 浏览337 评论0

摘要: 代码如下: #include <stdio.h> struct TreeNode { struct TreeNode* left; struct TreeNode* right; char elem; }; TreeNode* BinaryTreeFromOrd...

代码如下:

#include <stdio.h>

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char  elem;
};


TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length)
{
    if(length == 0)
    {
        return NULL;
    }

    TreeNode* node = new TreeNode;		//新建一个树节点
    node->elem = *(aftorder+length-1);

	printf("%c ",node->elem);

    int rootIndex = 0;

    for(;rootIndex < length; rootIndex++)		//找这个根节点
    {
        if(inorder[rootIndex] ==  *(aftorder+length-1))
            break;
    }

    node->left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex);
    node->right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1));
    
    return node;
}

int main()
{
	char* in="42513";		//中序
    char* af="45231";		//后序
    BinaryTreeFromOrderings(in, af, 5); 

	printf("\n");

    return 0;
}


暂时无法判断非法输入的代码:

#include <stdio.h>
#include <iostream>
#include <string.h>
#define MAXN 5005

using namespace std;

char in[MAXN];       //中序
char af[MAXN];       //后序
char ans[MAXN];		//最后输出的前序序列
int count=0;

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    char  elem;
};


TreeNode* BinTree(char* inorder, char* aftorder, int length)
{
    if(length == 0)
    {
        return NULL;
    }

    TreeNode* node = new TreeNode;		//新建一个树节点
    node->elem = *(aftorder+length-1);

	ans[count++]=node->elem;		//存入答案

    int rootIndex = 0;

    for( ;rootIndex<length;rootIndex++)		//找这个根节点
    {
        if(inorder[rootIndex]==*(aftorder+length-1))
            break;
    }

    node->left = BinTree(inorder,aftorder,rootIndex);
    node->right = BinTree(inorder+rootIndex+1 , aftorder+rootIndex , length-(rootIndex+1));

	return node;
}

int main()
{
	int n;
	scanf("%d",&n);

	int i;
	for(i=0;i<n;i++)
		cin>>in[i];

	for(i=0;i<n;i++)
		cin>>af[i];

    BinTree(in, af, n);

	for(i=0;i<strlen(ans)-1;i++)
		printf("%c ",ans[i]);
	printf("%c\n",ans[i]);

    return 0;
}

改用int型:

#include <stdio.h>
#include <stdlib.h>
#define MAXN 5005


int in[MAXN];       //中序
int af[MAXN];       //后序
int ans[MAXN];		//最后输出的前序序列
int count=0;

struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    int elem;
};


TreeNode* BinTree(int inorder[], int aftorder[], int length)
{
	if(length == 0)
    {
        return NULL;
    }

    TreeNode* node = new TreeNode;		//新建一个树节点
    node->elem = *(aftorder+length-1);

	ans[count++]=node->elem;		//存入答案

    int rootIndex=0;

    for( ;rootIndex<length;rootIndex++)		//在中序遍历中找这个根节点
    {
        if(inorder[rootIndex]==*(aftorder+length-1))
            break;
    }
	if(rootIndex>=length)
	{
		printf("-1\n");
		exit(0);
	}

    node->left = BinTree(inorder,aftorder,rootIndex);
    node->right = BinTree(inorder+rootIndex+1 , aftorder+rootIndex , length-(rootIndex+1));

	return node;
}

int main()
{
	int n;
	scanf("%d",&n);

	int i;
	for(i=0;i<n;i++)
		scanf("%d",&in[i]);

	for(i=0;i<n;i++)
		scanf("%d",&af[i]);

    BinTree(in,af,n);

	for(i=0;i<count-1;i++)
		printf("%d ",ans[i]);
	printf("%d\n",ans[i]);

    return 0;
}


用云栖社区APP,舒服~

【云栖快讯】Apache旗下顶级开源盛会 HBasecon Asia 2018将于8月17日在京举行,现场仅600席,免费赠票领取入口  详情请点击

网友评论

this_is_bill
文章436篇 | 关注12
关注
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
RDS是一种稳定可靠、可弹性伸缩的在线数据库服务。支持MySQL、SQL Server、Po... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航