题137.pta数据结构题集-03-树3 Tree Traversals Again (25 分)

一、题目

在这里插入图片描述

二、题解

依题意知道push之前若没有pop操作，则建立上一个push到栈里的节点的左子树，反之则建立pop出来的节点的右子树

#include <bits/stdc++.h>

using namespace std;

int flag=0;

typedef struct Tnode *Position;
typedef Position BinT;
struct Tnode
{
    int data;
    BinT left;
    BinT right;
};

BinT createTree(int N)
{
    int count0=0;
    BinT T=NULL;
    string op;
    stack<Position> s;
    BinT popnode=NULL;
    cin>>op;
    while(1)
    {
        if(op=="Push")
        {
            int data;
            cin>>data;
            Position tnode=(Position)malloc(sizeof(struct Tnode));//生成节点
            tnode->data=data;
            tnode->left=NULL;
            tnode->right=NULL;
            if(T==NULL)//第一个节点为根节点
            {
                T=tnode;
            }
            if(popnode!=NULL)//当上一个操作时pop时，push就是建右子树
            {
                popnode->right=tnode;
                popnode=NULL;//用完一个pop出的结点就清掉，当时因为没清导致后期一直有popnode，从而push一直以覆盖的方式建popnode的右子树
            }
            else if(!s.empty())//当上一个操作是push，并且栈不空时建立栈顶节点的左子树
            {
                s.top()->left=tnode;
            }
            s.push(tnode);
        }
        else
        {
            popnode=s.top();
            s.pop();
            count0++;//pop一个节点数目加1
            if(count0==N)//已建立的节点数目达到N则退出建树
            {
                break;
            }
        }
        cin>>op;
    }
    return T;
}

void PostOrderTraversal(BinT BT)
{
    BinT T=BT;
    if(T==NULL)
    {
        return;
    }
    PostOrderTraversal(T->left);
    PostOrderTraversal(T->right);
    if(flag)
    {
        putchar(' ');
    }
    else
    {
        flag=1;
    }
    printf("%d",T->data);
}

int main()
{
    int N;
    cin>>N;
    BinT T=createTree(N);
    PostOrderTraversal(T);
}