C語言實現二元樹鏈式結構的範例詳解

2022-12-01 14:03:24

前言

前面我們已經對堆進行學習，堆就是一個順序結構的二元樹，把陣列看成二元樹，下面一起學習一下鏈式結構的二元樹，這裡是用遞迴實現功能

1. 鏈式二元樹結構

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

2. 二元樹的遍歷

首先，我要說明一下遞迴實現；遞迴實現一般分為三個步驟（遞迴三要素）：初步明確函數功能，限制條件，找到實現此功能的等式

單項遞迴和二元樹遞迴（多項遞迴）的區別？

單項遞迴並沒有分支，多項遞迴是有分支的，這就意味著二元樹更看中整體，單項遞迴更看重分治。

單項遞迴和二元樹遞迴的共同點？

都是分治思想，子問題再分子問題再分子問題的思想

2.1 前序遍歷

思想：把樹看成整體：根、左子樹、右子樹，先遍歷根再走左子樹再走右子樹

void BinaryTreePrevOrder(BTNode* root)
{
    //根的情況(到底的限制條件)
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%c ", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

2.2 中序遍歷

思想：把樹看成整體：根、左子樹、右子樹，先遍歷左子樹再走根再走右子樹

void BinaryTreeInOrder(BTNode* root)
{
    //根的情況(到底的限制條件)
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	BinaryTreeInOrder(root->left);
	printf("%c ", root->data);
	BinaryTreeInOrder(root->right);
}

2.3 後序遍歷

void BinaryTreePostOrder(BTNode* root)
{
    //根的情況(到底的限制條件)
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->data);
}

2.4 層序遍歷

思想：出上一層的同時帶著下一層入佇列

//鏈式佇列的結構
typedef struct BinaryTreeNode* QueueDataType;
typedef struct QueueNode
{
	QueueDataType data;
	struct QueueNode* next;
}QueueNode;
//因為要直接得到隊頭的元素和隊尾的元素
typedef struct QueueLinkList
{
	QueueNode* head; //隊頭
	QueueNode* tail; //隊尾
	int size; //元素總數
}QLL;
//佇列初始化
void QLLInit(QLL* queue)
{
	assert(queue);

	queue->head = NULL;
	queue->tail = NULL;
	queue->size = 0;
}
//進隊
void QLLPush(QLL* queue, QueueDataType x)
{
	assert(queue);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("QLLPush:malloc is failed!n");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (queue->head == NULL)
	{
		queue->head = queue->tail = newnode;
	}
	else
	{
		queue->tail->next = newnode;
		queue->tail = newnode;
	}

	queue->size++;
}
//出隊
void QLLPop(QLL* queue)
{
	assert(queue != NULL);
	assert(QLLEmpty(queue) != true);
		
	//只有一個結點時
	if (queue->head->next == NULL)
	{
		free(queue->head); //free的是這個結點的空間，並不是指標
		queue->head = queue->tail = NULL;
	}
	else
	{
		//通常情況
		QueueNode* del = queue->head;
		queue->head = queue->head->next;
		free(del);
		//無需置空
	}

	queue->size--;
}
//拿取隊頭資料
QueueDataType QLLFront(QLL* queue)
{
	assert(queue != NULL);
	assert(QLLEmpty(queue) != true);

	return queue->head->data;
}
//判空
bool QLLEmpty(QLL* queue)
{
	assert(queue);

	//return queue->size == 0;
	return queue->head == NULL && queue->tail == NULL;
}
//銷燬
void QLLDestroy(QLL* queue)
{
	assert(queue);

	QueueNode* cur = queue->head;
	while (cur != NULL)
	{
		QueueNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}

	queue->head = queue->tail = NULL;
	queue->size = 0;
}

//層序遍歷實現
void BinaryTreeLevelOrder(BTNode* root)
{
	QLL queue;
	QLLInit(&queue);
    //根先入佇列
	if (root != NULL) {
		QLLPush(&queue, root);
	}
	//佇列不為NULL的時候進行出隊頭帶下層資料入隊操作
	while (QLLEmpty(&queue) != true)
	{
        //出隊頭操作
		BTNode* front = QLLFront(&queue);
		printf("%c ", front->data);
		QLLPop(&queue);
        //帶下一層進隊
		if (front->left != NULL)
		{
			QLLPush(&queue, front->left);
		}
		if (front->right != NULL)
		{
			QLLPush(&queue, front->right);
		}
	}
	printf("n");
	QLLDestroy(&queue);
}

說明：為什麼遞迴不畫圖來解決呢？

