#include "stdio.h"
#include "iostream.h"
#include "malloc.h"
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 100
typedef int Status;
typedef int Elemtype;

typedef struct BiNode
{
    Elemtype data;
    struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

typedef struct 
{
    BiNode *a[MAXSIZE];
    int top;
}SqStack;
Status TreeCreated=FALSE;

Status CreateBiTree(BiTree *T);
void NRlnOrderTraverse(BiTree T);
void Push(SqStack *s,BiNode *x);
BiNode *Pop(SqStack *s);

void main()
{
    int choice=0,flag;
    Status leave=FALSE;
    BiNode *BT;
    cout<<"========利用栈实现非递归遍历演示程序========"<<endl;
    do {
        cout<<"1.创建一个二叉树，按先序遍历结果输入，空用0表示"<<endl;
        cout<<"2.中序遍历二叉树，非递归方式遍历二叉树"<<endl;
        cout<<"0.Quit"<<endl;
        cout<<"------Input your selection:";
        cin>>choice;
        switch(choice)
        {
        case 1:
            if (TreeCreated)
            {
                cout<<"Sorry,the tree has been already created!"<<endl;
                break;
            }
            cout<<"Please put in number!"<<endl;
            flag=CreateBiTree(&BT);
            if (flag==OK) 
            {
                cout<<"Okey,Now a TREE named BT is created..."<<endl;
                TreeCreated=TRUE;
            }
            break;
        case 2:
            cout<<"In NROrder:";
            NRlnOrderTraverse(BT);
            cout<<endl;
            break;
        case 0:
            leave=TRUE;
            break;
        }
    } while(!leave);
    cout<<"Thanks for using,bye-bye!"<<endl;
}

Status CreateBiTree(BiTree *T)
{
    int ch=0;
    cin>>ch;
    if (ch==0)
        (*T)=NULL;
    else
    {
        (*T)=(BiTree)malloc(sizeof(BiNode));
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
    return OK;
}

void NRlnOrderTraverse(BiTree T)
{
    SqStack s;
    BiNode *p;
    s.top=0;
    Push(&s,T);
    while (s.top!=0)
    {
        while (s.a[s.top]!=NULL)
        {
            p=s.a[s.top];
            Push(&s,p->lchild);
        }
        p=Pop(&s);
        if(s.top!=0)
        {
            p=Pop(&s);
            cout<<p->data<<"   ";
            Push(&s,p->rchild);
        }
    }
    cout<<endl;
}    
void Push(SqStack *s,BiNode *x)
{
    if (s->top==MAXSIZE) 
        cout<<"stack overflow!"<<endl;
    else
    {
        s->top++;
        s->a[s->top]=x;
    }
}
BiNode *Pop(SqStack *s)
{
    BiNode *x;
    if (s->top==0)
    {
        cout<<"stack underflow!"<<endl;
        return (NULL);
    }
    else
    {
        x=s->a[s->top];
        s->top--;
        return (x);
    }
}

其中这段代码
void NRlnOrderTraverse(BiTree T)
{
    SqStack s;
    BiNode *p;
    s.top=0;
    Push(&s,T);
    while (s.top!=0)
    {
        while (s.a[s.top]!=NULL)
        {
            p=s.a[s.top];
            Push(&s,p->lchild);
        }
        p=Pop(&s);
        if(s.top!=0)
        {
            p=Pop(&s);
            cout<<p->data<<"   ";
            Push(&s,p->rchild);
        }
    }
    cout<<endl;
}   
不是很懂，求解释啊~~

Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType))
 { // 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。算法6.3
   // 中序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit
   SqStack S;
   InitStack(S);
   while(T||!StackEmpty(S))
   {
     if(T)
     { // 根指针进栈,遍历左子树
       Push(S,T);
       T=T->lchild;
     }
     else
     { // 根指针退栈,访问根结点,遍历右子树
       Pop(S,T);
       if(!Visit(T->data))
         return ERROR;
       T=T->rchild;
     }
   }
   printf("\n");
   return OK;
 }
里面的栈队代码自己写吧，或者直接利用系统的栈函数，泛型编程看看。。。。

中跟遍历还是好一点。。
后跟有点麻烦。。。。

因为你完全可以用栈按递归中跟遍历的过程出搞。。
方式是一模一样，只要你懂了递归的思想了
这样循环知道遍历完。。。。。。。、
自己用几个数据演示一遍更好理解，这就是我前几天学习后跟遍历的方法。。。

学习数据结构的孩子加油

[ 本帖最后由 小鱼儿c 于 2011-11-1 11:08 编辑 ]