MOOC 03-树3 Tree Traversals Again

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

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.

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.

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

3 4 2 6 5 1

 小结:

         考察对树的遍历理解，Push序列对应先序遍历序列，Pop序列是中序遍历序列；已知先序序列和中序序列，可知后序遍历序列；具体求解的算法上还是很考察逻辑能力的；说实话，是真想不到能这样递归求解

        具体算法解析：根据给出的Push和Pop序列 可得出先序和中序序列，各自放在数组里；先序的第一个是根，在后序中对应的值存放在数组的最后，再在中序数组中找出根所在的位置，将数组分为左和右，长度可以算出，然后递归的求解左和右的根；

#include 
#include 
#define STR_LEN 5
#define MAXSIZE 30

int Stack[MAXSIZE]; //堆栈
int Top; 

int Pre[MAXSIZE],In[MAXSIZE],Post[MAXSIZE]; //存放先序、中序、后序遍历的数组

void Push( int Stack[],int M ); //入栈

int Pop( int Stack[] );    //出栈

void solve( int PreL,int InL,int PostL,int n );  //核心算法

int main()
{
	//根据给出的Push和Pop顺序得出 先序序列和中序序列，存放在数组中
	int N,M,i;
	scanf("%d",&N);
	
	int iPre,iIn;
	iPre = iIn = 0;
	
	char str[STR_LEN];
	
	for(i=0;i<2*N;i++){
		
		scanf("%s",str);
		
		if(strcmp(str,"Push") == 0){
			
			scanf("%d",&M);
			Pre[iPre] = M;
			iPre++;
			
			Push( Stack,M );
		}else{
			
			In[iIn] = Pop( Stack );
			iIn++;
		}
	}
//	for(i=0;i

#include 
#include 
#include 
#include 
#define STR_LEN 5

typedef struct _TreeNode{ //树结点
	int Data;
	int Tag;  //入栈次数 
}TreeNode;

typedef struct _Stack{ 堆栈
	TreeNode* Array;
	int Top;
	int Len;
}Stack;

Stack* CreateStack( );

void PostTraversal( Stack* S );

bool IsEmpty( Stack* S );

void Push( Stack* S,int M );

void Pop( Stack* S,bool* pfirst );

void FreeStack( Stack* S );

int main()
{
	Stack* S = CreateStack( );
	
	PostTraversal( S );
	
	FreeStack( S );
	
	return 0;
}

//创建空栈,这里没用全局变量，而是练习另一种方式，根据实际需要来malloc堆栈大小
Stack* CreateStack( )
{
	Stack* S = (Stack*)malloc(sizeof(Stack));
	
	scanf("%d",&(S->Len));
	
	S->Array = malloc(S->Len*sizeof(TreeNode));
	
	S->Top = -1; 
	
	return S;
}

//核心算法
void PostTraversal( Stack* S )
{
	int M,N = 2*(S->Len);
	bool first = true;//first是为了满足题目要求的输出格式的标记
	char string[STR_LEN ];
	
	while(N--){
		
		scanf("%s",string);
		
		if(strcmp(string,"Push") == 0){ //入栈
			
			scanf("%d",&M);
			Push( S,M );
		}else{
			
			//出栈时，判别入栈次数，只出入栈2次的结点
			while(!IsEmpty( S ) && S->Array[S->Top].Tag == 2){
				
				Pop( S,&first );//第一个出栈的 打印不带空格，后面的都带空格，满足题目输出要求
			}
			
			//第一次遇到Pop,不出栈，做第二次入栈标记
			if(!IsEmpty( S )){
				
				S->Array[S->Top].Tag = 2;
			}
		}
	}
	
	while(!IsEmpty( S )){
		
		Pop( S,&first );
	}
}

bool IsEmpty( Stack* S )
{
	return S->Top == -1 ? true : false;	
}

void Push( Stack* S,int M )
{
	S->Top++;
	S->Array[S->Top].Data = M;
	S->Array[S->Top].Tag = 1;
}

void Pop( Stack* S,bool* pfirst )
{
	if(*pfirst){
		
		printf("%d",S->Array[S->Top].Data);
		*pfirst = false;
	}else{
		
		printf(" %d",S->Array[S->Top].Data);
	}
	
	S->Top--;
}

void FreeStack( Stack* S )
{
	free(S->Array);
	free(S);
}