二叉樹(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ù)男蛄?，結(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);
	}
}