初次做二叉树的题目--给定中序和前序求后序

た入场券 2022-07-15 08:29 13阅读 0赞

Farmer John takes the heritage of his cows very seriously. He is not, however, a truly fine bookkeeper. He keeps his cow genealogies as binary trees and, instead of writing them in graphic form, he records them in the more linear \`tree in-order' and \`tree pre-order' notations.

Your job is to create the \`tree post-order' notation of a cow's heritage after being given the in-order and pre-order notations. Each cow name is encoded as a unique letter. (You may already know that you can frequently reconstruct a tree from any two of the ordered traversals.) Obviously, the trees will have no more than 26 nodes.

Here is a graphical representation of the tree used in the sample input and output:

C / \\ / \\ B G / \\ / A D H / \\ E F

The in-order traversal of this tree prints the left sub-tree, the root, and the right sub-tree.

The pre-order traversal of this tree prints the root, the left sub-tree, and the right sub-tree.

The post-order traversal of this tree print the left sub-tree, the right sub-tree, and the root.

PROGRAM NAME: heritageINPUT FORMAT

Line 1: The in-order representation of a tree.

Line 2: The pre-order representation of that same tree.

SAMPLE INPUT (file heritage.in)

ABEDFCHGCBADEFGHOUTPUT FORMAT

A single line with the post-order representation of the tree.

SAMPLE OUTPUT (file heritage.out)

AEFDBHGC

思路：这题主要用到递归的思想代码：

#include<stdio.h>
    #include<string.h>
    #include<malloc.h>
    char root;
    FILE *fin,*fout;
    char pre_order[28],in_order[28];
    struct BNode
    { 
        char data; 
        BNode * ld,* rd;
    };
    int pos=0;
    void createtree(BNode * &b,int first,int last) 
    //这里用了引用类型
    { 
        int i;
        if(first>last) 
            return ; 
        b=(BNode *)malloc(sizeof(BNode)); 
        for(i=first;i<=last;i++) 
            if(in_order[i]==pre_order[pos]) 
                break; 
        b->data=pre_order[pos];
        pos++;

b->ld=NULL;

b->rd=NULL; 
        createtree(b->ld,first,i-1);
        createtree(b->rd,i+1,last);
    }
    
    void post_traversal(BNode *b)
    {
        if(b->ld) 
        post_traversal(b->ld); 
        if(b->rd) 
            post_traversal(b->rd); 
        fprintf(fout,"%c",b->data);
    }
    
    int main()
    {
        int len; 
        BNode *BTree; 
        fin=fopen("heritage.in","r"); 
        fout=fopen("heritage.out","w"); 
        fscanf(fin,"%s%s",in_order,pre_order); 
        len=strlen(in_order); 
        createtree(BTree,0,len-1); 
        post_traversal(BTree); 
        fprintf(fout,"\n"); 
        return 0;
    }

Here are the test data inputs:

\------- test 1 -------  
ABEDFCHG  
CBADEFGH  
\------- test 2 -------  
F  
F  
\------- test 3 -------  
BCAD  
ABCD  
\------- test 4 -------  
GOLEAFS  
SFAELOG  
\------- test 5 -------  
GSHBAQTPM  
ABGHSPQTM  
\------- test 6 -------  
AUBYCVDZEWFXGTH  
ZYUABVCDXWEFTGH  
\------- test 7 -------  
ABDCJHKILMNPOQFEGRS  
ABCDEFHJIKLMNOPQGRS  
\------- test 8 -------  
GFDIHKLJMBNESRTPOQAUCWVZYX  
ABDFGHIJKLMENOPRSTQCUVWXYZ  
\------- test 9 -------  
EHGDIFJLKMBNCOQSPRAWUXZYTV  
ABDEGHFIJKLMCNOPQSRTUWXYZV

Keep up the good work!