多項遞迴畫圖是很難理解的，因為他不是我們邏輯上想的，就拿前序遍歷來說，首先是根，再遍歷左子樹再遍歷右子樹這樣迴圈來走，但是在實際遞迴中邏輯是左子樹走到底，直到NULL時返回存取右子樹，如果說是畫圖是理解不了二元樹遞迴的，這裡我們就要扣住樹的結構：根、左子樹、右子樹，這樣是我們邏輯上的實現，並不是實際中的過程實現，這裡我需要說明一下，畫圖是為了在原有基礎上來進行糾錯，這裡糾正的錯也是和根的限制條件有關，這裡我還會出幾期二元樹的相關練習，到時候希望大佬們看看就能理解了二元樹遞迴！

3. 常見功能

3.1 二元樹結點個數

遞迴三要素解決問題

首先二元樹想到整體結構：根、左子樹、右子樹
函數功能：求二元樹結點的個數
限制條件：根為NULL的時候就不是一個結點（起初的結束條件：針對根來說）
等式：計算左子樹中的結點個數和右子樹的結點個數，最後加上根這個結點

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL) {
		return 0;
	}

	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

程式碼分析

上述列出來的思路就是實現思路，這裡注意的是樹的整體結構，我一直扣的就是整體結構，等式中寫的也是整體結構的邏輯；這裡來看程式碼很簡單就是根和左子樹和右子樹結構

為什麼不寫子結構：根、左孩子、右孩子？

原因就是如果寫成子結構的話就不是整體，而是把整體分為多個相同的結構來討論，這裡就不是整體觀念就很容易陷進去，為什麼二元樹遞迴難，難就難在你沒扣住整體，而是扣住的是子結構，如果扣住子結構那就很容易陷進去，只要陷進去了就不是我們自己想的邏輯，而是實際遞迴的過程邏輯，實際遞迴的過程邏輯和我們想的邏輯有很大的區別

為什麼首先要有個前提：樹的結構：根、左子樹、右子樹？

原因很簡單，我們考慮整體就少不了這個結構，這是我們首先要考慮的問題；另外也是因為這裡三要素中的實現是離不開這個整體結構的，如果離開了整體結構就又被陷進去了

限制條件是怎麼來限制的？

首先我們考慮的結構就是樹的整體結構：根、左子樹、右子樹，我們不可能是來對左右子樹來限制吧，因為左右子樹中有很多結點，從整體上來說是考慮不到的，另外你只要考慮左右子樹中的結點恭喜你，你又被陷進去出不來了哈哈，所以這裡的限制條件是針對根來講的：也就是根的起初的結束條件以及和題意的聯絡

3.2 二元樹葉子結點個數

遞迴三要素解決問題

前提：樹的結構：根、左子樹、右子樹
函數功能：求二元樹葉子節點的個數
限制條件：root=NULL的時候就不是葉子結點，根的左右孩子是空的時候但根不是空的時候就是葉子結點
等式：在左右子樹中找葉子節點，左右子樹中的葉子結點之和也就是樹的葉子結點

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}

	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

程式碼分析

3.3 第K層結點的個數

遞迴三要素解決問題

前提：樹的結構：根、左子樹、右子樹
函數功能：求第K層結點的個數
限制條件：root=NULL(起初的結束條件)，根所處的是第一層所以K=1的時候返回1（題意結束條件）
等式：在左右子樹的第k-1層中的結點個數（因為第一層是根，所以第K-1層才是我們要求的第K層）

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1)
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

程式碼分析

3.4 二元樹的深度

遞迴三要素解決問題

前提：樹的結構：根、左子樹、右子樹
函數功能：求樹的深度
限制條件：根為NULL時結束
等式：樹的根是第一層，那麼我們只用計算出左子樹和右子樹的哪個深度大就再加上1（根的深度）就是樹的深度

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int LeftTreeDepth = BinaryTreeDepth(root->left);
	int RightTreeDepth = BinaryTreeDepth(root->right);

	if (LeftTreeDepth > RightTreeDepth) {
		return LeftTreeDepth + 1;
	}
	else {
		return RightTreeDepth + 1;
	}
}

程式碼分析

沒進行優化的程式碼：

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

這個程式碼也是對的，但是時間複雜就要多了1倍，因為判斷中用到遞迴了，找到了並沒有記錄深度，也就進入判斷中的遞迴，再此遞迴一次，這樣時間複雜度就增了1倍。

3.5 判斷是不是樹是不是完全二元樹

思路：

完全二元樹的性質：前K-1層是滿二元樹，最後一層是從左到右是連續的

思路：用層序遍歷來解決，出上一層的同時帶下一層的資料，知道遇到NULL的時候就要進行判斷佇列中是不是還有不為NULL的值，如果有就不是完全二元樹，沒有則是

