ACM 重建二叉树-白红宇

ACM 重建二叉树

阅读量：6327 次

发布时间：2019-06-22

本文共 1420 字，大约阅读时间需要 4 分钟。

重建二叉树

时间限制：

1000 ms | 内存限制：65535 KB

难度：

描述

题目很简单，给你一棵二叉树的后序和中序序列，求出它的前序序列（So easy!）。

输入

输入有多组数据（少于100组），以文件结尾结束。

每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的后序和中序序列（字符串长度小于26，输入数据保证合法）。

输出

每组输出数据单独占一行，输出对应得先序序列。

样例输入

ACBFGED ABCDEFGCDAB CBAD

样例输出

DBACEGFBCAD

这道题主要考查对二叉树的遍历的熟悉程度，对先序遍历，中序遍历，后序遍历的掌握程度；

由后序遍历可以得到，最后一个字母应该就是树的根节点，中序遍历是先访问左子树，后访问根节点，在访问右子树，然后通过中序遍历的序列，可以把这颗树分成左右子树，得出这颗树的结构，然后再递归得出先序遍历的序列

#include 
       
        #include 
        
         #include 
         
          struct Node{    char value;    Node* left;    Node* right;};Node* buildNode(char value){    Node* node = (Node*)malloc(sizeof(Node));    node->value = value;    node->left = node->right = NULL;    return node;}Node* rebuildTree(char* post, char* in, int len){    int i = 0;    if(len == 0)        return NULL;    Node* head = buildNode(post[len-1]);    for(i = 0; i < len; i++)    {        if(in[i] == post[len - 1])            break;    }    head->left = rebuildTree(post, in, i);    head->right = rebuildTree(post+i, in+i+1, len-i-1);    return head;}void preorder(Node* head){    if(head == NULL)        return;    printf("%c", head->value);    preorder(head->left);    preorder(head->right);}int main(){    char post[100], in[100];    while(scanf("%s%s", post, in) != EOF)    {        preorder(rebuildTree(post, in, strlen(post)));        printf("\n");    }    return 1;}

转载于:https://www.cnblogs.com/sdlwlxf/p/4557344.html

你可能感兴趣的文章