二叉树的中序非递归遍历思想

#include<stdio.h>

#include<stdlib.h>

#define OK 1

#define  ERROR 0

typedef struct node

{

    int data;

    struct node *lchild;

    struct node *rchild;

} Node,Tree;

/*

www.quzhuanpan.com

解释全来自去转盘网，转载请告知

*/

typedef Node *ElemType;

typedef Tree *AnoElemType;

void creatBITree(AnoElemType &T,int array[],int n,int i)//i应该从零开始

{

    if(array[0]==‘0‘||i>n) T=NULL;

    else

    {

        if(!(T=(ElemType)malloc(sizeof(node))))

        {

            exit(0);

        }

        T->data=array[i];

        creatBITree(T->lchild,array,n,i*2+1);

        creatBITree(T->rchild,array,n,i*2+2);

    }

}

void InOrderTraverse(AnoElemType &T)

{

    AnoElemType  p;

    ElemType data[100];

    int top=0;

    p=T;

    while(p||top!=0)

    {

        while(p!=NULL)

        {

            data[top++]=p;

            p=p->lchild ;

        }

        p=data[--top];

        printf("%d ",p->data );

        p=p->rchild ;

    }

}

int main(void)

{

    AnoElemType T;

    int array[1000], n,i;

    scanf("%d",&n);

    for(i=0; i<n; i++)

    {

        scanf("%d",&array[i]);

    }

    creatBITree(T,array,n-1,0);

    InOrderTraverse(T);

    return 0;

}

二叉树的中序非递归遍历思想

原文：http://5912119.blog.51cto.com/5902119/1734721