二叉樹的存儲結(jié)構(gòu)

---- 二叉樹是非線性結(jié)構(gòu)，其存儲結(jié)構(gòu)可以分為兩種，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

1、順序存儲結(jié)構(gòu)

---- 二叉樹的順序存儲，就是用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點(diǎn)。即用一維數(shù)組存儲二叉樹中的結(jié)點(diǎn)。因此，必須把二叉樹的所有結(jié)點(diǎn)安排成一個恰當(dāng)?shù)男蛄?，結(jié)點(diǎn)在這個序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。用編號的方法從樹根起，自上層至下層，每層自左至右地給所有結(jié)點(diǎn)編號。

---- 依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結(jié)點(diǎn)的序號可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置，以及結(jié)點(diǎn)之間的關(guān)系。

---- 一棵完全二叉樹（滿二叉樹）如下圖所示：

? ? ? ? ? ? ? ? ? ? ? ?

將這棵二叉樹存入到數(shù)組中，相應(yīng)的下標(biāo)對應(yīng)其同樣的位置，如下圖所示：

? ? ? ? ? ? ? ??

但是對于一般的非完全二叉樹來說，如果仍然按照從上到下、從左到右的次序存儲在一維數(shù)組中，則數(shù)組下標(biāo)之間不能準(zhǔn)確反映樹中結(jié)點(diǎn)間的邏輯關(guān)系，可以在非完全二叉樹中添加一些并不存在的空結(jié)點(diǎn)使之變成完全二叉樹，（把不存在的結(jié)點(diǎn)設(shè)置為“^”）不過這樣做有可能會造成空間的浪費(fèi)，如下圖所示，然后再用一維數(shù)組順序存儲二叉樹。

? ? ? ? ?

? ? ? ? ? ? ?

缺點(diǎn)是：有可能對存儲空間造成極大的浪費(fèi)，在最壞的情況下，一棵深度為k的右斜樹，它只有k個結(jié)點(diǎn)，卻需要2^k-1個結(jié)點(diǎn)存儲空間。這顯然是對存儲空間的嚴(yán)重浪費(fèi)，所以順序存儲結(jié)構(gòu)一般只用于完全二叉樹或滿二叉樹。

生成二叉樹的順序存儲結(jié)構(gòu)代碼如下：

#includeusing?namespace?std;
#define?MAX?20
/***??生成二叉樹
思路：所有結(jié)點(diǎn)都需要和根結(jié)點(diǎn)比較大小，小于根結(jié)點(diǎn)的結(jié)點(diǎn)放在左子樹，反之，
??????大于根結(jié)點(diǎn)的結(jié)點(diǎn)放在右子樹。
-----?本算法需要定義兩個數(shù)組，數(shù)組b_tree用于存儲最終的二叉樹，數(shù)組node用于
??????保存結(jié)點(diǎn)數(shù)值，為了使數(shù)組的下標(biāo)和結(jié)點(diǎn)的編號相對應(yīng)，b_tree[0]不存儲數(shù)據(jù)，
	??從b_tree[1]開始存儲。
***/
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)行存儲
		{
			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)酱鎯Y(jié)構(gòu)

---- 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系。

---- 二叉樹的每個結(jié)點(diǎn)最多有兩個孩子，因此，每個結(jié)點(diǎn)除了存儲自身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個指針分別指向左、右孩子結(jié)點(diǎn)。

結(jié)點(diǎn)結(jié)構(gòu)如下圖所示：

? ? ? ??

其中data是數(shù)據(jù)域，lchild和rchild都是指針域，分別存放指向左孩子和右孩子的指針。由上圖所示的結(jié)點(diǎn)構(gòu)成的鏈表稱作二叉鏈表。當(dāng)沒有孩子結(jié)點(diǎn)時，相應(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;
//插入二叉樹結(jié)點(diǎn)（將d值插入到二叉樹中的相應(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);?//訪問左子樹
	else
		p?=?Find_Node(root->rchild,x);?//訪問右子樹
	return?p;
}
//統(tǒng)計(jì)二叉樹的深度
/*
	當(dāng)左子樹的深度大于右子樹時，則返回左子樹的深度+1，否則返回右子樹的深度+1
	當(dāng)root為葉子結(jié)點(diǎn)時，停止遞歸，返回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);
	}
}