求先序遍历

代码如下:

#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;
}
时间: 2024-05-25 05:38:35

求先序遍历的相关文章

二叉树系列(二):已知中序遍历序列和后序遍历序列,求先序遍历序列

前面已经介绍过三种遍历方法的规则,为了大家看着方便,这里我们在重新介绍一遍:   1.先序遍历   (1)访问根结点:   (2)先序遍历左子树:   (3)先序遍历右子树.   2.中序遍历   (1)中序遍历左子树:   (2)访问根结点:   (3)中序遍历右子树.   3.后序遍历   (1)后序遍历左子树:   (2)后序遍历右子树:   (3)访问根结点.   知道了二叉树的三种遍历规则,只要有中序遍历序列和前后任一种遍历序列,我们就可以求出第三种遍历序列,今天我们研究的是已知中序和

二叉树系列(一):已知先序遍历序列和中序遍历序列,求后序遍历序列

  首先介绍一下三种遍历顺序的操作方法:   1.先序遍历   (1)访问根结点:   (2)先序遍历左子树:   (3)先序遍历右子树.   2.中序遍历   (1)中序遍历左子树:   (2)访问根结点:   (3)中序遍历右子树.   3.后序遍历   (1)后序遍历左子树:   (2)后序遍历右子树:   (3)访问根结点.   知道了二叉树的三种遍历规则,只要有中序遍历序列和前后任一种遍历序列,我们就可以求出第三种遍历序列,今天我们研究的是已知先序和中序遍历序列,求后序遍历序列.   

根据先序中序遍历建树【模板】

主要就是通过先序找到当前子树根节点,再用中序遍历分子树,不断递归下去. #include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <cassert> #include <time.h>

二叉树的非递归先序,中序,后序遍历

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<stack> using namespace std; struct Tree{ int x; Tree *lchild, *rchild; Tree(){ lchild = rchild = NULL; } }; typedef Tree* pT; void buildT(pT &

UVa 548:Tree 二叉树的重建——中序遍历与后续遍历进行建树

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=489 题目类型: 数据结构, 二叉树 题目大意: 给两个组数字,都是在同一棵二叉树上的,第一组是按中序遍历(inorder)顺序输出的,第二组是按后序遍历(postorder)输出的, 根据这两组数据构建出原来的二叉树,然后计算从根结点到每个叶子结

UVa 10562 Undraw the Trees:二叉树先序遍历

10562 - Undraw the Trees Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=1503 Professor Homer has been reported missing. We suspect that his recent resea

UVa 548 Tree:中序遍历&amp;amp;后序遍历&amp;amp;DFS

548 - Tree Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=489 You are to determine the value of the leaf node in a given binary tree that is the termina

二叉树的创建、前序遍历、中序遍历、后序遍历

// BTree.cpp : Defines the entry point for the console application. /* 作者:成晓旭 时间:2001年7月2日(9:00:00-14:00:00) 内容:完成二叉树的创建.前序遍历.中序遍历.后序遍历 时间:2001年7月2日(14:00:00-16:00:00) 内容:完成二叉树的叶子节点访问,交换左.右孩子 */ #include "stdafx.h" #include "stdlib.h"

先序遍历二叉树的递归实现与非递归实现深入解析

以下是对先序遍历二叉树的递归实现与非递归实现进行了详细的分析介绍,需要的朋友可以过来参考下   1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点: 2)先序遍历左子树: 3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visi