一、為什么二叉樹的根結點常常是指向指針的指針

因為在創造一顆樹時，在申請根結點空間時，地址可能會發生變化，而這種變化是無法判斷的，是系統自動發生的，單個指針就無法找到變化后的地址，所以 ，用指針的指針，找到變化后的地址。當然 如果你在創造一顆樹前，就已經初始化分配了根結點的空間，那就不用指針的指針，直接用一個指針就行了。

它是一種C語言式的標準做法。

節點需要兩重指針，一重是節點本身動態更改數據的需要，另一重是分配與操作堆內存數據的需要。

至于是不是一定要做成指針的指針形式，取決于節點數據是直接手動管理內存，這種可以指針的指針，效率較高。還是封裝為某個結構的內部成員變量，開銷略大一點，就只是指針的形式，好控制，使用方便。用智能指針的話，實際也是屬于后者。

二叉樹的建立中：

t=(BiTtree*)malloc(sizeof(BiTtree)); t->data=d; CreateBiTree(t->left,x); CreateBiTree(t->right,x);;

其中t=(tree*)malloc(sizeof(tree));

改變了指針的指向所以指針的指針，或者指針的引用

void CreateBiTree(BiTtree *&t,char x)

1

附上代碼

#include

using namespace std;

struct BiTtree{

??? char data;

??? BiTtree *left,*right;

};

void CreateBiTree(BiTtree *&t,char x){

//在函數調用時用指針或者引用做參數，表示把變量的地址傳遞給子函數，

//但是子函數只能修改指針所指變量的值，并不能修改指針的指向。

//如果想要修改指針的指向，就要用指針的指針，或者指針的引用。

??? char d;

??? scanf(“%c”,&d);

??? if(d==x){

?????? t=NULL;

??? }

??? else{

?????? t=(BiTtree*)malloc(sizeof(BiTtree));

?????? t->data=d;

?????? CreateBiTree(t->left,x);

?????? CreateBiTree(t->right,x);

??? }

}

void printtree(BiTtree *t){

??? if(t){

?????? printf(“%c “, t->data);

?????? printtree(t->left);

?????? printtree(t->right);

??? }

}

int main(){

??? BiTtree *t;

??? CreateBiTree(t,’#’);

??? printtree(t);

??? return 0;

}

延伸閱讀：

二、樹

樹（Tree）是n(n>=0)個結點的有限集。n=0時稱為空樹。在任意一顆非空樹中：

此外，樹的定義還需要強調以下兩點：