非递归先序遍历二叉树-蒲公英云

非递归先序遍历二叉树

/*非递归先序遍历二叉树*/
#include<stdio.h>
#define maxsize 100
typedef char datatype;
/*二叉链表类型定义*/
typedef struct Binnode
{
    datatype data;                   /*数据域*/
    struct BinNode* lchild,*rchild;  /*指向左、右孩子的指针*/
}BinNode,*Bintree;
/*按先序创建二叉树*/
Bintree CreateTree(Bintree T)
{
    datatype ch;
    scanf("%c",&ch);
    if(ch=='#')
        return NULL;
    else
    {
        T=(Bintree)malloc(sizeof(BinNode));
        T->data=ch;
        T->lchild=CreateTree(T->lchild);/*创建左子树*/
        T->rchild=CreateTree(T->rchild);/*创建右子树*/
        return T;
    }
}
/*非递归先序遍历二叉树*/
void preorder(Bintree T)
{
    Bintree st[maxsize],p;
    int top=-1;
    if(T!=NULL)
    {
        top++;                          /*根节点进栈*/
        st[top]=T;
        while(top>-1)                   /*栈不为空时循环*/
        {
            p=st[top];                  /*退栈并访问该节点*/
            top--;
            printf("%c ",p->data);
            if(p->rchild!=NULL)         /*右孩子节点进栈*/
            {
                top++;
                st[top]=p->rchild;
            }
            if(p->lchild!=NULL)         /*左孩子节点进栈*/
            {
                top++;
                st[top]=p->lchild;
            }
        }printf("\n");
    }
}
main()
{
    Bintree t;
    printf("请按先序的方式输入二叉树的结点元素（注：#表示节点为空）:");
    t=CreateTree(t);
    printf("非递归先序遍历二叉树:");
    preorder(t);
}