C语言二叉树的创建、(先中后序)遍历以及存在的问题

 1 #include<stdlib.h>
 2 #include<stdio.h>
 3 
 4 #define True 1
 5 #define False 0
 6 
 7 typedef char TElemType;
 8 typedef struct TNode {
 9     TElemType data;
10     struct    TNode *lchild, *rchild;
11 }TNode,*BinTree;
12 
13 int CreateBinTree(BinTree T)
14 {
15     TElemType ch;
16     scanf("%c",&ch);
17     if (ch == '#')
18         T = NULL;
19     else 
20     {
21         T = (TNode *)malloc(sizeof(TNode));
22         T->data = ch;
23         CreateBinTree(T->lchild);//创建左子树
24         CreateBinTree(T->rchild);//创建右子树
25     }
26     return 0;
27 }
28 
29 void PreOrderTraverse(BinTree T)     //先序遍历
30 {
31     if (T!=NULL)
32     {
33         //        Visit(T->data);
34         printf("%c", T->data);
35         PreOrderTraverse(T->lchild);
36         PreOrderTraverse(T->rchild);
37     }
38 }
39 
40 void InOrderTraverse(BinTree T)      //中序遍历
41 {
42     if (T != NULL)
43     {
44         InOrderTraverse(T->lchild);
45 //        Visit(T->data);
46         printf("%c", T->data);
47         InOrderTraverse(T->rchild);
48     }
49 }
50 
51 void PostOrderTraverse(BinTree T)    //后序遍历
52 {
53     if (T != NULL)
54     {
55         PostOrderTraverse(T->lchild);
56         PostOrderTraverse(T->rchild);
57         printf("%c", T->data);
58     }
59 }
60 
61 
62 
63 int main()
64 {
65     BinTree a;
66     CreateBinTree(a);
67     PreOrderTraverse(a);
68     return 0;
69 }

满怀憧憬写完了代码，让我绝望的是，一运行就出现了问题：能够输入树的信息，但是无法输出，因此，我认为是二叉树的遍历函数出了问题，但是又无法单单从代码看出

于是，我就写了如下代码，自行构建了一个二叉树：

 1         BinTree a=NULL;
 2     BinTree b = NULL;
 3     BinTree c = NULL;
 4     a = (BinTree)malloc(sizeof(TNode));
 5     b = (BinTree)malloc(sizeof(TNode));
 6     c = (BinTree)malloc(sizeof(TNode));
 7     a->rchild = b;
 8     b->lchild = c;
 9     a->lchild = NULL;
10     b->rchild = NULL;
11     c->lchild = NULL;
12     c->rchild = NULL;
13     a->data = 'A';
14     b->data = 'B';
15     c->data = 'C';
16 
17     PreOrderTraverse(a);
18     printf("\n");
19     InOrderTraverse(a);
20     printf("\n");
21     PostOrderTraverse(a);

结果却成功地输出了自行构造的二叉树。由此可见我的遍历函数并没有问题，因此必定是二叉树的create函数出了问题，但是为何我却能够输入呢？

我在网上查了查相关的代码，发现一个采用引用值传递的算法，将create函数修改如下：

int CreateBinTree(BinTree &T)  //引用值传递
{
    TElemType ch;
    scanf_s("%c",&ch,sizeof(ch));
    if (ch == '#')
        T = NULL;
    else 
    {
        T = (TNode *)malloc(sizeof(TNode));
        T->data = ch;
        CreateBinTree(T->lchild);//构造左子树
        CreateBinTree(T->rchild);//构造右子树
    }
    return 0;
}

尝试着运行，成功了！

？？？这时我感到很奇怪。

为啥之前的不行呢？

这时，又看到使用BinTree作返回值的算法，修改后如下：

 1 BinTree creatBTree()   //以BinTree为返回值
 2 {
 3     TElemType ch;
 4     BinTree T;
 5     scanf_s("%c", &ch, sizeof(ch));
 6     if (ch == '#')
 7         T = NULL;
 8     else
 9     {
10         T = (TNode *)malloc(sizeof(TNode));
11         T->data = ch;
12         T->lchild=creatBTree();//构造左子树
13         T->rchild=creatBTree();//构造右子树
14     }
15     return T;
16 }

毫无疑问，同样能成功实现需求。

那么问题来了?为什么之前的不行呢？

因为我之前用的int CreateBinTree(BinTree T)；是单纯的值传递，就像swap（a，b）无法交换两值那样，虽然的确通过动态内存分配和链表构造了一个二叉树，但是在主函数中定义的a的值并没有任何改变，因此在遍历a时会毫无反应。

而引用作函数参数传递，能够直接对a的值进行改变，以a为根节点构建二叉树。

以BinTree为返回值就更不用说了，直接将新构建的二叉树赋值给a。

为了尝试地址为参数传递是否可行，写了如下函数

int CreateRoot(BinTree *T)，细节如下：

1 int CreateBinTree(BinTree *T)
2 {
3     TElemType ch;
4     scanf("%c",&ch);
5     *T=(BinTree)malloc(sizeof(TNode));
6     (*T)->data=ch;
7     (*T)->lchild=NULL;
8     (*T)->rchild=NULL;//设置左右孩子为NULL，以防陷入无限循环
9  }

能够成功插入根节点！

看到这里，便可以轻松完成递归构造函数：

 1 int CreateBinTree(BinTree *T)
 2 {
 3     TElemType ch;
 4     scanf("%c",&ch);
 5     if (ch == '#')
 6         *T = NULL;  //若写成T=NULL ，可能会陷入无限循环
 7     else 
 8     {
 9         *T = (BinTree)malloc(sizeof(TNode));
10         (*T)->data = ch;
11         CreateBinTree(&(*T)->lchild);//left child
12         CreateBinTree(&(*T)->rchild);//right child
13     }
14     return 0;
15 }
16 //在本函数中最需要注意的就是，所有地方都必须以(*T)的形式出现

写完这个随笔，对二叉树的理解增进了不少，今天的学习给我带来了不小的回报，继续努力~

C语言二叉树的创建、(先中后序)遍历以及存在的问题

推荐阅读