??write in front??
??所屬專欄：初階數(shù)據(jù)結(jié)構(gòu)
???博客主頁：睿睿的博客主頁
???代碼倉庫：??VS2022_C語言倉庫
??您的點贊、關(guān)注、收藏、評論，是對我最大的激勵和支持！?。?br>關(guān)注我，關(guān)注我，關(guān)注我，你們將會看到更多的優(yōu)質(zhì)內(nèi)容??！

前言

??在之前的二叉樹的順序結(jié)構(gòu)中我們發(fā)現(xiàn)，該二叉樹對于堆（一種完全二叉樹）非常實用，但是對于非完全二叉樹就會出現(xiàn)以下的結(jié)構(gòu)，造成空間浪費：

??所以這里我們還是要通過鏈?zhǔn)浇Y(jié)構(gòu)來實現(xiàn)二叉樹。但是其實普通二叉樹是沒有什么意義的，增刪查改沒有多大的意義。真正有意義的是搜索二叉樹：

??搜索二叉樹的特點是左子樹比根大/小，右子樹比根小/大。這里的二叉樹可以用來搜索，也可以用來進行插入，刪除等操作，擁有實際的意義。所以對于普通二叉樹，我們不用學(xué)習(xí)他的增刪查改，只用學(xué)習(xí)他的遍歷等操作，并且復(fù)習(xí)一下遞歸的相關(guān)知識。

一.二叉樹的理解：

我們先回顧一下回顧下二叉樹的概念，二叉樹是：

1. 空樹
2. 非空：根節(jié)點，根節(jié)點的左子樹、根節(jié)點的右子樹組成的。

??對于一顆二叉樹，我們看到它就要把他分為：根，左子樹，右子樹。對于左子樹，在把他分為：根，左子樹，右子樹。對于右子樹，在把他分為：根，左子樹，右子樹……以此類推直到左右子樹都為空才停止。

??從概念中可以看出，二叉樹定義是遞歸式的，因此后序基本操作中基本都是按照該概念實現(xiàn)的。

二.二叉樹的遍歷：

??學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的每個節(jié)點進行相應(yīng)的操作，并且每個節(jié)點只操作一次。訪問結(jié)點所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎(chǔ)。

??按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷。我們以這顆二叉樹為例：

創(chuàng)建二叉樹：

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

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc::fail");
		return;
	}

	node->left = NULL;
	node->right = NULL;
	node->data = x;

	return node;
}


BTNode* CreatTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node3->right = node7;


	return node1;
}

1.前序遍歷：

??前序遍歷的順序是：根，左子樹，右子樹。

代碼實現(xiàn)：

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

結(jié)果：

2.中序遍歷：

??中序遍歷的順序是：左子樹，根，右子樹。


代碼實現(xiàn)：

void InOrder(BTNode* root)
{

	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

結(jié)果：

3.后序遍歷：

??后序遍歷的順序是：左子樹，右子樹，根。

代碼實現(xiàn)：

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

結(jié)果：

??其實上面的三種遍歷就是通過s三句代碼的順序?qū)е陆Y(jié)果的不同，當(dāng)然他們的遞歸過程都能用下面這張圖來代表：

4.層序遍歷：

??除了先序遍歷、中序遍歷、后序遍歷外，還可以對二叉樹進行層序遍歷。設(shè)二叉樹的根節(jié)點所在層數(shù)為1，層序遍歷就是從所在二叉樹的根節(jié)點出發(fā)，首先訪問第一層的樹根節(jié)點，然后從左到右訪問第2層上的節(jié)點，接著是第三層的節(jié)點，以此類推，自上而下，自左至右逐層訪問樹的結(jié)點的過程就是層序遍歷

??那么如何實現(xiàn)層序遍歷呢？這里我們就要用到我們之前所學(xué)的隊列了！
??在這里，我們將二叉樹的根先進隊列，然后將其出隊列，每出一次，就讓其左右子結(jié)點進入隊列，隨后在出一個隊列，將其左右子節(jié)點加入隊列……這樣通過隊列的push和pop就能實現(xiàn)層序遍歷

