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

代码实现

C语言

/*
本题本质上是已知前序中序遍历，求后序遍历的问题。
在输入的时候有如下规律：
1、第一个push进来的是整个树的根节点。
2、若本次操作为push，且上次操作为push，则本次push的节点是上次push节点的左儿子。
3、若本次操作为push，且上次操作为pop，则本次push节点是上次pop出来节点的右儿子。
4、若本次操作为pop，且上次操作为push，则本次push节点是叶节点。
5、若本次操作为pop，且上次操作为pop，无节点设置。 
*/

#include<stdio.h>
#include<string.h>
#define MaxTree 30
#define Null -1

int A[MaxTree]; // 用于记录递归后序遍历得到的节点号 
int Aindex = 0;

struct TreeNode {
    int Left;
    int Right;
} T[MaxTree];

struct Stack {
    int TreeNodes[MaxTree];
    int front;
} S;

void InitStack() {
    for ( int i=0; i<MaxTree; i++ ) {
        S.TreeNodes[i] = Null;
    }
    S.front = MaxTree;
}

void InitTree() {
    for ( int i=0; i<MaxTree; i++ ) {
        T[i].Left = Null;
        T[i].Right = Null;
    }
}

void Push(int R) {
    if ( S.front ) {
        S.front--;
        S.TreeNodes[S.front] = R;
    } else {
        printf("Stack full\n");
    }
}

int Pop() {
    int output;
    if ( S.front < MaxTree ) {
        output = S.TreeNodes[S.front];
        S.front++;
        return output;
    } else {
        printf("Stack empty");
    }
}

void PostOrderTraversal(int Root) { 
    if ( Root!=Null ) {
        PostOrderTraversal(T[Root].Left);
        PostOrderTraversal(T[Root].Right);
        A[Aindex++] = Root;     // 递归后序遍历需要一个全局变量储存得到的节点号 
    }
}

int main() {
    int N;  // 输入的节点数 
    int Root;   // 标记整个树的根节点 
    int RootFlag = 0;   // 标记整个树的根节点是否已存在 
    int record = 0; // 记录每次push和pop的节点 
    int pushpop = 1;    // 记录上次操作，1代表push，0代表pop 
    InitTree();
    InitStack();

    scanf("%d", &N);    
    for ( int i=0; i<2*N; i++ ) {
        char operation[10]; 
        int R;
        scanf("%s", operation);
        if ( strcmp(operation, "Push") == 0 ) { // 本次操作push 
            scanf("%d", &R);
            if ( RootFlag ) {   // 整个树根节点已存在时 
                if ( pushpop == 1 ) {   // 右儿子 
                    T[record].Left = R;
                } else if ( pushpop == 0 ) {    // 左儿子 
                    T[record].Right = R;
                }
            } else {    // 整个树根节点不存在时
                Root = R;   // 记录整个树的根节点
                RootFlag = 1;                
            }
            Push(R);
            record = R; // 操作完成后更新记录节点为本次节点 
            pushpop = 1;    // 更新操作状态为push 
        } else {    // 本次操作pop 
            R = Pop();
            if ( pushpop == 1 ) {   // 叶节点 
                T[R].Left = Null;
                T[R].Right = Null;
            } else if ( pushpop == 0 ) {

            }
            record = R;
            pushpop = 0;
        }
    }

    PostOrderTraversal(Root);
    if ( N ) {
        printf("%d", A[0]);
        for ( int i=1; i<N; i++ ) {
        printf(" %d", A[i]);
        }
    }

    return 0;
}