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

www.MyException.Cn  网友分享于：2013-03-01  浏览：24次

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() 算法二
============================================================```