关于数据结构中二叉树的中序遍历非递归算法解决思路

关于数据结构中二叉树的中序遍历非递归算法
最近做一个二叉树的中序遍历的非递归算法，但是编译通过就是运行出问题，哪位高手帮我改改错啊~~
我通过debug知道问题一定出在入栈了，因为执行完GoFarLeft(T,s)这个函数后栈的top指针并没有向下移动一个单位，所以再次入栈的时候就把原来栈中的元素覆盖了……但是实在不知道该怎么改，请帮帮忙~~~：）

C/C++ code


#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;
}

------解决方案--------------------

C/C++ code



1.先序遍历非递归算法
#define maxsize 100
typedef 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 100
typedef 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 100
typedef 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() 算法二 
============================================================

关于数据结构中二叉树的中序遍历非递归算法解决思路

相关推荐