美文网首页
PAT(A)1020. Tree Traversals

PAT(A)1020. Tree Traversals

作者: 有苦向瓜诉说 | 来源:发表于2017-04-16 08:55 被阅读9次

    include <stdio.h>

    #include <stdlib.h>
    typedef struct node{
        int data;
        struct node* left,*right;
    }TreeNode,*Tree;
    Tree BuiltTree(int *post,int *in,int n )//由其他两种序列建立树的过程,递归
    {
        int i;
        Tree root=(Tree)malloc(sizeof(TreeNode));
        root->data=post[n-1];
        root->left=root->right=NULL;
        for(i=0;i<n;i++){
            if(in[i]==post[n-1]){
                break;
            }
        }
        if(i>0){
            root->left=BuiltTree(post,in,i);
        }
        if(n-i-1>0){
            root->right=BuiltTree(post+i,in+i+1,n-i-1);
        }
        return root;
    }
    void LevelOrder(Tree s){//层序遍历
        int isfirst=1;
        TreeNode *queue[30];
        int front=0,rear=0;
        queue[rear++]=s;
        while(front!=rear){
            TreeNode* t=queue[front++];
            if(isfirst){
                isfirst=0;
                printf("%d",t->data );
            }
            else{
                printf(" %d",t->data );
            }
            if(t->left){
                queue[rear++]=t->left;
            }
            if(t->right){
                queue[rear++]=t->right;
            }
        }
    }
    int main(){
    //  freopen("in.txt","r",stdin);
        int n;
        int post[30],in[30];
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&post[i]);
        }
        for(int i=0;i<n;i++){
            scanf("%d",&in[i]);
        }
        Tree T=BuiltTree(post,in,n);
        LevelOrder(T);
        return 0;
    }

    相关文章

      网友评论

          本文标题:PAT(A)1020. Tree Traversals

          本文链接:https://www.haomeiwen.com/subject/tytrwttx.html