二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
---- 二叉樹(shù)是非線性結(jié)構(gòu)，其存儲(chǔ)結(jié)構(gòu)可以分為兩種，即順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
1、順序存儲(chǔ)結(jié)構(gòu)
---- 二叉樹(shù)的順序存儲(chǔ)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹(shù)中的結(jié)點(diǎn)。即用一維數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)。因此，必須把二叉樹(shù)的所有結(jié)點(diǎn)安排成一個(gè)恰當(dāng)?shù)男蛄校Y(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。用編號(hào)的方法從樹(shù)根起，自上層至下層，每層自左至右地給所有結(jié)點(diǎn)編號(hào)。
---- 依據(jù)二叉樹(shù)的性質(zhì)，完全二叉樹(shù)和滿二叉樹(shù)采用順序存儲(chǔ)比較合適，樹(shù)中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹(shù)中的位置，以及結(jié)點(diǎn)之間的關(guān)系。
---- 一棵完全二叉樹(shù)（滿二叉樹(shù)）如下圖所示：
? ? ? ? ? ? ? ? ? ? ? ?
將這棵二叉樹(shù)存入到數(shù)組中，相應(yīng)的下標(biāo)對(duì)應(yīng)其同樣的位置，如下圖所示：
? ? ? ? ? ? ? ??
但是對(duì)于一般的非完全二叉樹(shù)來(lái)說(shuō)，如果仍然按照從上到下、從左到右的次序存儲(chǔ)在一維數(shù)組中，則數(shù)組下標(biāo)之間不能準(zhǔn)確反映樹(shù)中結(jié)點(diǎn)間的邏輯關(guān)系，可以在非完全二叉樹(shù)中添加一些并不存在的空結(jié)點(diǎn)使之變成完全二叉樹(shù)，（把不存在的結(jié)點(diǎn)設(shè)置為“^”）不過(guò)這樣做有可能會(huì)造成空間的浪費(fèi)，如下圖所示，然后再用一維數(shù)組順序存儲(chǔ)二叉樹(shù)。
? ? ? ? ?
? ? ? ? ? ? ?
缺點(diǎn)是：有可能對(duì)存儲(chǔ)空間造成極大的浪費(fèi)，在最壞的情況下，一棵深度為k的右斜樹(shù)，它只有k個(gè)結(jié)點(diǎn)，卻需要2^k-1個(gè)結(jié)點(diǎn)存儲(chǔ)空間。這顯然是對(duì)存儲(chǔ)空間的嚴(yán)重浪費(fèi)，所以順序存儲(chǔ)結(jié)構(gòu)一般只用于完全二叉樹(shù)或滿二叉樹(shù)。
生成二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)代碼如下：
#includeusing?namespace?std;
#define?MAX?20
/***??生成二叉樹(shù)
思路：所有結(jié)點(diǎn)都需要和根結(jié)點(diǎn)比較大小，小于根結(jié)點(diǎn)的結(jié)點(diǎn)放在左子樹(shù)，反之，
??????大于根結(jié)點(diǎn)的結(jié)點(diǎn)放在右子樹(shù)。
-----?本算法需要定義兩個(gè)數(shù)組，數(shù)組b_tree用于存儲(chǔ)最終的二叉樹(shù)，數(shù)組node用于
??????保存結(jié)點(diǎn)數(shù)值，為了使數(shù)組的下標(biāo)和結(jié)點(diǎn)的編號(hào)相對(duì)應(yīng)，b_tree[0]不存儲(chǔ)數(shù)據(jù)，
??從b_tree[1]開(kāi)始存儲(chǔ)。
***/
void?Create_bTree(int?*b_tree,int?*node,int?len)
{
int?i;
int?level;
b_tree[1]?=?node[1];
for(i=2;i<len;i++)
{
level?=?1;
while(b_tree[level]!=0)?//結(jié)點(diǎn)為空，退出循環(huán)，進(jìn)行存儲(chǔ)
{
if(node[i]<b_tree[level])
level?=?2*level;
else
level?=?2*level+1;
}
b_tree[level]?=?node[i];
}
}
int?main()
{
int?b_tree[MAX]?=?{0};?//初始為空
int?node[11]?=?{0,8,6,7,4,2,3,15,1,14,16};//8是根結(jié)點(diǎn)
Create_bTree(b_tree,node,11);
for(int?i=1;i<MAX;i++)
{
cout<<b_tree[i]<<"t";
if(i%5==0)
cout<<endl;
}
cout<<endl;
system("pause");
return?0;
}輸出結(jié)果：
2、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
---- 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈來(lái)指示元素的邏輯關(guān)系。
---- 二叉樹(shù)的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，因此，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)自身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針?lè)謩e指向左、右孩子結(jié)點(diǎn)。
結(jié)點(diǎn)結(jié)構(gòu)如下圖所示：
? ? ? ??
其中data是數(shù)據(jù)域，lchild和rchild都是指針域，分別存放指向左孩子和右孩子的指針。由上圖所示的結(jié)點(diǎn)構(gòu)成的鏈表稱作二叉鏈表。當(dāng)沒(méi)有孩子結(jié)點(diǎn)時(shí)，相應(yīng)的指針域置為空。二叉鏈表中結(jié)點(diǎn)結(jié)構(gòu)定義代碼如下：
#includeusing?namespace?std;
typedef?int?TElemType;
typedef?struct?BTNode?//結(jié)點(diǎn)結(jié)構(gòu)
{
TElemType?data;//結(jié)點(diǎn)數(shù)據(jù)
struct?BTNode?*lchild,*rchild;?//左右孩子指針
}BNode,*BTree;
//插入二叉樹(shù)結(jié)點(diǎn)（將d值插入到二叉樹(shù)中的相應(yīng)位置）
BTree?Insert_tree(BTree?root,TElemType?d)
{
BNode?*?newnode;
BNode?*?curnode;
BNode?*?parnode;
newnode?=?(BNode?*)malloc(sizeof(BNode));
newnode->data?=?d;
newnode->lchild?=?NULL;
newnode->rchild?=?NULL;
if(root==NULL)
return?newnode;?//作為根結(jié)點(diǎn)返回
else
{
curnode?=?root;
while(curnode!=NULL)
{
parnode?=?curnode;//保存父結(jié)點(diǎn)
if(ddata)
curnode?=?curnode->lchild;
else
curnode?=?curnode->rchild;
}
if(ddata)
parnode->lchild?=?newnode;
else
parnode->rchild?=?newnode;
}
return?root;
}
//返回data域?yàn)閤的結(jié)點(diǎn)指針
BTree?Find_Node(BTree?root,TElemType?x)
{
BTree?p;
if(root==NULL||root->data==x)
return?root;
else?if(x>root->data)
p?=?Find_Node(root->lchild,x);?//訪問(wèn)左子樹(shù)
else
p?=?Find_Node(root->rchild,x);?//訪問(wèn)右子樹(shù)
return?p;
}
//統(tǒng)計(jì)二叉樹(shù)的深度
/*
當(dāng)左子樹(shù)的深度大于右子樹(shù)時(shí)，則返回左子樹(shù)的深度+1，否則返回右子樹(shù)的深度+1
當(dāng)root為葉子結(jié)點(diǎn)時(shí)，停止遞歸，返回1，然后逐層向上累加。
*/
int?BTDepth(BTree?root)
{
int?ldepth,rdepth;
if(root==NULL)
return?0;
else
{
ldepth?=?BTDepth(root->lchild);
rdepth?=?BTDepth(root->rchild);
return?(ldepth>rdepth)?(ldepth+1):(rdepth+1);
}
}
下載文檔
