一、引言：
   大三上学期学了数据结构后就没再接触过数据结构的内容了，至今已经整整两年半了，已经把链表，队列，堆栈，树，二叉树等内容忘得干干净净了，并且如果不是决定做《机器学习》的作业，自己丝毫没有意识到自己已经忘得干干净净，或者说是以前只是依样画葫芦的把二叉树的程序调出来了，但是根本就没有明白其中的原理！！

二、做《机器学习》作业的时候，怎么也想不明白两个问题：
第一个问题：
"p->next"表示什么？p是一个指针，指针怎么会有next呢？应该Node结构体才有next指针呀。

第二个问题：
怎么建立一棵树？杨惠说要传一个根结点，并返回该根结点，但是为什么要传一个根结点呢？返回一个根结点怎么就能表示一棵树了呢？？真是想不明白！！

第三个问题：
建树函数buildTree()或者insert()，create()等需要设置几个参数？必须设置一个Node root参数吗？如果不设置root参数，怎么让它递归呢？

三、解决：
第一个问题：
唉，太久没看指针了，或者说以前根本就没有理解什么是指针，指针变量，指针变量所指向的变量等概念，复习了一遍谭浩强的C语言的书，感觉第一个问题豁然开朗。原来"p->next"表示的是：p指针变量所指向的变量的next指针变量。

第二个问题：
唉，看来以前根本没有理解二叉树，也没有理解递归方法，只因为吴平老师的一句“递归方法效率低”就完全不看递归了，真是傻瓜。不仅仅是递归，感觉自己连函数参数都不太理解，根本不知道什么时候需要参数，参数有何作用。更不用说明白一个函数的设计关键要清楚它传入什么参数，返回什么结果了。

第三个问题：
至今仍然不太明白！似乎就是必须接受一个Node root参数。

查了网上的递归建立二叉树的几个程序，它们分别是无参数、有一个参数、有两个参数的三种不同实现方法，从中终于领悟到什么时候需要参数，为什么需要参数了！可是第二、三个例子的一个参数和两个参数实际是一样的，只不过一个参数的例子用控制台输入数据而已。唉，还是不知道如果不设置一个Node root参数可不可实现建树。

四、下面分别是这三个建立二叉树的程序：
1.无参数：http://www.51log.net/dev/603/4692612.htm
Tree *Create()
{
    char ch;
    cin>> ch;
    Tree *root;

    if( ch == NIL )
    {
         return NULL;
    }
    else
    {
         root = new Tree(ch);
         root->left = Create();
         root->right = Create();
         return root;
    }
}
自己的注释：
Create函数：
输入：无
输出：一棵二叉树（根据返回的root根结点指针(注意不是root根结点，而是指针)就能访问到这棵树的所有结点了）

2.一个参数：http://shakesmin.javaeye.com/blog/43107
# //创建二叉树  
# void CreateBiTree(BiTree &t) {  
#     int ch=getchar();  
#     if(ch==' ') t=NULL;  
#     else {  
#         if( !( t=(BiTNode*)malloc(sizeof(BiTNode))) ) exit(OVERFLOW);  
#         t->data=ch;  
#         CreateBiTree(t->lchild);  
#         CreateBiTree(t->rchild);  
#     }  
# }  

自己的注释：
CreateBiTree函数：
输入：根结点；
输出：一棵二叉树；（无返回值）

注意：
这种方法传入根结点，但是没有返回值的原理。下面看一下它的使用方式就明白了：
# //递归遍历二叉树  
# void PreOrderTraverse(BiTree t) {  
#     if(t) {  
#         /* 以先序方式遍历,若要以中序或后序遍历 
#         只需改变以下三句顺序*/ 
#         printf("%c ",t->data);  
#         PreOrderTraverse(t->lchild);  
#         PreOrderTraverse(t->rchild);  
#     }  
# }  

# int main() {  
#     BiTree t;  
#     printf("请按先序正确输入二叉树(空格为空树):\n");  
#     CreateBiTree(t);  
#  
#     printf("先序历遍: ");  
#     PreOrderTraverse(t);  
#     return 0;  
# } 
明白了吧？原来是在main函数中定义了一个全局的根结点，以该根结点为基础建立二叉树和遍历二叉树，因此CreateBiTree中就不再需要返回root根结点指针才能访问该二叉树，它的PreOrderTraverse遍历函数传的直接是根结点，而第一个程序中遍历函数传的是指向root的指针变量。

