关于数据结构中二叉树的中序遍历非递归算法
最近做一个二叉树的中序遍历的非递归算法，但是编译通过就是运行出问题，哪位高手帮我改改错啊~~
我通过debug知道问题一定出在入栈了，因为执行完GoFarLeft(T,s)这个函数后栈的top指针并没有向下移动一个单位，所以再次入栈的时候就把原来栈中的元素覆盖了……但是实在不知道该怎么改，请帮帮忙~~~：）
#include "stdafx.h"#include "stdio.h"#include "malloc.h"#include "stdlib.h"#define OVERFLOW -2#define TRUE 1#define FALSE 0#define ERROR 0#define STACK_INIT_SEZE 100#define STACKINCREMENT 10 typedef struct BiTNode{ char data; struct BiTNode* lchild,*rchild;}BiTNode,*BiTree;typedef struct Stack{ BiTree* base; BiTree* top; int stacksize;}Stack;void InitStack(Stack &s){ s.base = (BiTree*)malloc(STACK_INIT_SEZE*sizeof(BiTNode)); if(!s.base) exit(OVERFLOW); s.top = s.base; s.stacksize = STACK_INIT_SEZE;}int StackEmpty(Stack s){ if(s.top == s.base) return FALSE; else return TRUE;}void Push(Stack &s,BiTree T){ *s.top = T; s.top++;}BiTree Pop(Stack &s){ BiTree e = NULL; if(s.base == s.top) return ERROR; s.top--; e = *s.top; return e;}BiTree CreaBiTree(BiTree &T){ char ch; scanf("%c",&ch); if(ch == 'x') T = NULL; else{ if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data = ch; CreaBiTree(T->lchild); CreaBiTree(T->rchild); } return T;}void visit(char& e){ printf("%c",e);}BiTNode* GoFarLeft(BiTree T,Stack s){ if(!T) return NULL; while(T->lchild){ Push(s,T); T = T->lchild; } return T;}void Inorder_Mid(BiTree T,Stack &s,void(*visit)(char &e)){ BiTree t = GoFarLeft(T,s); while(t){ visit(t->data); if(t->rchild) t = GoFarLeft(t->rchild,s); else { if(!StackEmpty(s)) t = Pop(s); else t = NULL; } }}int main(int argc, char* argv[]){ BiTree tree = CreaBiTree(tree); Stack s; InitStack(s); Inorder_Mid(tree,s,visit); printf("Hello World!\n"); return 0;}1.先序遍历非递归算法#define maxsize 100typedef struct{ Bitree Elem[maxsize]; int top;}SqStack; void PreOrderUnrec(Bitree t){ SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s); p=p->rchild; }//endif }//endwhile }//PreOrderUnrec 2.中序遍历非递归算法#define maxsize 100typedef struct{ Bitree Elem[maxsize]; int top;}SqStack; void InOrderUnrec(Bitree t){ SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历 }//endif }//endwhile }//InOrderUnrec 3.后序遍历非递归算法#define maxsize 100typedef enum tagtype;typedef struct { Bitree ptr; tagtype tag;}stacknode; typedef struct{ stacknode Elem[maxsize]; int top;}SqStack; void PostOrderUnrec(Bitree t){ SqStack s; stacknode x; StackInit(s); p=t; do { while (p!=null) //遍历左子树 { x.ptr = p; x.tag = L; //标记为左子树 push(s,x); p=p->lchild; } while (!StackEmpty(s) && s.Elem[s.top].tag==R) { x = pop(s); p = x.ptr; visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点 }if (!StackEmpty(s)) { s.Elem[s.top].tag =R; //遍历右子树 p=s.Elem[s.top].ptr->rchild; } }while (!StackEmpty(s));}//PostOrderUnrec============================================================= 算法一： Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e)) { //采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack(S); Push(S,T); //根指针进栈 while(!StackEmpty(s)) { while(GetTop(S,p)&&p) Push(S,p->lchild); //向左走到尽头 Pop(S,p); //空指针退栈 if(!StackEmpty(S)) //访问结点，向右一步 { Pop(S,p); if(!Visit(p->data)) return ERROR; Push(S,p->rchild); }//if }//while return OK; }//InOrderTraverse 算法一 ============================================================ ============================================================ 算法二： Status InOrderTraverse(BiTree T, Status (*Visit)(TelemType e)) { //采用二叉链表存储结构，Visit是对数据元素操作的应用函数。 //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 InitStack(S); p=T; while(p||!StackEmpty(S)) { if(p) { Push(S,p); p=p->lchild; }//if 根指针进栈，遍历左子树 else { Pop(S,p); if(!Visit(p->data)) return ERROR; p=p->rchild; }//else 根指针退栈，访问根结点，遍历右子树 }//while }InOrderTraverse() 算法二 ============================================================