快捷導(dǎo)航

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)詳細(xì)解析二叉樹(shù)的操作

更新時(shí)間：2022年04月26日 08:40:47 作者：洛語(yǔ)言

二叉樹(shù)可以簡(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++中二叉樹(shù)的實(shí)現(xiàn)和遍歷，需要的可以參考一下

二叉樹(shù)分類

滿二叉樹(shù)

除最后一層無(wú)任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹(shù)。也可以理解為每一層的結(jié)點(diǎn)數(shù)都達(dá)到最大值的二叉樹(shù)。

完全二叉樹(shù)

一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中的位置相同，則這棵二叉樹(shù)稱為完全二叉樹(shù)。

簡(jiǎn)單的說(shuō)，完全二叉樹(shù)就是最后一層可以有缺失的滿二叉樹(shù)(完全二叉樹(shù)是一種特殊的滿二叉樹(shù))，并且是從右往左的缺失。

二叉樹(shù)性質(zhì)

若規(guī)定根節(jié)點(diǎn)的層數(shù)為1，則一棵樹(shù)非空二叉樹(shù)的第 i 層上最多有2^(i-1)個(gè)節(jié)點(diǎn)。
若規(guī)定根節(jié)點(diǎn)層數(shù)為1，則深度為h的二叉樹(shù)的最大節(jié)點(diǎn)數(shù)是2^h−1
對(duì)任何一顆二叉樹(shù)，如果葉節(jié)點(diǎn)(度為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)的滿二叉樹(shù)的深度為小于（log_2）?N+1的最大整數(shù)。

性質(zhì)的使用

在具有 2n 個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中，葉子結(jié)點(diǎn)個(gè)數(shù)為( )

A n

B n + 1

C n - 1

D n / 2

分析：

設(shè)度為 0 的結(jié)點(diǎn)有 x0 個(gè)

設(shè)度為 1 的結(jié)點(diǎn)有 x1 個(gè)

設(shè)度為 2 的結(jié)點(diǎn)有 x2 個(gè)

x0 + x1 + x2 = 2n

x0 = x2 + 1

由上面兩個(gè)式子可推出：2 * 2x2 + x1 + 1 = 2n

因?yàn)槭峭耆鏄?shù)，x1 可能是0，1，但是要使上式結(jié)果為偶數(shù)，x1只能是1，所以 x2 等于n ，選A。

二叉樹(shù)的遍歷

首先我們先創(chuàng)建一個(gè)簡(jiǎn)單的二叉樹(shù)

typedef char BTDataType;
typedef struct BinaryTreeNode {
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
int main()
{
	BTNode* A = (BTNode*)malloc(sizeof(BTNode));
	A->data = 'A';
	A->left = NULL;
	A->right = NULL;
	BTNode* B = (BTNode*)malloc(sizeof(BTNode));
	B->data = 'B';
	B->left = NULL;
	B->right = NULL;
	BTNode* C = (BTNode*)malloc(sizeof(BTNode));
	C->data = 'C';
	C->left = NULL;
	C->right = NULL;
	BTNode* D = (BTNode*)malloc(sizeof(BTNode));
	D->data = 'D';
	D->left = NULL;
	D->right = NULL;
	BTNode* E = (BTNode*)malloc(sizeof(BTNode));
	E->data = 'E';
	E->left = NULL;
	E->right = NULL;
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	LevelOrder(A);
}

前序遍歷

前序(先序)：根 -> 左子樹(shù) -> 右子樹(shù)

預(yù)期結(jié)果：A B D E C

//前序
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		//為了結(jié)果更加直觀，將NULL打印
		printf("NULL ");
		return;
	}
	//先打印根的數(shù)據(jù)
	printf("%c ", root->data);
	//遍歷左子樹(shù)
	PrevOrder(root->left);
	//遍歷右子樹(shù)
	PrevOrder(root->right);
}

編譯結(jié)果：

中序遍歷

中序：左子樹(shù) -> 根 -> 右子樹(shù)

預(yù)期結(jié)果：D B E A C

void MidOrder(BTNode* root)
{
	//為了結(jié)果更加直觀，將NULL打印
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	MidOrder(root->left);
	printf("%c ", root->data);
	MidOrder(root->right);
}

編譯結(jié)果：

后序遍歷

后續(xù)：左子樹(shù) -> 右子樹(shù) -> 根

預(yù)期結(jié)果：D E B C A

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%c ", root->data);
}

編譯結(jié)果：

層序遍歷

void LevelOrder(BTNode* root)
{
	//創(chuàng)建隊(duì)列q
	Queue q;
	//初始化隊(duì)列
	QueueInit(&q);
	//如果根結(jié)點(diǎn)不為空，將根節(jié)點(diǎn)入隊(duì)列
	if (root) QueuePush(&q, root);
	//進(jìn)行循環(huán)，直到隊(duì)列為空
	while (!QueueEmpty(&q))
	{
		//獲取隊(duì)列的第一個(gè)數(shù)據(jù)，并打印
		QDataType front = QueueFront(&q);
		printf("%c ", front->data);
		//對(duì)頭數(shù)據(jù)出隊(duì)列
		QueuePop(&q);
		//如果左子樹(shù)不為空，左子樹(shù)入隊(duì)列
		if (front->left != NULL)
		{
			QueuePush(&q, front->left);
		}
		//如果右子樹(shù)不為空，右子樹(shù)入隊(duì)列
		if (front->right != NULL)
		{
			QueuePush(&q, front->right);
		}
	}
}

求二叉樹(shù)的節(jié)點(diǎn)數(shù)

int BTSize(BTNode* root)
{
	return root == NULL ? 0 :1 + BTSize(root->left) + BTSize(root->right);
}

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

int BTLeafSize(BTNode* root)
{
	if (root == 0) return 0;
	return root->left == NULL && root->right == NULL ? 1 : BTLeafSize(root->right) + BTLeafSize(root->left);
}

求二叉樹(shù)的最大深度

int maxDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + fmax(maxDepth(root ->left),maxDepth(root ->right));
}

二叉樹(shù)的銷毀

//二叉樹(shù)的銷毀
//傳二級(jí)指針是為了改變指針的指向
void DistoryTree(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	DistoryTree(&(*root)->left);
	DistoryTree(&(*root)->right);
	free(*root);
	*root = NULL;
}

到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)詳細(xì)解析二叉樹(shù)的操作的文章就介紹到這了,更多相關(guān)C語(yǔ)言二叉樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: