程序代码：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT   10
#define QUEUE_LENGTH 100

struct BiTree
{
    char data;
    struct BiTree *lchild;
    struct BiTree *rchild;
};
typedef struct BiTree BiTree;

struct SqStack
{
    BiTree *base;
    BiTree *top;
    int stacksize;
};
typedef struct SqStack SqStack;

struct Queue
{
    BiTree *data[QUEUE_LENGTH+1];
    int front;
    int rear;
};
typedef struct Queue Queue;

BiTree *CreateBiTree();
char Menu();
void PreOrderTraverse_Re(BiTree *p0);
void InOrderTraverse_Re(BiTree *p0);
void PostOrderTraverse_Re(BiTree *p0);
SqStack *InitStack();
void Push(SqStack *S,BiTree e);
int StackEmpty(SqStack *S);
BiTree Pop(SqStack *S);
void PreOrder(BiTree *p0);
void InOrder(BiTree *p0);
void PostOrder(BiTree *p0);
void InitQueue(Queue &q);
void EnQueue(Queue &q,BiTree *x);
int EmptyQueue(Queue &q);
int DeQueue(Queue &q,BiTree &p);
void LevelOrd(BiTree *r);

void main()
{
    char ch;
    BiTree *Tree;
    while(1)
    {
        ch=Menu();
        switch(ch)
        {
            case'1':
            {
                Tree=CreateBiTree();
                printf("The binary tree has been created!\n");
                break;
            }
            case'2':
            {
                PreOrderTraverse_Re(Tree);
                printf("That is the result by Preord with recursion!\n");
                break;
            }
            case'3':
            {
                InOrderTraverse_Re(Tree);
                printf("That is the result by Inord with recursion!\n");
                break;
            }
            case'4':
            {
                PostOrderTraverse_Re(Tree);
                printf("That is the result by Postord with recursion!\n");
                break;
            }
            case'5':
            {
                PreOrder(Tree);
                printf("That is the result by Preord without recursion!\n");
                break;
            }
            case'6':
            {
                InOrder(Tree);
                printf("That is the result by Inord without recursion!\n");
                break;
            }
            case'7':
            {
                PostOrder(Tree);
                printf("That is the result by Postord without recursion!\n");
                break;
            }
            case'8':
            {
                LevelOrd(Tree);
                printf("That is the result by Levelord!\n");
                break;
            }
            default:exit(0);
        }
    }
}

char Menu()
{
    char ch;
    printf("\nThe operation of traverse BiTree!\n");
    printf("1.Creat binary tree\n");
    printf("2.Traverse binary tree by Preord with recursion\n");
    printf("3.Traverse binary tree by Inord with recursion\n");
    printf("4.Traverse binary tree by Postord with recursion\n");
    printf("5.Traverse binary tree by Preord without recursion\n");
    printf("6.Traverse binary tree by Inord without recursion\n");
    printf("7.Traverse binary tree by Postord without recursion\n");
    printf("8.Traverse binary tree by Levelord\n");
    printf("9.Destory binary tree\n");
    printf("Please input your option:");
    scanf(" %c",&ch);
    getchar();
    return ch;
}

BiTree *CreateBiTree()
{
    char ch;
    BiTree *T;
    scanf("%c",&ch);   
    if(ch==' ')
        T=NULL;
    else
    {
        T=(BiTree *)malloc(sizeof(BiTree));
        T->data=ch;
        T->lchild=CreateBiTree();
        T->rchild=CreateBiTree();
    }
    return (T);
}

void PreOrderTraverse_Re(BiTree *p0)
{
    if(p0)
    {
        printf("%c\n",p0->data);
        PreOrderTraverse_Re(p0->lchild);
        PreOrderTraverse_Re(p0->rchild);
    }
}

void InOrderTraverse_Re(BiTree *p0)
{
    if(p0)
    {
        InOrderTraverse_Re(p0->lchild);
        printf("%c\n",p0->data);
        InOrderTraverse_Re(p0->rchild);
    }
}

