二叉树实现--创建+遍历

注意：在进行CreateBiTree的时候，输入的时候 0代表终止，是有讲究的，比如输入3个字符，会加上4个0，2个字符对应3个零，并且对应前序遍历，所以输入2 8 6 0 0 0 0代表根节点2，左节点为8，8的左节点为6.
若是2 8 0 0 6 0 0 ，代表根节点1， 左节点8，右节点为6


#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OVERFLOW -2
#define INFEASIBLE -1
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

typedef int TElemType;
TElemType Nil=0;
typedef struct BiTNode
{
    TElemType data;
    BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree SElemType;//注意！栈中的元素类型是什么！
struct SqStack
{
    SElemType *base;
    SElemType *top;
    int stacksize;
};

int InitStack(SqStack* sq)
{
    sq->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
    if(!sq->base)exit(OVERFLOW);
    sq->top=sq->base;
    sq->stacksize=STACK_INIT_SIZE;
    return OK;
}

int Push(SqStack* sq,BiTree bt)
{
    if(sq->top-sq->base>=sq->stacksize)
    {
        sq->base=(SElemType*)realloc(sq->base,(sq->stacksize+STACKINCREMENT)*sizeof(SElemType));
        if(!sq->base)exit(OVERFLOW);
        sq->top=sq->base+sq->stacksize;
        sq->stacksize+=STACKINCREMENT;
    }
    *sq->top++=bt;
    return OK;
}//Push

int Pop(SqStack* sq,BiTree* bt)
{
    if(sq->base==sq->top)return ERROR;
    *bt=*--sq->top;
    return OK;
}//Pop

int StackEmpty(SqStack* sq)
{
    if(sq->base==sq->top)return OK;
    else return ERROR;
}//StackEmpty


int InitBiTree(BiTree *T)
{
    (*T)=NULL;
    return OK;
}

void CreateBiTree(BiTree *T)
{
    TElemType ch;
    //BiTree *p;
    //*p=*T;
    scanf("%d",&ch);
    if(ch==Nil)
        (*T)=NULL;
    else
    {
        (*T)=(BiTree)malloc(sizeof(BiTNode));
        if(!(*T))
            exit(OVERFLOW);
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
    //return(*p);
}

int BiTreeEmpty(BiTree *T)
{ // 初始条件: 二叉树T存在
    // 操作结果: 若T为空二叉树,则返回TRUE,否则FALSE
    if(*T)
        return FALSE;
    else
        return TRUE;
}

void InOrder(BiTree* root)
{/*中序遍历二叉树的非递归算法*/
    SqStack S;
    BiTree p;
    InitStack(&S);
    p=*root;
    while(p!=NULL||!StackEmpty(&S))
    {
        if(p!=NULL) //根指针进栈，遍历左子树
        {
            Push(&S,p);
            p=p->lchild;
        }
        else
        {/*根指针退栈，访问根节点，遍历右子树*/
            Pop(&S,&p);
            printf("%d ",p->data);
            p=p->rchild;
        }
    }
}

void main()
{
    BiTree T;
    InitBiTree(&T);
    printf("请先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树) ");
    CreateBiTree(&T);
    printf("中序遍历输出结点的值：");
    InOrder(&T);
    putchar(' /n');
}