C語言超詳細總結講解二元樹的概念與使用

2022-04-08 22:00:02

1.二元樹的概念及結構

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

②二元樹的特點：

每個結點最多有兩棵子樹，即二元樹不存在度大於2的結點。（度最多為2）
二元樹的子樹有左右之分，其子樹的次序不能顛倒。

③現實中的二元樹：

當一名普通的人看到這樣一顆樹，可能會想：好標準的一棵樹

當一個程式猿看到這樣一棵樹，可能會想：好像資料結構中的二元樹，並且還是顆滿二元樹

④資料結構中的二元樹：

注：二元樹最多有兩個度

⑤特殊的二元樹：

滿二元樹：一個二元樹，如果每一個層的結點數都達到最大值，則這個二元樹就是滿二叉樹。也就是說，如果一個二元樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二元樹。
完全二元樹：完全二元樹是效率很高的資料結構，完全二元樹是由滿二元樹而引出來的。對於深度為K的，有n個結點的二元樹，當且僅當其每一個結點都與深度為K的滿二元樹中編號從1至n的結點一一對應時稱之為完全二元樹。要注意的是滿二元樹是一種特殊的完全二叉樹。

⑥二元樹的儲存結構：二元樹一般可以使用兩種結構儲存，一種順序結構，一種鏈式結構。

⑦二元樹的性質：

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

⑧練習題

2.二元樹鏈式結構的實現

①二元樹鏈式結構的遍歷：

所謂遍歷(Traversal)是指沿著某條搜尋路線，依次對樹中每個結點均做一次且僅做一次存取。訪問結點所做的操作依賴於具體的應用問題。遍歷是二元樹上最重要的運算之一，是二元樹上進行其它運算之基礎。

前序/中序/後序的遞迴結構遍歷：是根據存取結點操作發生位置命名

前序（先根）：先存取根節點，然後存取左子樹，最後存取右子樹
中序（中根）：先存取左節點，然後存取根節點，最後存取右子樹
後序（後根）：先存取左節點，然後存取右子樹，最後存取根節點

先定一個結構體型別：

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);
}

求二元樹結點的個數：

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

求葉子結點的個數：

int treeLeafSize(BTNode* p)//葉子結點個數
{
	if (p == NULL)
	{
		return 0;
	}
	if (p->left == NULL&&p->right == NULL)
	{
		return 1;
	}
 
	return treeLeafSize(p->left) + treeLeafSize(p->right);
}

到此這篇關於C語言超詳細總結講解二元樹的概念與使用的文章就介紹到這了,更多相關C語言二元樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

C語言超詳細總結講解二元樹的概念與使用

目錄

1.二元樹的概念及結構

2.二元樹鏈式結構的實現

熱門文章

C語言 超詳細總結講解二元樹的概念與使用

目錄

1.二元樹的概念及結構

2.二元樹鏈式結構的實現

熱門文章

C語言超詳細總結講解二元樹的概念與使用