C语言非递归后序遍历二叉树

本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码，供大家参考，具体内容如下

法一：实现思路：一个栈 先按 根->右子树->左子树的顺序访问二叉树。访问时不输出。另一个栈存入前一个栈只进栈的结点。

最后输出后一个栈的结点数据。

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
 char element;
 struct TreeNode *left,*right;
}Tree,*BTree;
typedef struct StackNode{
 BTree data;
 struct StackNode *next;
}Stack,*PStack;
typedef struct{
 PStack top;
}LinkStack,*PLinkStack;
//初始化空栈
PLinkStack Init_Stack(void){
 PLinkStack S;
 S=(PLinkStack)malloc(sizeof(LinkStack));
 if(S){
   S->top=NULL;
 }
 return S;
}
//压栈
void Push_Stack(PLinkStack S,BTree T){
 PStack p;
 p=(PStack)malloc(sizeof(Stack));
 p->data=T;
 p->next=S->top;
 S->top=p;
}
//判空
int empty_Stack(PLinkStack S){
 if(S->top){
   return 0;
 }else{
   return 1;
 }
}
//出栈
PStack Pop_Stack(PLinkStack S){
 PStack q;
 if(empty_Stack(S)){
   return S->top;
 }else{
   q=S->top;
   S->top=S->top->next;
 }
 return q;  
}
//销毁栈
void DestroyStack(PLinkStack S){
 PStack del;
 while(S->top!=NULL){
   del=S->top;
   S->top=S->top->next;
   free(del);
 }
 free(S);
}
BTree BuildTree(void){
 char ch;
 BTree node;
 ch=getchar();
 if(ch=='#'){
   node=NULL;
 }else{
   node=(BTree)malloc(sizeof(Tree));
   node->element=ch;
   node->left=BuildTree();
   node->right=BuildTree();
 }
 return node;
}
void NotRecursionPostOrder(BTree T){
 PLinkStack S,CS;
 S=Init_Stack();
 CS=Init_Stack();
 while(T || !empty_Stack(S)){
   if(T){
     Push_Stack(S,T);
     Push_Stack(CS,T);
     T=T->right;
   }else{
     T=Pop_Stack(S)->data;
     T=T->left;
   }
 }
 while(CS->top!=NULL){
   printf("％c",CS->top->data->element);
   CS->top=CS->top->next;
 }
 DestroyStack(CS);
}
int main(void){
 BTree T;
 T=BuildTree();
 NotRecursionPostOrder(T);
 return 0;
}

法二：实现思路。按先序遍历访问每一个结点。存入栈中，当为空时，就出立即栈（第一次出栈）。出栈后应该立即进栈，去访问进栈结点的右结点，这样可以保证先输出左、右结点，再输出根结点。二次进栈利用flag标记。

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
 char element;
 int flag;
 struct TreeNode *left, *right;
}Tree, *BTree;
typedef struct StackNode {
 BTree data;
 struct StackNode *next;
}Stack, *PStack;
typedef struct {
 PStack top;
}LinkStack, *PLinkStack;
//初始化空栈
PLinkStack Init_Stack(void) {
 PLinkStack S = (PLinkStack)malloc(sizeof(LinkStack));
 if (S) {
   S->top = NULL;
 }
 return S;
}
//压栈
void Push_Stack(PLinkStack S, BTree T) {
 PStack p;
 p = (PStack)malloc(sizeof(Stack));
 p->data = T;
 p->next = S->top;
 S->top = p;
}
//判空
int empty_Stack(PLinkStack S) {
 if (S->top) {
   return 0;
 }
 else {
   return 1;
 }
}
//出栈
PStack Pop_Stack(PLinkStack S) {
 PStack q = S->top;
 S->top = S->top->next;
 return q;
}
BTree BuildTree(void) {
 BTree t;
 char ch;
 ch = getchar();
 if (ch == '#') {
   t = NULL;
 }
 else {
   t = (BTree)malloc(sizeof(Tree));
   t->element = ch;
   t->left = BuildTree();
   t->right = BuildTree();
 }
 return t;
}
void DestroyStack(PLinkStack S){
 PStack p;
 while(S->top){
   p=S->top;
   free(p);
   S->top=S->top->next;
 }
}
void NotRecursionPostOrder(BTree T) {
 PLinkStack S;
 S = Init_Stack();
 while (T || !empty_Stack(S)) {
   if (T) {
     T->flag = 0;
     Push_Stack(S, T);
     T = T->left;
   }
   else {
     T = Pop_Stack(S)->data;
     if (T->flag == 0) {
       T->flag = 1;
       Push_Stack(S, T);
       T = T->right;
     }
     else {
       if (T->flag == 1) {
         printf("％c", T->element);
         T = NULL;
       }
     }
   }
 }
 DestroyStack(S);//销毁栈
}
int main(void) {
 BTree T;
 T = BuildTree();
 NotRecursionPostOrder(T);
 return 0;
}

来源：http://blog.csdn.net/chendongqaq/article/details/70832303