??樊梓慕：個人主頁

???個人專欄：《C語言》《數(shù)據(jù)結(jié)構(gòu)》《藍橋杯試題》《LeetCode刷題筆記》《實訓項目》

??每一個不曾起舞的日子，都是對生命的辜負

目錄

前言

1.前序建立二叉樹

2.銷毀二叉樹

3.統(tǒng)計

4.查找值為x的節(jié)點

5.前中后序遍歷

6.層序遍歷

7.判斷二叉樹是否為完全二叉樹

總結(jié)

前言

本篇文章博主將會與大家一起學習二叉樹的構(gòu)建與一些基本操作實現(xiàn)，那么對于二叉樹來說：遞歸是不可繞開的話題，在本篇文章中你會看到很多的遞歸，遞歸的核心思想就是分割子問題，他異于我們之前學習的遍歷枚舉等思想，所以希望你能有所收獲??

歡迎大家??收藏??以便未來做題時可以快速找到思路，巧妙的方法可以事半功倍。

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

GITEE相關代碼：??fanfei_c的倉庫??

=========================================================================

1.前序建立二叉樹

首先我們輸入一段前序序列，用字符串存儲，空節(jié)點的部分我們用字符'#' 替代，利用*pi作為下標，遍歷該字符串。

前序：將字符賦給當前節(jié)點的數(shù)據(jù)域，*pi的值+1，給當前節(jié)點的左孩子執(zhí)行相同操作，給當前節(jié)點的右孩子執(zhí)行相同操作，采用遞歸方式完成。

那么你可以寫出中序建立二叉樹的算法么？

代碼實現(xiàn)：

BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	root->_data = a[(*pi)++];

	root->_left = BinaryTreeCreate(a, pi);
	root->_right= BinaryTreeCreate(a, pi);
	return root;
}

為什么使用指針pi，而不用整型pi？?

• 若傳整型，在函數(shù)遞歸的過程中，由于函數(shù)棧幀的關系，整型pi的值不會保留，所以需要傳遞指針。

2.銷毀二叉樹

銷毀二叉樹比較簡單。

注意：銷毀二叉樹采用的是后序遍歷的方式，因為如果先銷毀根節(jié)點，那么就找不到孩子節(jié)點了。?

代碼實現(xiàn)：?

// 二叉樹銷毀
void BinaryTreeDestory(BTNode** root)
{
	if (*root)
	{
		BinaryTreeDestory(&(*root)->_left);
		BinaryTreeDestory(&(*root)->_right);
		free(*root);
        *root = NULL;
	}
}

3.統(tǒng)計

我們主要看一下統(tǒng)計第k層節(jié)點的算法：

如何判斷何時遞歸到第k層呢？

• 想要到達第k層，我們可以利用遞歸每次讓k-1，當k的值為1的時候，那么此時我們就來到了第k層
• 可以來到第k層的，也就是k==1時我們返回1
• 遞歸還是采用雙路遞歸，即返回左右子樹的和即可

代碼實現(xiàn)：?

//計算節(jié)點數(shù)
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

//計算葉子節(jié)點數(shù)
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);
}

// 二叉樹第k層節(jié)點個數(shù)（假設從第1層開始）
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k-1) 
        + BinaryTreeLevelKSize(root->_right, k-1);
    //遞歸每次讓k-1，當k的值為1的時候，那么此時我們就來到了第k層
}

//二叉樹深度
int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return fmax(BinaryTreeHeight(root->_left)
        , BinaryTreeHeight(root->_right))+1;
}

4.查找值為x的節(jié)點

該遞歸過程可以理解為前序思想，即如果根節(jié)點的值為x，那么肯定就可以直接返回，如果不同，我們就可以向左子樹和右子樹方向考慮，具體的設計可見代碼。

代碼實現(xiàn)：

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	BTNode* ret = NULL;
	ret = BinaryTreeFind(root->_left,x);
	if (ret)
	{
		return ret;
	}
	ret = BinaryTreeFind(root->_right, x);
	if (ret)
	{
		return ret;
	}
	return NULL;
}

5.前中后序遍歷

代碼實現(xiàn)：

// 二叉樹前序遍歷 
void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_left);
	BinaryTreeInOrder(root->_right);
}

// 二叉樹中序遍歷
void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}

// 二叉樹后序遍歷
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeInOrder(root->_left);
	BinaryTreeInOrder(root->_right);
	printf("%c ", root->_data);
}

6.層序遍歷

層序遍歷的實現(xiàn)需要用到隊列的邏輯結(jié)構(gòu)。

首先將根節(jié)點入隊，輸出隊首元素，并根據(jù)根節(jié)點找到左右孩子節(jié)點并入隊，然后出隊根節(jié)點，此時隊首元素更新為根節(jié)點的左子樹，再以此左子樹為根循環(huán)這個過程，就能成功實現(xiàn)層序遍歷。

代碼實現(xiàn)：

void BinaryTreeLevelOrder(BTNode* root)
{
	Que q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%c ", front->_data);
		if (front->_left)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right)
		{
			QueuePush(&q, front->_right);
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
	return;
}

7.判斷二叉樹是否為完全二叉樹

完全二叉樹通俗的講就是每個節(jié)點都是連續(xù)的，不存在某個節(jié)點之前存在空節(jié)點的情況，那么根據(jù)這個特性，我們同樣可以利用層序遍歷的思想，利用隊列的邏輯結(jié)構(gòu)來解決。

思路：與層序遍歷不同的是，我們不管左右子樹是否為空都入隊，這樣在循環(huán)結(jié)束時，隊列中要么全為空，此時證明該二叉樹是完全二叉樹，如果隊列中但凡存在一個不為空的情況，那就證明該二叉樹不為完全二叉樹。

代碼實現(xiàn)：

bool BinaryTreeComplete(BTNode* root)
{
	Que q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
		QueuePop(&q);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

注意：循環(huán)條件中QueueEmpty判斷的是隊列是否為空，即隊首指針指向是否為空，而第一次遍歷隊列判斷的條件是隊首元素的數(shù)據(jù)域是否為NULL，兩者不一樣。?

總結(jié)

遞歸是一種十分巧妙的方法，他的特點是可以拆分子問題，將大問題簡化為可以解決小問題，但不知道你是否和我一樣，思考問題好像已經(jīng)習慣了遍歷枚舉求解的思想，那么下一篇文章我會為大家?guī)?span style="color:#1c7892;">二叉樹的OJ題系列，強化對于遞歸問題的理解，讓我們一起努力吧??

=========================================================================

如果你對該系列文章有興趣的話，歡迎持續(xù)關注博主動態(tài)，博主會持續(xù)輸出優(yōu)質(zhì)內(nèi)容

??博主很需要大家的支持，你的支持是我創(chuàng)作的不竭動力??

??~ 點贊收藏＋關注 ~??

=========================================================================

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