一、引言：
?? 大三上學期學了數據結構后就沒再接觸過數據結構的內容了，至今已經整整兩年半了，已經把鏈表，隊列，堆棧，樹，二叉樹等內容忘得干干凈凈了，并且如果不是決定做《機器學習》的作業，自己絲毫沒有意識到自己已經忘得干干凈凈，或者說是以前只是依樣畫葫蘆的把二叉樹的程序調出來了，但是根本就沒有明白其中的原理！！

二、做《機器學習》作業的時候，怎么也想不明白兩個問題：
第一個問題：
"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