03-树3 Tree Traversals Again（树的遍历）

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.

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

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

入栈是前序遍历，弹出是中序遍历，输出要求后续遍历。

    1)后序遍历递归写法

/**
    1)后序遍历递归写法
*/

#include <iostream>
#include <stack>
using namespace std;

const int maxn=35;
typedef int Tree;
#define Null -1
struct TNode
{
    Tree left,right;
    TNode()
    {
        left=right=Null;
    }
}tree[maxn];
Tree CreateTree(TNode *T);
void BehTraver(Tree root);
int flag=0;

int main()
{
    Tree root=CreateTree(tree);
    BehTraver(root);
    return 0;
}

Tree CreateTree(TNode *T)
{
    int root=Null;
    int n;
    cin >> n;
    getchar(); //吸收掉换行符
    string str;
    int index,pre=Null; //index存储结点的下标，pre存储结点的孩子节点的下标
    stack<int> st;
    int flag=0,coun=0; //当第一次Push与Pop的数目相等时，此时Pop掉的结点下标就是根节点
    for(int i=1;i<=2*n;++i)
    {
        getline(cin,str);
        if(str.substr(0,3)=="Pus")
        {
            ++coun;
            index=0;
            for(int j=5;j<(int)str.size();++j) //得到结点的下标
                index=index*10+str[j]-'0';
            if(pre!=Null&&flag==0) //如果非首结点且上一个输入是Push
                T[pre].left=index;
            else if(pre!=Null&&flag==1) //如果上一个节点是Pop
                T[pre].right=index;
            pre=index; //要将此节点的下标赋给pre存储
            st.push(index);
            flag=0;
        }
        else if(str.substr(0,3)=="Pop")
        {
            --coun;
            pre=st.top();
            st.pop();
            flag=1;
        }
        if(coun==0&&root==Null)
            root=pre;
    }
    return root;
}

void BehTraver(Tree root)
{
    if(root!=Null)
    {
        BehTraver(tree[root].left);
        BehTraver(tree[root].right);
        if(flag==0)
            flag=1;
        else
            cout << ' ';
        cout << root;
    }
}
*/

    2)后序遍历非递归写法

///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(Tree root)
{
    stack<int> st;
    int fir=root,sec;
    while(!st.empty()||fir!=Null)
    {
        while(fir!=Null)
        {
            st.push(fir);
            st.push(fir);
            fir=tree[fir].left;
        }
        if(!st.empty())
            fir=st.top();
        st.pop();
        if(!st.empty())
            sec=st.top();
        else    //此处要注意，如果是树根，则树根取出来后栈就空了，所以此处要特判一下
        {
            if(flag==0)
                flag=1;
            else
                cout << ' ';
            cout << fir;
            break;
        }

        if(fir==sec)
            fir=tree[fir].right;
        else //第二次结点出栈后，打印输出
        {
            if(flag==0)
                flag=1;
            else
                cout << ' ';
            cout << fir;
            fir=Null;   //打印节点后，要把fir赋为Null，否则会造成多余的结点从while循环入栈
        }
    }
}

/**
    2)后序遍历非递归写法
*/

#include <iostream>
#include <stack>
using namespace std;

const int maxn=35;
typedef int Tree;
#define Null -1
struct TNode
{
    Tree left,right;
    TNode()
    {
        left=right=Null;
    }
}tree[maxn];
Tree CreateTree(TNode *T);
void BehTraver(Tree root);
int flag=0;

int main()
{
    Tree root=CreateTree(tree);
    BehTraver(root);
    return 0;
}

Tree CreateTree(TNode *T)
{
    int root=Null;
    int n;
    cin >> n;
    getchar();
    string str;
    int index,pre=Null;
    stack<int> st;
    int flag=0,coun=0;
    for(int i=1;i<=2*n;++i)
    {
        getline(cin,str);
        if(str.substr(0,3)=="Pus")
        {
            ++coun;
            index=0;
            for(int j=5;j<(int)str.size();++j)
                index=index*10+str[j]-'0';
            if(pre!=Null&&flag==0)
                T[pre].left=index;
            else if(pre!=Null&&flag==1)
                T[pre].right=index;
            pre=index;
            st.push(index);
            flag=0;
        }
        else if(str.substr(0,3)=="Pop")
        {
            --coun;
            pre=st.top();
            st.pop();
            flag=1;
        }
        if(coun==0&&root==Null)
            root=pre;
    }
    return root;
}

///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(Tree root)
{
    stack<int> st;
    int fir=root,sec;
    while(!st.empty()||fir!=Null)
    {
        while(fir!=Null)
        {
            st.push(fir); 
            st.push(fir);
            fir=tree[fir].left;
        }
        if(!st.empty())
            fir=st.top();
        st.pop();
        if(!st.empty())
            sec=st.top();
        else    //此处要注意，如果是树根，则树根取出来后栈就空了，所以此处要特判一下
        {
            if(flag==0)
                flag=1;
            else
                cout << ' ';
            cout << fir;
            break;
        }

        if(fir==sec)
            fir=tree[fir].right;
        else //第二次结点出栈后，打印输出
        {
            if(flag==0)
                flag=1;
            else
                cout << ' ';
            cout << fir;
            fir=Null;   //打印节点后，要把fir赋为Null，否则会造成多余的结点从while循环入栈
        }
    }
}