3.有两个参数：http://dev.csdn.net/article/68/68480.shtm
#include <iostream.h>
#ifndef DEBUG
#define DEBUG
typedef int DataType;
typedef struct Node
{
       DataType        data;
       struct Node  *LChild;
       struct Node  *RChild;
}Node;
/*树的数据结构*/
/////////////////////////////////////////////////////////////
Node * Initiate()
/*初始化为空树*/
{
       Node   *root = 0;
       return   root ;
}
/////////////////////////////////////////////////////////////
Node * Creat(  DataType data  )
 /*建节点*/
{
       Node   * Temp   = new Node ;
       Temp -> data     = data ;
       Temp -> LChild = 0 ;
       Temp -> RChild = 0;
       return Temp ;
}
 
/************************************************/
void  Insert( Node *&root , DataType data )
//在c下不能这样 Node *&root
/* 降顺序二叉数装入数据，左子树<右子树*/
{     
       Node *p = Creat( data );//注：该程序中此行代码在if前，如果要插入一个非root结点，则每次都要新创建两个结点，一进入insert()创建一个p，递归时又创建一次。如果把该语句放到if内也不对，因为else if( p->data < root->data )时p就为空了。
       if( !root  )
       {      //Node *p = Creat( data ); //注：原程序逻辑不对，应该在if为真时才创建新结点；
              root = p;
           
       }
          else if( p->data < root->data )
          {
                 Insert ( root->LChild , p->data );
          }
          else
          {
                 Insert ( root->RChild , p->data );
          } /*相等的 将装数据到右孩子 */
       
}
/****************************************************/
 void PrintTree(Node * root)
 /*递归中序遍历 ---> 显示从小到大*/
{
       if( !root )  return ;
       PrintTree(root->LChild);
     
      cout<< root->data <<"  :";
      PrintTree( root->RChild );
      return ;
}

自己的注释：
Insert函数：
输入：根结点和结点数据；
输出：一棵二叉树；（无返回值）

注意：
同样，这种方式也传入了根结点来创建二叉树，并且函数没有返回root指针变量。再看它的使用方式：
///测试代码////////////
void main()
{
       int a;
       Node *Root = Initiate() ;
       cout<<" -1 to exit: "<<endl;
       cin>>a;           
       while( (a != -1)&&cin.good() )
                 //遇到非法输入同样退出循环
       {    
              Insert( Root ,  a );
                       cin>>a ;                       
       }
         if(!cin.good())
                     //输出错误信息
         {
                     cout<<" the type is error ! "<<endl;
         }
          PrintTree(Root);
          cout<<" ok ? "<<endl;
           FreeTree(Root);//销毁树 防止内存泄漏
          return;
}

现在明白了吧，也是在main中事先定义了一个root全局指针变量，然后把它做为参数建立二叉树和遍历二叉树。

结合自己买的那本书《数据结构 算法与实现 C++描述》上的清晰描述，知道，一棵二叉树是数据在内存中的逻辑表示，需要有一个指向该二叉树的root根节点的指针变量来记录它的首地址，然后就能访问到该树的所有结点了。

那么，这个根结点的指针变量在create()函数内定义呢（第一种无参的实现方式），还是在main函数中定义？——>两种方式都可以！如果在create()函数内定义，则需要返回该root的指针变量，这样才能取得二叉树的首地址遍历该树；如果在main函数中定义，则在create(TreeNode *root)中添加一参数接受该首地址建立二叉树。ok！



参考资料：
1. 二叉树的创建函数中对参数的疑问
http://www.51log.net/dev/603/4692612.htm

2. 数据结构课程源代码之二叉树实现及相关算法
http://shakesmin.javaeye.com/blog/43107

3. ::递归实现——创建二叉树 ----> 装入数据--->遍历---> 显示 --->销毁::递归实现) 
http://dev.csdn.net/article/68/68480.shtm