理解的关键在于，建立栈，前序遍历第一次遇到就排出，中序遍历第二次遇到排出，后序遍历第三遇到排出，用c时注意指针的使用。
具体思想:一直沿着左支树走到底，并且将经过的节点压入栈，到底时，拿出栈顶元素，判断一下子，是第几次遇到它，如果是第三次就排出，并且把遍历指针设为NULL,否则就取其右孩子继续这个操作。以下是我从c开始实现的栈，树，等结构及其基本操作。然后在此基础上实现这个算法。
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode{
char data;
struct TreeNode* lchild;
struct TreeNode* rchild;
int flag=0;
}TreeNode,*Tree;
typedef struct Stack{
TreeNode* base;
TreeNode* top;
int stack_size;
}Stack;
void Init_Stack(Stack &s){
s.base=(Tree)malloc(100*sizeof(TreeNode));
s.top=s.base;
if(!s.base) return;
s.stack_size=100;
}
void Push_Stack(Stack &s,TreeNode e){
if(!s.base) return;
if(s.top-s.base>=s.stack_size){
s.base=(Tree)realloc(s.base,(s.top-s.base+10)*sizeof(TreeNode));
s.stack_size+=10;
}
*s.top++=e;
}
int Stack_Empty(Stack s){
if(s.top-s.base==0) return 1;
else
return 0;
}
void pop(Stack &s,Tree &e){
if(!Stack_Empty(s)){
e=(--s.top);
}
}
void getTop(Stack s,TreeNode &e){
if(!Stack_Empty){
e=*(s.top-1);
}
}
void Test_Stack(Stack s){
if(!Stack_Empty(s)){
for(Tree i=s.base;i<s.top;i++)
printf("%c",i->data);
}
}
void Create_Tree(Tree &T){
char ch;
scanf(" %c",&ch);
if(ch=='-') T=NULL;
else{
T=(Tree)malloc(sizeof(TreeNode));
if(!T) return ;
else{
T->data=ch;
T->flag=0;
Create_Tree(T->lchild);
Create_Tree(T->rchild);
}
}
}
void Traverse_Tree(Tree T){
if(T){
printf("%c\n",T->data);
Traverse_Tree(T->lchild);
Traverse_Tree(T->rchild);
}else{
return ;
}
}
void ReorderTraverse_Tree(Tree T){
Stack s;
Init_Stack(s);
Tree p=T;
while(p||!Stack_Empty(s)){
if(p){
p->flag++;
Push_Stack(s,*p);
p=p->lchild;
}
else{
pop(s,p);
if(p->flag==2) {
printf(" %c\n",p->data);
p=NULL;
}else{
p->flag++;
Push_Stack(s,*p);
p=s;
}
}
}
}
int main(void){
Tree T=NULL;
Create_Tree(T);
Traverse_Tree(T);
ReorderTraverse_Tree(T);
}
