C語言二叉樹的操作方法

本篇內容主要講解“C語言二叉樹的操作方法”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C語言二叉樹的操作方法”吧!

二叉樹分類

滿二叉樹

除最后一層無任何子節點外，每一層上的所有結點都有兩個子結點的二叉樹。也可以理解為每一層的結點數都達到最大值的二叉樹。

完全二叉樹

一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

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

二叉樹性質

• 若規定根節點的層數為1，則一棵樹非空二叉樹的第 i 層上最多有2^(i-1)個節點。

• 若規定根節點層數為1，則深度為h的二叉樹的最大節點數是2^h−1

• 對任何一顆二叉樹，如果葉節點(度為0的節點)個數為 n0 ，度為 2 的節點個數為 n2 ，則n0 = n2 + 1。

• 若規定根節點層數為1，具有N個節點的滿二叉樹的深度為小于（log_2）N+1的最大整數。

性質的使用

在具有 2n 個結點的完全二叉樹中，葉子結點個數為( )

A n

B n + 1

C n - 1

D n / 2

分析：

設度為 0 的結點有 x0 個

設度為 1 的結點有 x1 個

設度為 2 的結點有 x2 個

x0 + x1 + x2 = 2n

x0 = x2 + 1

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

因為是完全二叉樹，x1 可能是0，1，但是要使上式結果為偶數，x1只能是1，所以 x2 等于n ， 選A。

二叉樹的遍歷

首先我們先創建一個簡單的二叉樹

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

前序遍歷

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

預期結果：A B D E C

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

編譯結果：

中序遍歷

中序：左子樹 -> 根 -> 右子樹

預期結果：D B E A C

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

編譯結果：

后序遍歷

后續：左子樹 -> 右子樹 -> 根

預期結果：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);
}

編譯結果：

層序遍歷

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

求二叉樹的節點數

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

求二叉樹葉子結點個數

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

求二叉樹的最大深度

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

二叉樹的銷毀

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

到此，相信大家對“C語言二叉樹的操作方法”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！