03-树3 Tree Traversals Again (25 分)

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

3 4 2 6 5 1

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 31 //TREE从1开始存储有效结点，下标为0表示NULL
#define Push "Push" //定义字符串宏常量
#define Pop "Pop"
/*栈*/
struct SNode
{
    int Data[MAXSIZE];
    int Top;
};
/*树*/
typedef struct TreeNode *BinTree;
struct TreeNode
{
    int Left;
    int Right;
}Tree[MAXSIZE];
int CNT=0;

void PostorderTraversal(int ROOT);
int ReadTree();

int main()
{
    /* 1.按照中序遍历读入二叉树 2.找出根节点 3.从根节点开始后序遍历，输出结点 */
    int root;
    root = ReadTree();
    PostorderTraversal(root);
    return 0;
}

/*按照中序遍历读入二叉树，并返回根节点*/
int ReadTree()
{
    int N,t,j=1;
    scanf("%d",&N);
    int tmp[N];  //用于存储结点Push顺序
    
    /*初始化栈*/
    struct SNode *S;
    S = (struct SNode *)malloc(sizeof(struct SNode));
    S->Top = -1;
    
    char *ch[2*N]; //字符指针数组，用于存储键盘输入的Push or Pop操作字符
    /*第一个Push结点为根节点，入栈*/
    ch[0] = (char *)malloc(sizeof(char)*5);
    scanf("\n%s",ch[0]);
    scanf("%d",&tmp[0]);
    S->Top++;
    S->Data[S->Top] = tmp[0];
    if(N){
            //构造空树
        for(int i=1;i<=N;i++)
        {
            Tree[i].Left =0;
            Tree[i].Right=0;
        }

        for(int i=1;i<=2*N-1;i++)
        {
            /*算法: 1.第一个结点必为Push操作，先存储 2.继续输入，结点若为Push操作，入栈，并判断上一个操作： 若为Push，則该结点为上一个结点的左儿子； 若为Pop，則该结点为上一个Pop结点的右儿子； 结点若为Pop操作，出栈。 3.循环第二步，直到栈空。 */
            ch[i] = (char *)malloc(sizeof(char)*5);
            scanf("\n%s",ch[i]);
            if(strcmp(ch[i],Push)==0)
            {
                scanf("%d",&tmp[j]);
                S->Top++;
                S->Data[S->Top] = tmp[j];
// printf("S->Top =%d,S->Data[%d] = %d\n",S->Top,S->Top,S->Data[S->Top]);
                if(strcmp(ch[i-1],Push)==0)
                {
                    Tree[tmp[j-1]].Left = tmp[j];
// printf("Tree[%d].Left = %d\n",tmp[j-1],Tree[tmp[j-1]].Left);
                }else if(strcmp(ch[i-1],Pop)==0)
                {
                    Tree[t].Right = tmp[j];
// printf("Tree[%d].Right = %d\n",t,Tree[t].Right);
                }
                j++;

            }else if(strcmp(ch[i],Pop)==0)
            {
                t = S->Data[S->Top];
// printf("Pop = %d\n",t);
                S->Top--;
// printf("S->Top =%d\n",S->Top);
            }
        }
    }
    return tmp[0];
}

void PostorderTraversal(int ROOT)
{
    if( ROOT!=0 ) {
        PostorderTraversal(Tree[ROOT].Left);
        PostorderTraversal( Tree[ROOT].Right );
        if(CNT == 0)
            printf("%d", ROOT);
        else
            printf(" %d", ROOT);
        CNT++;
    }
}