bool BinaryTreeComplete(BTNode* root)
{
	QLL queue;
	QLLInit(&queue);
	if (root != NULL)
	{
		QLLPush(&queue, root);
	}

	//拿到每層的
	while (QLLEmpty(&queue) != true)
	{
		BTNode* front = QLLFront(&queue);
		QLLPop(&queue);

		//當這層遇到NULL的時候進行判斷
		if (front == NULL)
		{
			break;
		}
		else
		{
			QLLPush(&queue, front->left);
			QLLPush(&queue, front->right);
		}
	}
    
	//出到NULL進行檢查
	//如果後面有非NULL就不是完全二元樹
	while (QLLEmpty(&queue) != true)
	{
		BTNode* front = QLLFront(&queue);
		QLLPop(&queue);
		//不為NULL說明最後一層不是連續的
		if (front != NULL)
		{
			QLLDestroy(&queue);
			return false;
		}
	}
	
	QLLDestroy(&queue);
	return true;
}

3.6 在二元樹中查詢值為x的結點

遞迴三要素解決問題

前提：樹的結構：根、左子樹、右子樹

函數功能：在二元樹中查詢值為x的結點

限制條件：root=NULL時結束，root->val=x時找到了就結束

等式：在根裡面找，在左子樹和右子樹裡面找

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
	}

	BTNode* ret1 = BinaryTreeFind(root->left, x);
	if (ret1 != NULL)
	{
		return ret1;
	}

	BTNode* ret2 = BinaryTreeFind(root->right, x);
	if (ret2 != NULL)
	{
		return ret2;
	}

	return NULL;
}

程式碼分析

錯誤列舉

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	if (root->data == x)
	{
		return root;
    }

	return BinaryTreeFind(root->left, x) || BinaryTreeFind(root->right, x);
}

為什麼邏輯上是對的，但是是錯的？

最後的return的意思翻譯過來就是在左子樹裡面找，找到了就返回，不進右子樹，如果左子樹中沒找到就進右子樹，找到了返回，如果都沒找到就直接返回NULL；邏輯上是對的，但是呢，這裡我們返回的是指標，指標的的關係不能用邏輯關係來表達，所以是錯的

3.7 拿到每一層的資料

思路

也是圍繞層序遍歷來寫：記錄每一層的結點樹來出佇列就行了，這裡也是層序遍歷的知識是主要的，就不再進行討論了

void EveryLayer(BTNode* root)
{
	QLL queue;
	int levelCount = 0;
	QLLInit(&queue);
	if (root != NULL) {
		QLLPush(&queue, root);
		//第一層就是一個資料
		levelCount = 1;
	}

	while (QLLEmpty(&queue) != true)
	{
		while (levelCount--)
		{
			BTNode* front = QLLFront(&queue);
			printf("%c ", front->data);
			QLLPop(&queue);
			if (front->left != NULL)
			{
				QLLPush(&queue, front->left);
			}
			if (front->right != NULL)
			{
				QLLPush(&queue, front->right);
			}
		}
		//下一層的個數
		levelCount = QLLSize(&queue);
		printf("n");
	}
	
	QLLDestroy(&queue);
}

結合上述題就很容易看出實際上我們寫程式碼來劃分的話也是樹的整體結構：根、左子樹、右子樹，時刻把握著樹的整體結構，這個結構充分體現在等式中，同時也影響到了限制條件，限制條件中只用管根的結束條件以及形成條件，其他的不用管，這就是在程式碼中實現的過程，這裡我就不在畫圖，覺得這個過程不能實現我說的對應的功能的時候你就畫圖去嘗試理解一下，謝謝

4. 二元樹的建立和銷燬

4.1 二元樹的建立

思路：

這裡用到前序遍歷來建立，也就是陣列的元素按個放進根的資料域中

限制條件：就是當元素為#，代表的是二元樹中的NULL

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	//形成條件
	if (a[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("BinaryTreeCreate: malloc is failed!n");
		exit(-1);
	}
	//根
	root->data = a[(*pi)++];

	//左右子樹
	root->left = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);

	return root;
}
void Test2()
{
	char str[] = { 'A','B','D','#','#','E','#','H','#','#','C','F','#','#','G','#','#' };

	int i = 0;
	BTNode* root = BinaryTreeCreate(str, &i);
}

4.2 二元樹的銷燬

//二級指標
void BinaryTreeDestory(BTNode** root)
{
	if ((*root) == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free((*root));
	*root = NULL;
}

void FirstPointBinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	FirstPointBinaryTreeDestory(root->left);
	FirstPointBinaryTreeDestory(root->right);
	free(root);
	//root = NULL;(沒必要）
}//需要說明的是用這個函數呼叫後要對root置空

為什麼採用後序遍歷來銷燬二元樹？

因為後序遍歷最開始走到的就是左子樹的最後一層，然後逐次向上銷燬，並不會影響每個結點的指向；如果採用前序遍歷呢？採用前序遍歷上來就是free掉了根結點，就找到不到這個根結點的左右孩子了

以上就是C語言實現二元樹鏈式結構的範例詳解的詳細內容，更多關於C語言二元樹鏈式結構的資料請關注it145.com其它相關文章！