void PostOrderTraverse_Re(BiTree *p0)
{
    if(p0)
    {
        PostOrderTraverse_Re(p0->lchild);
        PostOrderTraverse_Re(p0->rchild);
        printf("%c\n",p0->data);
    }
}

SqStack *InitStack()
{
    SqStack *S;
    S=(SqStack *)malloc(sizeof(SqStack));
    S->base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));
    S->top=S->base;
    S->stacksize=STACK_INIT_SIZE;
    return S;
}

void Push(SqStack *S,BiTree e)
{
    if(S->top-S->base>=S->stacksize)
    {
        S->base=(BiTree*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTree));
        S->top=S->base+S->stacksize;
        S->stacksize+=STACKINCREMENT;
    }
    *(S->top)=e;
    S->top++;
}

int StackEmpty(SqStack *S)
{
    if(S->top==S->base)
        return 1;
    else
        return 0;
}

BiTree Pop(SqStack *S)
{
    S->top --;
    return *S->top;

}

void PreOrder(BiTree *p0)
{
    SqStack *S;
    BiTree *p=p0;
    S=InitStack();
    if(p0)
        Push(S,*p);
    while(!StackEmpty(S))
    {
        p=(BiTree *)malloc(sizeof(BiTree));
        *p=Pop(S);
        printf("%c\n",p->data);
        if(p->rchild)
            Push(S,*p->rchild);
        if(p->lchild)
            Push(S,*p->lchild);
    }
}


void InOrder(BiTree *p0)
{
    SqStack *S;
    BiTree *p=p0;
    S=InitStack();
    while(p||!StackEmpty(S))
    {
        if(p)
        {
            Push(S,*p);
            p=p->lchild;
        }
        else
        {
            p=(BiTree *)malloc(sizeof(BiTree));
            *p=Pop(S);
            printf("%c\n",p->data);
            p=p->rchild;
        }
    }
}


void PostOrder(BiTree *p0)
{
    SqStack *S;
    BiTree p;
    BiTree *l,*r;
    S=InitStack();
    Push(S,*p0);
    while(!StackEmpty(S))
    {
        p=Pop(S);
        l=p.lchild;
        r=p.rchild;
        if(l==NULL&&r==NULL)
            printf("%c\n", p.data);
        else
        {
            p.lchild=NULL;
            p.rchild=NULL;
            Push(S,p);
            if(r!=NULL)
                Push(S,*r);
            if(l!=NULL)
                Push(S,*l);
        }
     }
}

void InitQueue(Queue &q)
{
    q.front=0;
    q.rear=0;
}

void EnQueue(Queue &q,BiTree *x)
{
    if(q.rear==QUEUE_LENGTH)
        printf("overflow");
    q.rear++;
    q.data[q.rear]=x;
}

int EmptyQueue(Queue &q)
{
    if(q.rear==q.front)
        return 1;
    else
        return 0;
}

int DeQueue(Queue &q,BiTree *p)
{
    if(EmptyQueue(q))
    {
        printf("underflow");
        return 0;
    }
    else
    {
        p=q.data[q.front+1];// printf("%c",x);
        q.front++;
    }
    if(EmptyQueue(q))
    {
        q.front=0;
        q.rear=0;
    }
    return 1;
}

void LevelOrd(BiTree *r)
{
    Queue q;
    InitQueue(q);
    BiTree *p,*p1,*p2;
    p=r;//(Tree)malloc(sizeof(TreeNode));
    if(p)
        EnQueue(q,p);
    while(!EmptyQueue(q))
    {
        DeQueue(q,p);
        printf("%c\n",p->data);
        p1=p->lchild;
        p2=p->rchild;
        if(p1)
            EnQueue(q,p1);
        if(p2)
            EnQueue(q,p2);
    }
}