Tree Traversals Again(根据前序，中序，确定后序顺序）

题目的大意是：进行一系列的操作push,pop。来确定后序遍历的顺序

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 t

Sample Input:

Push 1

Push 2

Push 3

Pop

Push 4

Pop

Push 5

Push 6

Pop

Sample Output:

3 4 2 6 5 1

思路：push过程就是前序遍历，pop过程就是中序遍历，再写一个根据前序和中序遍历确定后序遍历的算法。

2.取先序序列中的第一个元素，该元素为根结点

3.根据根结点在中序序列中查找根结点的位置，从而得到该树左子树结点个数（L）与右子树的结点个数（R）

4.在后序序列数组中，第0到第L个元素为左子树，第L+1到第L+R个元素为右子树，最后一个元素为根结点

#include<cstdio>

#include<stack>

#include<iostream>

#include<string>

using namespace std;

#define MAX 30

int preOrder[MAX];

int inOrder[MAX];

int postOrder[MAX];

//根据前序和中序划分，来确定后序遍历。前序的第一个数字为根结点，

//找到根结点root在中序数组位置，中序数组中root左边为根结点左子树，右边为右子树

void Solve(int preL,int inL,int postL,int n){

  if(n==)return;

  if(n==){

    postOrder[postL]=preOrder[preL];

  }

  int root=preOrder[preL];

  postOrder[postL+n-]=root;

  int i,R,L;

  for(i=;i<n;i++){

    if(root==inOrder[inL+i])break;

  }

  L=i,R=n-i-;                  //L为左子树结点数目，R为右子树结点数目

  Solve(preL+,inL,postL,L);    //确定后序数组中根结点root左边的排列顺序

  Solve(preL+L+,inL+L+,postL+L,R);

}

int main(){

  int n;

  for(int i=;i<MAX;i++){

    preOrder[i]=;

    inOrder[i]=;

    postOrder[i]=;

  }

  stack<int> s;

  cin>>n;

  string str;

  int data;

  int index=,pos=;

  for(int i=;i<*n;i++){

    cin>>str;

    if(str=="Push"){      //push代表前序遍历

     cin>>data;

    s.push(data);

      preOrder[index++]=data;

    }else if(str=="Pop"){ //pop为中序遍历

      inOrder[pos++]=s.top();

      s.pop();

    }

  }

  Solve(,,,n);

  for(int i=;i<n;i++){

    if(i>)printf(" ");

    printf("%d",postOrder[i]);

  }

  return ;

}

巴特西

Tree Traversals Again(根据前序，中序，确定后序顺序）

Input Specification:

Output Specification:

Sample Input:

Sample Output:

最新文章

热门文章