我們首先將隊列的代碼導(dǎo)入即可，就可以創(chuàng)建隊列了：

代碼實現(xiàn)：

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	
	while (!QueueEmpty(&q))
	{
		BTNode* front= QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}

注意：
??這里我們放入隊列的不是要打印的數(shù)據(jù)，而是樹結(jié)點的指針，為什么呢？如果我們存入的是要打印的數(shù)據(jù)（整形數(shù)據(jù)），那么我們無法找到他們的子節(jié)點!所以我們每次pop出一個指針，然后push這個指針（結(jié)點）的子節(jié)點即可。圖解如下：

三.判斷二叉樹是否為完全二叉樹：

我們先來看看這張圖：

??我們會發(fā)現(xiàn)，通過層序遍歷的方法，滿二叉樹在層序遍歷時的非空結(jié)點一定是連續(xù)的，空結(jié)點也是連續(xù)的，所以我們只要在層序遍歷的基礎(chǔ)上把空結(jié)點存入，然后判斷空結(jié)點是否連續(xù)即可。

代碼實現(xiàn)：

// 判斷二叉樹是否是完全二叉樹
bool TreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}

	// 判斷是不是完全二叉樹
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		// 后面有非空，說明非空節(jié)點不是完全連續(xù)
		if (front)
		{
			QueueDestroy(&q);
			return false;
		}
	}

四.二叉樹結(jié)點數(shù)量：

??如果我們要計算結(jié)點的數(shù)量，通過上面所學(xué)的遍歷的方式當(dāng)然可以計算出結(jié)點數(shù)量。

這就是遍歷的方法，但是事實上我們用分治的方法更多一些：

分治和遍歷的區(qū)別：

拿學(xué)校人口統(tǒng)計作為例子，遍歷法與分治法的區(qū)別如下：

遍歷法，做法如下：
校長自己一個人帶著一個本子，跑遍全校查人數(shù)

分治法，做法如下：
校長想知道人數(shù)，就找來院長統(tǒng)計每個院的人數(shù)相加，院長找來系主任統(tǒng)計每個系的人數(shù)相加……這樣校長就不用親自動手了。其實遞歸就是把任務(wù)交給打工人（嗚嗚）。

那么我們?nèi)绾螌崿F(xiàn)分治法呢？
總體思路就是 返回：左子樹數(shù)量+右子樹數(shù)量+1
代碼實現(xiàn)：

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

五.二叉樹的高度（深度）：

在這里要求二叉樹的高度，我們也是用分治的思想：

int TreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
}

其實對于遞歸內(nèi)容，我們只需要考慮：

• 將問題分為子問題，子問題的解決方式和總問題的解決方式的方式一樣
• 有中止的條件

六.二叉樹第k層節(jié)點個數(shù)

現(xiàn)在我們把他分為子問題：

當(dāng)前樹的第k層個數(shù)=左子樹的第k-1層個數(shù)+右子樹的第k-1層個數(shù)
代碼如下：

int TreeKLevel(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	int leftklevel = TreeKLevel(root->left, k - 1);
	int rightklevel = TreeKLevel(root->right, k - 1);

	return leftklevel + rightklevel;
}

總結(jié)

??更新不易，辛苦各位小伙伴們動動小手，??三連走一走???? ~ ~ ~ 你們真的對我很重要！最后，本文仍有許多不足之處，歡迎各位認真讀完文章的小伙伴們隨時私信交流、批評指正！

專欄訂閱：
每日一題
c語言學(xué)習(xí)
算法
智力題
初階數(shù)據(jù)結(jié)構(gòu)
更新不易，辛苦各位小伙伴們動動小手，??三連走一走???? ~ ~ ~ 你們真的對我很重要！最后，本文仍有許多不足之處，歡迎各位認真讀完文章的小伙伴們隨時私信交流、批評指正！

文章來源地址http://www.zghlxwxcb.cn/news/detail-435174.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！