二叉樹的諸多操作往往是通過遞歸調用來實現的，這就決定，不能只通過main函數實現全部過程，其中還需要調用main外定義的函數。也因此，對main調用外定義的函數的參數傳遞，就有了嚴格的要求。在網上查找很多關於二叉樹建立的程序，但直接拷貝在自己計算機上運行卻發現不少錯誤，無法編譯通過。以下有關代碼在VS2010上編譯通過，不涉及二叉樹的全部操作，本文著重通過二叉樹的創建過程說明遞歸實現與二重指針的相關問題。
1、二叉樹的定義
二叉樹的定義結構通常為如下形式：
typedef struct Node
{
char ch;
struct Node *lchild,*rchild;
}Node,*BTree;
Node一般可用來定義二叉樹節點，而*BTree可用來定義指向二叉樹（根節點）的指針。
2、內存動態分配
采用內存動態分配需要用到malloc函數。值得注意的是，該函數在成功開辟新的內存時，默認返回void*指針（即未指定指針），因此需要強制轉換成Node*形式，其調用形式如：(Node*)malloc(sizeof(Node))
3、遞歸調用
因為遞歸調用的需要，二叉樹的一些操作需要獨立作為一個函數。但是，這些函數是在main中調用，因此傳遞的參數和返回的值的處理是非常重要的。另外注意，對二叉樹的操作，首先就需要知道二叉樹的入口，即指向二叉樹的指針，也即指向二叉樹根節點的指針。因此，所傳遞的參數，則為指向根節點的指針。又因為涉及分配內存的操作，必須傳遞二級指針才能將實參指向所分配的內存，否則是形參指向了內存塊，當函數調用結束時，不復存在，這在有遞歸調用的函數裡，采用返回值也是不起作用，同樣在一輪調用結束後被銷毀。因此子函數的參數形式為二重指針。
如下程序，CreateTree函數可以是由返回值，也可以不具有返回值（因為傳遞的是地址）。在main函數中作了測試，返回的值為二叉樹根節點的值。
Node* CreateTree(Node** pTree)
{
char chr;
scanf("%c",&chr);
if(chr=='#')
{
(*pTree)=NULL;
}
else
{
if(!((*pTree)=(Node*)malloc(sizeof(Node))))
{
exit(OVERFLOW);
//#define OVERFLOW -2
}
(*pTree)->ch=chr;
CreateTree(&((*pTree)->lchild));
CreateTree(&((*pTree)->rchild));
}
return *pTree;
}
void main()
{
Node *pRoot;
Node *test;
char ch;
printf("現在開始創建二叉樹...輸入N結束\n");
test=CreateTree(&pRoot);
//傳遞指針的地址
//printf("所創建的二叉樹為：\n");
//PrintBinaryTree(test);
//while(1);
}
附注：測試程序
#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2
//定義二叉樹節點
typedef struct Node
{
char ch;
struct Node *lchild,*rchild;
}Node,*BTree;
//Node *pRoot=NULL;
//輸出二叉樹函數
void PrintBinaryTree(Node *Tree)
{
if(Tree==NULL)
return;
//printf("%c-->",Tree->ch);
PrintBinaryTree(Tree->lchild);
printf("%c-->",Tree->ch);
PrintBinaryTree(Tree->rchild);
}
//創建二叉樹
Node* CreateTree(Node** pTree)
{
char chr;
scanf("%c",&chr);
if(chr=='#')
{
(*pTree)=NULL;
}
else
{
if(!((*pTree)=(Node*)malloc(sizeof(Node))))
{
exit(OVERFLOW);
}
(*pTree)->ch=chr;
CreateTree(&((*pTree)->lchild));//(*pTree)->lchild為Node *變量，而參數則是Node **變量，則需要&取址，否則形參無法保留*lchild值
CreateTree(&((*pTree)->rchild));
}
return *pTree;
}
void main()
{
Node *treehead;
Node *test;
//Node *bitree=NULL;
char ch;
printf("現在開始創建二叉樹...輸入N結束\n");
test=CreateTree(&treehead);
printf("所創建的二叉樹為：\n");
PrintBinaryTree(test);
while(1);
}
