用C语言实现二叉树的简单的基本操作

编写程序，用二叉链表存储表示方法，实现二叉树的基本操作。

(1) 根据扩展二叉树的前序遍历序列，建立二叉树。

(2) 根据二叉树的前序和中序遍历序列，构造二叉树。

(3) 实现二叉树的前序、中序和后序遍历，输出遍历结果。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<malloc.h>
#define MAX 20
typedef char DataType;
 //二叉树结点结构声明
typedef struct BTNode
{        
    DataType data;//节点数据
    struct BTNode* Lchild;//左孩子指针
    struct BTNode* Rchild;//右孩子指针
}*BiTree;
 //先序遍历创建二叉树
void createBiTree(BiTree* bt) 
{ 
    DataType ch;
    BiTree q;
    scanf("%c", &ch);
    //输入#,说明该树为空
    if ( ch =='#')
    {
        *bt = NULL;
        return;
    }
    //输入非'#':为根结点分配空间
    q = (BiTree)malloc(sizeof(struct BTNode));
    if (!q)
    {
        printf("分配失败!");
        exit(0);
    }
    //分配成功
    q->data = ch;
    *bt = q;
    createBiTree(&q->Lchild);//递归建立左子树
    createBiTree(&q->Rchild);//递归建立右子树
}
//先序遍历二叉树
void PreOrder(BiTree p)
{ 
    if (p != NULL)
    {
        printf("%c", p->data);//输出遍历到的数据，上面我们设置的char类型，因此这用%c
        PreOrder(p->Lchild);//先序遍历左子树
        PreOrder(p->Rchild);//先序遍历右子树
    }
}
 //中序遍历二叉树
void InOrder(BiTree p) 
{ 
    if (p != NULL)
    {
        InOrder(p->Lchild);//中序遍历左子树
        printf("%c", p->data);
        InOrder(p->Rchild);//中序遍历右子树
    }
}
//后序遍历二叉树
void PostOrder(BiTree p) 
{  
    if (p != NULL)
    {
        PostOrder(p->Lchild);//后序遍历左子树
        PostOrder(p->Rchild);
        printf("%c", p->data);//后序遍历右子树
    }
}
//先序遍历的非递归算法
void Preorder_n(BiTree p) 
{  
    BiTree stack[MAX];//准备一个顺序栈存储结点
    BiTree q;
    int top = 0;  //top=0:栈空
    int i;
    for (i = 0; i < MAX; i++)//初始化栈
        stack[i] = NULL;
    q = p;  //设置q指向待遍历的二叉树
    while (q != NULL)
    {
        printf("%c", q->data);  //先访问根节点
        if (q->Rchild != NULL)
            stack[top++] = q->Rchild;

        if (q->Lchild != NULL)
            q = q->Lchild;
        //结点的左孩子为空,说明该结点的左子树访问结束,进入下一二叉树（出栈）
        else
        {
            if (top > 0)
                q = stack[--top];
            else
                q = NULL;
        }
    }
}
//释放二叉树空间
void release(BiTree t) 
{ 
    if (t != NULL)
    {
        release(t->Lchild);
        release(t->Rchild);
        free(t);
    }
}

int main() {
    BiTree bt = NULL;
    printf("请输入数据（#表示空）：");
    createBiTree(&bt);
    printf("树的先序遍历是:");
    PreOrder(bt);
    printf("\n树的中序遍历是:");
    InOrder(bt);
    printf("\n树的后序遍历是:");
    PostOrder(bt);
    printf("\n先序遍历序列（非递归）:");
    Preorder_n(bt);
    release(bt);
    return 0;
}