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

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

②二叉樹的特點：

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

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

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

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

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

注：二叉樹最多有兩個度 

⑤特殊的二叉樹： 

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

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

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

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

⑧練習(xí)題  

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

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

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

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

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

 先定一個結(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é)點的個數(shù)：

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

求葉子結(jié)點的個數(shù)：

int treeLeafSize(BTNode* p)//葉子結(jié)點個數(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語言 超詳細(xì)總結(jié)講解二叉樹的概念與使用的文章就介紹到這了,更多相關(guān)C語言 二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論