博客

问题描述：

用c语言创建一颗二叉树，用递归方法实现对其进行先序、中序和后序遍历的操作。

先上代码

#include <stdio.h>
#include <stdlib.h>
/*（1）创建一颗二叉树
，用递归方法实现对其进行先序、
中序和后序遍历的操作
*/
//创建二叉树结构体
typedef struct Node
{
    char data;
    struct Node *LChild;
    struct Node *RChild;
}BiTNode,*BiTree;

//结构体初始化
void init(BiTree *bt)
{
    *bt=(BiTree)malloc(sizeof(BiTNode));//?这里为什么要使孩子指向空
    (*bt)->LChild=NULL;
    (*bt)->RChild=NULL;
}

//建立二叉树
void CreateBiTree(BiTree *bt)
{
    char ch;
    printf("请输入数据：\n");
    getchar();
    ch=getchar();
    if(ch=='.') *bt=NULL;
    else
    {
        *bt=(BiTree)malloc(sizeof(BiTNode));//?
        (*bt)->data=ch;
        CreateBiTree(&((*bt)->LChild));
        CreateBiTree(&((*bt)->RChild));
    }
}

//先序遍历二叉树
void PreOrder(BiTree bt)
{
    if(bt!=NULL)
    {
        printf("%c",bt->data);
        PreOrder(bt->LChild);
        PreOrder(bt->RChild);
    }
}

//中序遍历二叉树
void inOrder(BiTree bt)
{
    if(bt!=NULL)
    {
        inOrder(bt->LChild);
        printf("%c",bt->data);
        inOrder(bt->RChild);
    }
}

//后序遍历二叉树
void PostOrder(BiTree bt)
{
     if(bt!=NULL)
    {
        PostOrder(bt->LChild);
        PostOrder(bt->RChild);
        printf("%c",bt->data);

    }
}
int main()
{
    BiTree bt;
    init(&bt);
    int i;
     while(1)
    {
        printf("输入1：创建二叉树\n");
        printf("输入2：先序遍历二叉树\n");
        printf("输入3：中序遍历二叉树\n");
        printf("输入4：后序遍历二叉树\n");
        printf("输入0：退出\n");
        printf("请输入要执行的操作：\n");
        scanf("%d",&i);
        switch(i)
        {
            case 1:
              CreateBiTree(&bt);
              break;

            case 2:
              PreOrder(bt);
              printf("\n");
               break;

            case 3:

                inOrder(bt);
                printf("\n");
               break;
            case 4:

                PostOrder(bt);
                printf("\n");
               break;

            case 0:
                break;
        }
        if(i==0)
            break;
    }

}

这里在写的过程中，我有两点疑问：

1、二叉树的初始化是否多余，不初始化的后果是什么？

2、在为bitree申请空间时，可以在后面直接写成

*bt=malloc(sizeof(BiTree));


这两个问题我都分别试了一下，和运行了一下。

第一个： 如果注释掉初始化语句，程序依然会执行，运行也一切正常没有错误，然后问老师，老师说初始化是为了语言的严谨，但这里具体为什么需要初始化操作，以及不初始化，也可以执行成功具体原因未知。

第二个： 在申请空间时不能那么些，程序会直接异常终止，具体原因，猜测是因为malloc语句后面不能跟结构体指针类型。

以上的问题，欢迎大牛帮我解答。