二叉樹可以簡(jiǎn)單理解為對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，最多擁有一個(gè)上級(jí)節(jié)點(diǎn)，同時(shí)最多具備左右兩個(gè)下級(jí)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)。本文將詳細(xì)介紹一下C++中二叉樹的概念和結(jié)構(gòu)，需要的可以參考一下

1.二叉樹的概念及結(jié)構(gòu)

①概念：一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根節(jié)點(diǎn)加上兩棵別稱為左子樹和右子樹的二叉樹組成。

②二叉樹的特點(diǎn)：

每個(gè)結(jié)點(diǎn)最多有兩棵子樹，即二叉樹不存在度大于2的結(jié)點(diǎn)。（度最多為2）
二叉樹的子樹有左右之分，其子樹的次序不能顛倒。

③現(xiàn)實(shí)中的二叉樹：

當(dāng)一名普通的人看到這樣一顆樹，可能會(huì)想：好標(biāo)準(zhǔn)的一棵樹

當(dāng)一個(gè)程序猿看到這樣一棵樹，可能會(huì)想：好像數(shù)據(jù)結(jié)構(gòu)中的二叉樹，并且還是顆滿二叉樹

④數(shù)據(jù)結(jié)構(gòu)中的二叉樹：

注：二叉樹最多有兩個(gè)度

⑤特殊的二叉樹：

滿二叉樹：一個(gè)二叉樹，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹就是滿二叉樹。也就是說(shuō)，如果一個(gè)二叉樹的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是(2^k) -1 ，則它就是滿二叉樹。
完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來(lái)的。對(duì) 于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹中編號(hào) 從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹。要注意的是滿二叉樹是一種特殊的完全二叉樹。

⑥二叉樹的存儲(chǔ)結(jié)構(gòu)：二叉樹一般可以使用兩種結(jié)構(gòu)存儲(chǔ)，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

⑦二叉樹的性質(zhì)：

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1) 個(gè)結(jié)點(diǎn).
若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點(diǎn)數(shù)是2^h- 1.
對(duì)任何一棵二叉樹, 如果度為0其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的分支結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2 +1
若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，具有n個(gè)結(jié)點(diǎn)的滿二叉樹的深度，h=log?n+1

⑧練習(xí)題

2.二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)

①二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的遍歷：

所謂遍歷(Traversal)是指沿著某條搜索路線，依次對(duì)樹中每個(gè)結(jié)點(diǎn)均做一次且僅做一次訪問。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。遍歷是二叉樹上最重要的運(yùn)算之一，是二叉樹上進(jìn)行其它運(yùn)算之基礎(chǔ)。

前序/中序/后序的遞歸結(jié)構(gòu)遍歷：是根據(jù)訪問結(jié)點(diǎn)操作發(fā)生位置命名

前序（先根）：先訪問根節(jié)點(diǎn)，然后訪問左子樹，最后訪問右子樹
中序（中根）：先訪問左節(jié)點(diǎn)，然后訪問根節(jié)點(diǎn)，最后訪問右子樹
后序（后根）：先訪問左節(jié)點(diǎn)，然后訪問右子樹，最后訪問根節(jié)點(diǎn)

先定一個(gè)結(jié)構(gòu)體類型：

typedef char BTDataType;
typedef struct BinarytreeNode
{
	BTDataType data;
	struct BinarytreeNode* left;
	struct BinarytreeNode* right;
}BTNode;

前序：

void Preamble(BTNode* p)//前序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", p->data);
	Preamble(p->left);
	Preamble(p->right);
}

中序：

void Morder(BTNode* p)//中序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	Morder(p->left);
	printf("%c ", p->data);
	Morder(p->right);
}

后序：

void Porder(BTNode* p)//后序
{
	if (p == NULL)
	{
		printf("NULL ");
		return;
	}
	Porder(p->left);
	Porder(p->right);
	printf("%c ", p->data);
}

求二叉樹結(jié)點(diǎn)的個(gè)數(shù)：

int treeSize(BTNode* p)//結(jié)點(diǎn)個(gè)數(shù)
{
	return p == NULL ? 0 : treeSize(p->left) + treeSize(p->right)+1;
}

求葉子結(jié)點(diǎn)的個(gè)數(shù)：

int treeLeafSize(BTNode* p)//葉子結(jié)點(diǎn)個(gè)數(shù)
{
	if (p == NULL)
	{
		return 0;
	}
	if (p->left == NULL&&p->right == NULL)
	{
		return 1;
	}
 
	return treeLeafSize(p->left) + treeLeafSize(p->right);
}

到此這篇關(guān)于C語(yǔ)言超詳細(xì)總結(jié)講解二叉樹的概念與使用的文章就介紹到這了,更多相關(guān)C語(yǔ)言二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: