c语言版本二叉树基本操作示例(先序 递归 非递归)

先序递归遍历：
A B D E C F G
中序递归遍历：
D B E A F C G
后序递归遍历：
D E B F G C A
层序递归遍历：
ABCDEFG
先序非递归遍历：
A B D E C F G
中序非递归遍历：
D B E A F C G
后序非递归遍历：
D E B F G C A
深度：
请按任意键继续. . .
</div>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;

typedef char ElemType;
typedef struct BTNode
{
    ElemType data;
    struct BTNode *leftChild;
    struct BTNode *rightChild;
}BTNode, *BinTree;

typedef BinTree SElemType;

typedef struct{//栈结构定义
    SElemType *base;
    SElemType *top;
    int stacksize;
}SqStack;

BinTree CreateBinTree(BinTree T);
Status Visit(ElemType e);
Status Depth(BinTree T);
Status PreOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status InOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status PostOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status LevelOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));

//定义栈的相关操作
Status InitStack(SqStack *S);
Status DestroyStack(SqStack *S);
Status ClearStack(SqStack *S);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status GetTop(SqStack S,SElemType *e);
Status Push(SqStack *S,SElemType e);
Status Pop(SqStack *S,SElemType *e);
Status StackTraverse(const SqStack *S);

Status PreOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status InOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));
Status PostOrderNoneRecursionTraverse(BinTree T, Status (*Visit)(ElemType e));

int main()
{
    int depth;
    BinTree Tree = NULL;
    Status(*visit)(ElemType e) = Visit; 
    printf_s("请按先序遍历输入二叉树元素（每个结点一个字符，空结点为'='）:\n"); 
    Tree = CreateBinTree(Tree);

    printf_s("\n先序递归遍历：\n");
    PreOrderRecursionTraverse(Tree,visit);
    printf_s("\n中序递归遍历：\n");
    InOrderRecursionTraverse(Tree,visit);
    printf_s("\n后序递归遍历：\n");
    PostOrderRecursionTraverse(Tree,visit);
    printf_s("\n层序递归遍历：\n");
    LevelOrderRecursionTraverse(Tree,visit);

    printf_s("\n先序非递归遍历：\n");
    PreOrderNoneRecursionTraverse(Tree,visit);
    printf_s("\n中序非递归遍历：\n");
    InOrderNoneRecursionTraverse(Tree,visit);
    printf_s("\n后序非递归遍历：\n");
    PostOrderNoneRecursionTraverse(Tree,visit);

    printf_s("\n深度：\n");
    depth = Depth(Tree);
    printf_s("%d\n", depth);
    system("pause");
    return 0;
}

//创建二叉树
BinTree CreateBinTree(BinTree T)
{
    char ch;
    scanf_s("%c", &ch);
    if (ch == '=')
    {
        T = NULL;
    }
    else
    {
        if (!(T=(BTNode *) malloc(sizeof(BTNode))))
        {
            exit(OVERFLOW);
        }
        T->data = ch;    //生成根结点
        T->leftChild = CreateBinTree(T->leftChild);
        T->rightChild = CreateBinTree(T->rightChild);
    }
    return T;
}

//访问二叉树
Status Visit(ElemType e)
{
    if (e == '\0')
    {
        return ERROR;
    }
    else
    {
        printf_s("%c ", e);
    }
    return OK;
}

//先序遍历递归算法
Status PreOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
    if (T)
    {
        if (!Visit(T->data))
        {
            return ERROR;
        }
        PreOrderRecursionTraverse(T->leftChild, Visit);
        PreOrderRecursionTraverse(T->rightChild, Visit);
    }
    return OK;
}

//中序遍历递归算法
Status InOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
    if (T)
    {
        InOrderRecursionTraverse(T->leftChild, Visit);
        if (!Visit(T->data))
        {
            return ERROR;
        }
        InOrderRecursionTraverse(T->rightChild, Visit);
    }
    return OK;
}

//后序遍历递归算法
Status PostOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
    if (T)
    {
        PostOrderRecursionTraverse(T->leftChild, Visit);
        PostOrderRecursionTraverse(T->rightChild, Visit);
        if (!Visit(T->data))
        {
            return ERROR;
        }
    }
    return OK;
}

//层序遍历递归算法
Status LevelOrderRecursionTraverse(BinTree T, Status (*Visit)(ElemType e))
{
    if (T)
    {
        BTNode *Q[100];//假设不溢出
        int front = -1,rear = -1;
        if (T)
        {
            Q[++rear] = T;
            printf_s("%c", T->data);
            while (front != rear)
            {
    &nb