一、為什么二叉樹的根結點常常是指向指針的指針
因為在創造一顆樹時,在申請根結點空間時,地址可能會發生變化,而這種變化是無法判斷的,是系統自動發生的,單個指針就無法找到變化后的地址,所以 ,用指針的指針,找到變化后的地址。當然 如果你在創造一顆樹前,就已經初始化分配了根結點的空間,那就不用指針的指針,直接用一個指針就行了。
它是一種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時稱為空樹。在任意一顆非空樹中:
有且僅有一個特定的稱為根(Root)的結點;當n>1時,其余結點可分為m(m>0)個互不相交的有限集T1、T2、…… 為什么二叉樹的根結點常常是指向指針的指針Tn,其中每一個集合本身又是一棵樹,并且稱為根的子樹。此外,樹的定義還需要強調以下兩點:
n>0時根結點是少數的,不可能存在多個根結點,數據結構中的樹只能有一個根結點。m>0時,子樹的個數沒有限制,但它們一定是互不相交的。