老斑鸠1998 2019-04-08 21:36
浏览 589

PTA 03-树3 Tree Traversals Again

在Dev C++里输出答案正确,但过不了PTA测试里的sample测试,显示答案错误DEV C++jie'guo图片说明

代码如下

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct stack* Ptrs;
struct BinTree{
    int data;
    int left;
    int right;
};
struct stack{
    int s_data;
    Ptrs next;
};
void push(int data,Ptrs s)
{
    Ptrs tmp;
    tmp=(Ptrs)malloc(sizeof(struct stack));
    tmp->s_data=data;
    if(s->next==NULL)
    {
        s->next=tmp;
        tmp->next=NULL;
    } 
    else
    {
        tmp->next=s->next;
        s->next=tmp;
    }
}
int pop(Ptrs s)
{
    int top;
    Ptrs tmp;
    tmp=s->next;
    top=tmp->s_data;
    s->next=tmp->next;
    free(tmp);
    return top;
}
int top(Ptrs s)
{
    if(s->next==NULL)
    return 0;
    else
    return(s->next->s_data);

}
int Isempty(Ptrs s)
{
    if(s->next==NULL)
    return 0;
    else
    return 1;
}
void plantTree(int N,struct BinTree T[])
{
    char op[5];
    int data;
    Ptrs stack;
    stack=(Ptrs)malloc(sizeof(struct stack));
    stack->next=NULL;
    int k=0;
    int pre_top;
    int flag=0;
    for(int i=0;i<2*N;i++)
    {
        //输入部分 
        scanf("%s",op);
        if(strcmp(op,"Push")==0)
        {
            if(i==2*N-1)
            scanf(" %d",&data);
            else
            scanf(" %d\n",&data);
            if(flag==0)
            pre_top=top(stack);
            push(data,stack);
            T[k].data=data;
            k++;
            if(pre_top!=0)
          {
            if(T[pre_top-1].left==0)
            T[pre_top-1].left=data;
            else
            T[pre_top-1].right=data;
          }
            flag=0;
        }
        else
        {
            if(i==2*N-1);
            else
            scanf("\n");
            pre_top=pop(stack);
            flag=1;//
        }   
    }//plant tree successfully

}

int SearchFather(int child,int N,struct BinTree T[])
{

    for(int i=0;i<N;i++)
    {
        if(T[i].left==child||T[i].right==child)
        return(T[i].data);
    }
    return 0;//root
}
int LeftLeaf(int left,int root,struct BinTree T[],Ptrs stack)//找到左叶,并一直push father和右兄弟;若没有左叶,则不执行push 
{

    while(left!=0)
    {
        if(T[root].data!=top(stack))
        push(T[root].data,stack);
        if(T[root].right!=0)
        push(T[root].right,stack);

        root=left-1;//一直向左的终点 数组序号 
        left=T[root].left;
    }
    if(T[root].data!=top(stack))
    push(T[root].data,stack);

 } 
void postOrderTraversal(int N,struct BinTree T[])
{
    Ptrs stack;
    stack=(Ptrs)malloc(sizeof(struct stack));
    stack->next=NULL;

    int left,root;
     int flag=0;
    root=0;//root
    left=T[root].left;
    //push(T[root].data,stack);
    LeftLeaf(left,root,T,stack); 
    //找到左叶,并push

    while(Isempty(stack)!=0)//栈不空时 
    {
        int _pop;
        _pop=pop(stack);
        if(flag==1)
        printf(" ");
        printf("%d",_pop);//输出 
        flag=1;
        int father=SearchFather(_pop,N,T); 
        if(top(stack)!=father)//还有右兄弟分支需遍历 ,若相等说明已经遍历过右边 
      {
        root=top(stack)-1;
        left=T[root].left;
        LeftLeaf(left,root,T,stack);//find leftleaf

      }
    }

 } 

int main()
{
    int N;
    scanf("%d\n",&N);
    struct BinTree T[N]={0};
    plantTree(N,T);
    postOrderTraversal(N,T);
    return 0;
}

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 COCOS的问题COCOS的问题
    • ¥15 FPGA-SRIO初始化失败
    • ¥15 MapReduce实现倒排索引失败
    • ¥15 ZABBIX6.0L连接数据库报错,如何解决?(操作系统-centos)
    • ¥15 找一位技术过硬的游戏pj程序员
    • ¥15 matlab生成电测深三层曲线模型代码
    • ¥50 随机森林与房贷信用风险模型
    • ¥50 buildozer打包kivy app失败
    • ¥30 在vs2022里运行python代码
    • ¥15 不同尺寸货物如何寻找合适的包装箱型谱