二叉树的创建

对于创建一棵二叉树，首先想到的方法是使用递归思想进行。这里，采用先序递归创建二叉树。

首先介绍下自己写的二叉树的定义：

1 typedef int TElementType;
2 
3 typedef struct BiTNode
4 {
5     TElementType data;
6     BiTNode* leftChild,*rightChild;
7 } BiTNode,*BiTree;

1.先序递归创建二叉树

先附上自己最开始写的代码：

 1 //太丑了！！
 2 void CreateTreeDLR(BiTree _biTree)
 3 {
 4     TElementType data;
 5     cin>>data;
 6     if(data==0)
 7     {
 8        _biTree=NULL;
 9         return;
10     }
11     _biTree->data=data;
12     _biTree->leftChild=new BiTNode();
13     FillTreeDLR(_biTree->leftChild);
14     _biTree->rightChild=new BiTNode();
15     FillTreeDLR(_biTree->rightChild);
16 }

因为需要传入一个BiTree类型，所以需要在外部初始化一个BiTree类型。这时候问题就来了，但出现终止条件0时，虽然能正常结束递归，但_biTree=NULL语句对外层的BiTree对象根本不起作用。所以会导致出现一个不含值的BiTree类型。就会出现如下情况：

input:1 2 4 0 0 5 0 0 3 6 0 0 7 0 0

output:1 2 4 0 0 5 0 0 3 6 0 0 7 0 0 （使用先序遍历）

输出结果出现0，完全不是我们想要的。

既然知道了问题所在，那么进行如下改进：

 1 //传址的方法，也解决了因为传值需要在外部初始化BiTNode的问题
 2 //怎么一开始就转不过来！！
 3 void FillTreeDLR(BiTree &_biTree)
 4 {
 5     TElementType data;
 6     cin>>data;
 7     if(data==0)
 8     {
 9        _biTree=NULL;
10     }
11     else
12     {
13     _biTree=new BiTNode();
14     _biTree->data=data;
15     FillTreeDLR(_biTree->leftChild);
16     FillTreeDLR(_biTree->rightChild);
17     }
18 }

当然，如果不想使用传入参数，可以采用返回值得形式。

 1 //这个代码貌似还是有点违反“不能返回局部初始化的指针”这一原则
 2 BiTNode* CreateTreeDLR()
 3 {
 4     TElementType data;
 5     cin>>data;
 6     if(data==0)
 7     {
 8         return NULL;
 9     }
10     BiTNode* root=new BiTNode();
11     root->data=data;
12     root->leftChild=CreateTreeDLR();
13     root->rightChild=CreateTreeDLR();
14     return root;
15 }

执行结果符合我们的需求：

input:1 2 4 0 0 5 0 0 3 6 0 0 7 0 0

output:1 2 4 5 3 6 7 （使用先序遍历）

2.非递归创建二叉树

非递归创建二叉树的思想跟层序遍历的思想类似，利用到队列，当弹出一个结点时，对当前结点进行赋值，如果值为空（这里值是0），则表明该结点无后续子结点；否则，将该结点的左右孩子入队列。依此过程，直到队列为空，结束。

但是在一开始创建二叉树的时候，还是因为对指针的掌握不够，还是犯了将指针进行传值操作，后面使用指针的指针来解决这问题的。这一点在以后的学习中再怎么强调也不为过啊，指针真的把我绕晕了。

首先，重新定义了下二叉树。

1 typedef struct BiTNode
2 {
3     TElementType data;
4     BiTNode* leftChild,*rightChild;
5 } BiTNode,*BiTree,**BiTreePtr;/*新添加指针的指针*/

下面是我实现的非递归创建二叉树的算法，说实话，对于下面指针的指针的用法，要如何改进优化，我晕乎着，反正是看不出来了。

 1 void CreateTreeNonRecur(BiTree& root)
 2 {
 3     queue<BiTreePtr> q;
 4     TElementType data;
 5     q.push(&root);
 6     while(q.size()!=0)
 7     {
 8         //弹出要配置的结点
 9         BiTreePtr r=q.front();
10         q.pop();
11         //输入数据
12         cin>>data;
13         if(data==0){
14             *r=NULL;
15             continue;
16         }
17         *r=new BiTNode();
18         (*r)->data=data;
19         //压入新的子结点
20         q.push(&((*r)->leftChild));
21         q.push(&((*r)->rightChild));
22     }
23 }

测试结果：

input:1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0

output:1 2 4 8 5 3 6 7 （使用先序遍历）