網站首頁編程語言正文

C語言實現二叉樹鏈式結構的示例詳解_C 語言

作者：小小涵兒 ? 更新時間： 2022-12-27 編程語言

前言

前面我們已經對堆進行學習，堆就是一個順序結構的二叉樹，把數組看成二叉樹，下面一起學習一下鏈式結構的二叉樹，這里是用遞歸實現功能

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掉了根結點，就找到不到這個根結點的左右孩子了

原文鏈接：https://blog.csdn.net/m0_46343224/article/details/128095808

上一篇：Python中的類的定義和對象的創建方法_python
下一篇：SAP技巧之修改自帶搜索幫助為自定數據集_數據庫其它

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁編程語言正文

C語言實現二叉樹鏈式結構的示例詳解_C 語言

目錄

前言

1. 鏈式二叉樹結構

2. 二叉樹的遍歷

2.1 前序遍歷

2.2 中序遍歷

2.3 后序遍歷

2.4 層序遍歷

3. 常見功能

3.1 二叉樹結點個數

3.2 二叉樹葉子結點個數

3.3 第K層結點的個數

3.4 二叉樹的深度

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

3.6 在二叉樹中查找值為x的結點

3.7 拿到每一層的數據

4. 二叉樹的創建和銷毀

4.1 二叉樹的創建

4.2 二叉樹的銷毀

相關推薦

日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

網站首頁 編程語言 正文

C語言實現二叉樹鏈式結構的示例詳解_C 語言

目錄

前言

1. 鏈式二叉樹結構

2. 二叉樹的遍歷

2.1 前序遍歷

2.2 中序遍歷

2.3 后序遍歷

2.4 層序遍歷

3. 常見功能

3.1 二叉樹結點個數

3.2 二叉樹葉子結點個數

3.3 第K層結點的個數

3.4 二叉樹的深度

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

3.6 在二叉樹中查找值為x的結點

3.7 拿到每一層的數據

4. 二叉樹的創建和銷毀

4.1 二叉樹的創建

4.2 二叉樹的銷毀

相關推薦

網站首頁編程語言正文