国产 无码 综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

  1. Toy模板網(wǎng)首頁(yè)
  2. >Toy博客

【數(shù)據(jù)結(jié)構(gòu)】二叉樹(shù)遍歷的實(shí)現(xiàn)（超詳細(xì)解析，小白必看系列）

2年前作者：sunny-ll分類(lèi)：Toy博客閱讀(20)違法舉報(bào)

這篇具有很好參考價(jià)值的文章主要介紹了【數(shù)據(jù)結(jié)構(gòu)】二叉樹(shù)遍歷的實(shí)現(xiàn)（超詳細(xì)解析，小白必看系列）。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

目錄

一、前言

??為何使用鏈?zhǔn)蕉鏄?shù)?

???何為鏈?zhǔn)蕉鏄?shù)

???二叉樹(shù)的構(gòu)建

??創(chuàng)建二叉鏈結(jié)構(gòu)

??手動(dòng)構(gòu)建一顆樹(shù)?

??二叉樹(shù)的遍歷 （重點(diǎn)）

??前序遍歷

???中序遍歷

???后續(xù)遍歷

???二叉樹(shù)的經(jīng)典問(wèn)題（重點(diǎn)）

??二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)

???二叉樹(shù)葉子節(jié)點(diǎn)的個(gè)數(shù)

???二叉樹(shù)第K層節(jié)點(diǎn)個(gè)數(shù)

???二叉樹(shù)的深度

???二叉樹(shù)查找值為x的節(jié)點(diǎn)?

???二叉樹(shù)的銷(xiāo)毀

??總代碼和演示圖

二、共勉

一、前言

在之前的文章中，已經(jīng)詳細(xì)的講解了二叉樹(shù)、堆等問(wèn)題，所以本次博客將繼續(xù)延續(xù)之前的知識(shí)點(diǎn)，講解鏈?zhǔn)蕉鏄?shù)的遍歷和一些經(jīng)典問(wèn)題。

??為何使用鏈?zhǔn)蕉鏄?shù)?

在前幾篇博文中，我們學(xué)習(xí)的都是完全二叉樹(shù)或滿二叉樹(shù)，而這兩個(gè)都是可以用數(shù)組來(lái)實(shí)現(xiàn)的，但是如果不是完全二叉樹(shù)呢？回顧下曾經(jīng)學(xué)過(guò)的知識(shí)點(diǎn)：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

?
由上圖得知，普通二叉樹(shù)也可以使用數(shù)組來(lái)存儲(chǔ)，但是會(huì)存在大量的空間浪費(fèi)，而完全二叉樹(shù)就不會(huì)這樣，因?yàn)槠淇臻g利用率是％100的。既然這樣，那普通二叉樹(shù)該如何進(jìn)行存儲(chǔ)呢？答案是使用鏈?zhǔn)浇Y(jié)構(gòu)進(jìn)行存儲(chǔ)。

???何為鏈?zhǔn)蕉鏄?shù)

  • ?鏈?zhǔn)浇Y(jié)構(gòu)分為兩種：二叉鏈和三叉鏈

??先看下代碼結(jié)構(gòu)：

typedef int BTDataType;
// 二叉鏈
struct BinaryTreeNode
{
	struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
	struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
	BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
};
// 三叉鏈
struct BinaryTreeNode
{
	struct BinTreeNode* _pParent; // 指向當(dāng)前節(jié)點(diǎn)的雙親
	struct BinTreeNode* _pLeft; // 指向當(dāng)前節(jié)點(diǎn)左孩子
	struct BinTreeNode* _pRight; // 指向當(dāng)前節(jié)點(diǎn)右孩子
	BTDataType _data; // 當(dāng)前節(jié)點(diǎn)值域
};
?? 畫(huà)圖演示：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


? 注意：鏈?zhǔn)蕉鏄?shù)和我們之前的學(xué)習(xí)略有差別。以前我們學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)無(wú)非就是增刪查改這些東西，而鏈?zhǔn)蕉鏄?shù)不太關(guān)注這塊的增刪查改。因?yàn)槠胀ǘ鏄?shù)的增刪查改沒(méi)有意義。如下的二叉樹(shù)：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


鏈?zhǔn)蕉鏄?shù)是要比之前鏈表啥的更加復(fù)雜的，如果只是單純的讓鏈?zhǔn)蕉鏄?shù)存儲(chǔ)數(shù)據(jù)的話，價(jià)值就不大了，不如使用線性表。接下來(lái)，我將通過(guò)其遍歷方式，結(jié)點(diǎn)個(gè)數(shù)……為大家展開(kāi)討論。此節(jié)內(nèi)容是為了后續(xù)學(xué)習(xí)更復(fù)雜的搜索二叉樹(shù)打基礎(chǔ)，具體是啥后面再談。
?

在具體講解之前，再回顧下二叉樹(shù)，二叉樹(shù)是：

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

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


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

???二叉樹(shù)的構(gòu)建

??創(chuàng)建二叉鏈結(jié)構(gòu)

創(chuàng)建二叉鏈結(jié)構(gòu)其實(shí)就很easy了，也就是創(chuàng)建一個(gè)結(jié)構(gòu)體罷了，這種在先前已經(jīng)寫(xiě)過(guò)很多，咱就是說(shuō)直接上代碼：

// 二叉樹(shù)結(jié)構(gòu)體
typedef struct BrinyTree
{
	struct BrinyTree* left;
	struct BrinyTree* right;
	int data;
}BT;

??手動(dòng)構(gòu)建一顆樹(shù)?

其實(shí)構(gòu)建一棵樹(shù)的思想還是挺簡(jiǎn)單的，按照?qǐng)D示創(chuàng)建6個(gè)節(jié)點(diǎn)，并根據(jù)圖中的樣子將節(jié)點(diǎn)順次鏈接起來(lái)

// 創(chuàng)建一個(gè)節(jié)點(diǎn) （有返回值，返回值類(lèi)型為---結(jié)構(gòu)體指針）
BT* BuyNode(int x)
{
	BT* newnode = (BT*)malloc(sizeof(BT));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(-1);
	}
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

// 創(chuàng)建一個(gè)樹(shù)
BT* CreatBinaryTree()
{
	// 創(chuàng)建6個(gè)節(jié)點(diǎn)
	BT* node1 = BuyNode(1);
	BT* node2 = BuyNode(2);
	BT* node3 = BuyNode(3);
	BT* node4 = BuyNode(4);
	BT* node5 = BuyNode(5);
	BT* node6 = BuyNode(6);

	//將結(jié)點(diǎn)連接起來(lái)，構(gòu)成自己想要的樹(shù)
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

??二叉樹(shù)的遍歷 （重點(diǎn)）

以一顆二叉樹(shù)為例：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

后續(xù)的遍歷均是建立在次二叉樹(shù)基礎(chǔ)上展開(kāi)。?
?

??前序遍歷

  • ?遍歷規(guī)則：

前序遍歷，也叫先根遍歷

遍歷順序：根?->?左子樹(shù)?->?右子樹(shù)

  • 思路：

既然先從根走，根就是1，接下來(lái)訪問(wèn)1的左子樹(shù)，此時(shí)又要先訪問(wèn)其左子樹(shù)的根為2，接著再訪問(wèn)2的左子樹(shù)->根：3，接著訪問(wèn)其左子樹(shù)和右子樹(shù)，不過(guò)均為空，遞歸返回，此時(shí)3作為2的左子樹(shù)訪問(wèn)完畢，訪問(wèn)2的右子樹(shù)為NULL，再遞歸返回此時(shí)1的左子樹(shù)就訪問(wèn)完畢了，訪問(wèn)其右子樹(shù)，同理訪問(wèn)左樹(shù)4，再訪問(wèn)左樹(shù)5，接著左右子樹(shù)NULL，遞歸返回訪問(wèn)4的右樹(shù)，……類(lèi)似的

  • 圖示：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

  • ?代碼演示：

前序遍歷的代碼非常簡(jiǎn)潔，短短幾行即可操作，先看代碼：

// 前序遍歷 根 左 右
void  PrevOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL "); // 如果為空，就打印
		return;      // 當(dāng)前函數(shù)結(jié)束
	}
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
  • 效果如下：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言
跟我們先前畫(huà)的圖一模一樣，讓我們通過(guò)一副遞歸圖來(lái)深刻理解其原理：

  • 遞歸圖：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

???中序遍歷

  • ?遍歷規(guī)則：

中序遍歷，也叫中根遍歷

遍歷順序：左子樹(shù)?->?根結(jié)點(diǎn)?->?右子樹(shù)

  • 思路：

根據(jù)遍歷順序，我們得知，如若想訪問(wèn)1，得先訪問(wèn)其左子樹(shù)2，訪問(wèn)2還得先訪問(wèn)其左子樹(shù)3，類(lèi)似的，再訪問(wèn)其左子樹(shù)為NULL，遞歸返回訪問(wèn)根結(jié)點(diǎn)3，再訪問(wèn)右子樹(shù)NULL，遞歸返回訪問(wèn)根結(jié)點(diǎn)2，再訪問(wèn)右子樹(shù)NULL，遞歸返回訪問(wèn)根結(jié)點(diǎn)1，再訪問(wèn)其右子樹(shù)，1的右子樹(shù)訪問(wèn)規(guī)律同1的左子樹(shù)，這里不過(guò)多贅述。

  • 畫(huà)圖演示：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


?

  • ?代碼演示：

中序遍歷的代碼和前序遍歷一樣，看起來(lái)都非常簡(jiǎn)潔：

// 中序遍歷  左 根 右
void InOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL "); // 如果為空，就打印
		return;      // 當(dāng)前函數(shù)結(jié)束
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
  • 效果如下：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


單純看代碼看不出啥頭緒，還得是畫(huà)遞歸圖。

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


?

???后續(xù)遍歷

  • ?遍歷規(guī)則：

后續(xù)遍歷，也叫后根遍歷

遍歷順序：左子樹(shù)?->?右子樹(shù)?->?根結(jié)點(diǎn)

  • 思路：

要訪問(wèn)1得先訪問(wèn)1的左子樹(shù)2，繼而得先訪問(wèn)2的左子樹(shù)3，再先訪問(wèn)3的左子樹(shù)NULL，右子樹(shù)NULL，根3，遞歸返回訪問(wèn)2的右子樹(shù)NULL，根2，再遞歸返回訪問(wèn)1的右子樹(shù)……類(lèi)似的

  • 畫(huà)圖演示：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

  • 代碼演示：
// 后序 左 右 根
void PosOrder(BT* root)
{
	if (root == NULL)
	{
		printf("NULL "); // 如果為空，就打印
		return;      // 當(dāng)前函數(shù)結(jié)束
	}
	PosOrder(root->left);
	PosOrder(root->right);
	printf("%d ", root->data);
}
  • 效果如下：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

  • 畫(huà)圖演示遞歸過(guò)程：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言
?

???二叉樹(shù)的經(jīng)典問(wèn)題（重點(diǎn)）

??二叉樹(shù)節(jié)點(diǎn)個(gè)數(shù)

  • ?思想：

求結(jié)點(diǎn)個(gè)數(shù)，這里我將提供如下幾種方法，但不都是可行的，要對(duì)比著看，本質(zhì)都是遞歸的思想：

  • 法一：遍歷

在前文中，我們已經(jīng)學(xué)習(xí)了如何遍歷鏈?zhǔn)蕉鏄?shù)，現(xiàn)在想求結(jié)點(diǎn)的個(gè)數(shù)，那么只需要隨便采用一種遍歷方式，并把打印換成計(jì)數(shù)++來(lái)求個(gè)數(shù)即可，聽(tīng)起來(lái)非常容易，先看代碼：

//節(jié)點(diǎn)個(gè)數(shù)
void BTreeSize(BTNode* root)
{
	int count = 0; //局部變量
	if (root == NULL) //如果為空
		return;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
}

難道上述代碼能夠準(zhǔn)確求出結(jié)點(diǎn)個(gè)數(shù)嗎？其實(shí)不然，根本求不出來(lái)。


具體解釋起來(lái)需要借用棧幀的思想，因?yàn)檫@里用的是遞歸，而遞歸是每遞歸一次在棧幀里頭都會(huì)開(kāi)辟一塊空間，每一塊棧幀都會(huì)有一個(gè)count，而我希望的是只需要有一個(gè)count，然后所有的count均加在一起，可是現(xiàn)在每遞歸一次，重新開(kāi)辟一個(gè)count，count即局部變量。遞歸完就銷(xiāo)毀，同形參的改變不會(huì)影響實(shí)參一樣，一個(gè)道理。所有此法根本就行不通，得換。
?

  • 法二：定義局部靜態(tài)變量count

在法一中，我們定義的是局部變量count，會(huì)導(dǎo)致每遞歸一次就開(kāi)辟棧幀，并創(chuàng)建count，每次遞歸結(jié)束返回就銷(xiāo)毀棧幀。那如果可以把count放在靜態(tài)區(qū)里頭，不久可以保留住count嗎

//節(jié)點(diǎn)個(gè)數(shù)
int BTreeSize(BTNode* root)
{
	static int count = 0; //局部靜態(tài)變量
	if (root == NULL) //如果為空
		return count;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
	return count;
}
  • 效果如下：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

看似好像是成功了，確實(shí)結(jié)點(diǎn)個(gè)數(shù)為6，但真的就是成功了嗎？當(dāng)然不是，如果我們現(xiàn)在想多打印幾次呢？
什么鬼？怎么size還呈現(xiàn)等差數(shù)列遞增呢？就是因?yàn)檫@里運(yùn)用了static關(guān)鍵字，將count扣在靜態(tài)區(qū)，導(dǎo)致多次調(diào)用沒(méi)辦法初始化為0，使其每次遞歸調(diào)用累計(jì)加加，但是當(dāng)你再重新調(diào)用自己時(shí)，count不會(huì)重新置為0，會(huì)依舊保留為曾經(jīng)++的結(jié)果。局部的靜態(tài)變量有一個(gè)好處，它的生命周期在全局，但是只能在局部去訪問(wèn)。它的初始化為0只有第一次調(diào)用會(huì)訪問(wèn)，其余均不會(huì)。由此可見(jiàn)，局部的靜態(tài)也是不行的，還得再優(yōu)化。
?

  • 法三：定義全局變量count

法二的局部靜態(tài)變量行不通，那就把count設(shè)定為全局變量。要知道全局變量是存在靜態(tài)區(qū)的。雖然也在靜態(tài)區(qū)，但是其初始化為0是可以重復(fù)訪問(wèn)的。
?

//節(jié)點(diǎn)個(gè)數(shù)
int count = 0;
void BTreeSize(BTNode* root)
{
	if (root == NULL) //如果為空
		return;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
}
  • 效果如下：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


確實(shí)可以求出結(jié)點(diǎn)個(gè)數(shù)，并且也不會(huì)出現(xiàn)像法二一樣的問(wèn)題。但是其實(shí)定義全局變量也會(huì)存在一個(gè)小問(wèn)題：線程安全的問(wèn)題，這個(gè)等以后學(xué)到Linux再來(lái)討論，我們這邊考慮再換一種更優(yōu)解。

  • 法四：最優(yōu)解

我們這里可以考慮多套一層，可以考慮把變量的地址傳過(guò)去。這樣操作不會(huì)存在任何問(wèn)題，上代碼：
?

//節(jié)點(diǎn)個(gè)數(shù)
void BTreeSize(BTNode* root, int* pCount)
{
	if (root == NULL) //如果為空
		return;
	++(*pCount);
	BTreeSize(root->left, pCount);
	BTreeSize(root->right, pCount);
}

確實(shí)可以求出結(jié)點(diǎn)個(gè)數(shù)，并且也不會(huì)出現(xiàn)像法二一樣的問(wèn)題。但是其實(shí)定義全局變量也會(huì)存在一個(gè)小問(wèn)題：線程安全的問(wèn)題，這個(gè)等以后學(xué)到Linux再來(lái)討論，我們這邊考慮再換一種更優(yōu)解。

  • 法五：新思路

直接利用子問(wèn)題的思想來(lái)寫(xiě)，返回當(dāng)root為空為0，不是就遞歸左樹(shù)+右樹(shù)+1。

  1. 空樹(shù)，最小規(guī)模子問(wèn)題，結(jié)點(diǎn)個(gè)數(shù)返回0
  2. 非空，左子樹(shù)結(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)結(jié)點(diǎn)個(gè)數(shù) + 1（自己）
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
    BTreeSize(root->left) + 
    BTreeSize(root->right) + 1;
}

此法非常巧妙，很靈活的運(yùn)用了遞歸的思想，我們通過(guò)遞歸圖來(lái)深刻理解下：
?

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


?

???二叉樹(shù)葉子節(jié)點(diǎn)的個(gè)數(shù)

  • ?思路1：遍歷+計(jì)數(shù)

在遍歷的基礎(chǔ)上如果結(jié)點(diǎn)的左右子樹(shù)均為空則count++。但是此題我們依舊采用分治思想。

// 計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)
// 遍歷 + 計(jì)數(shù)
void TreeLeveSize1(BT* root, int* count)
{
    if(root==NULL)
    {
        return ;
    }
    if(root->left==NULL&&root->right==NULL)
    {
        (*count)++;
    }
    TreeLeveSize1(root->left,count);
    TreeLeveSize1(root->right,count);

}
  • ?思路2：遍歷+遞歸
// 葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeveSize2(BT*root)
{
    if(root==NULL)
    {
        return 0;
    }
    int left = TreeLeveSize2(root->left);
    int right = TreeLeveSize2(root->right);
    if(left==0&&right==0)
    {
        return 1;
    }
    return left+right;
}
  • 思路3：分治思想

首先，如果為空，直接返回0，如若結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)均為空，則為葉節(jié)點(diǎn)，此時(shí)返回1，其它的繼續(xù)分治遞歸。

  • 代碼演示：
/ 計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeveSize(BT* root)
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->left==NULL&&root->right==NULL)
    {
        return 1;
    }
    return TreeLeveSize(root->left)+TreeLeveSize(root->right);
}
  • 遞歸圖：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言


?

???二叉樹(shù)第K層節(jié)點(diǎn)個(gè)數(shù)

  • ?思路：

假設(shè)K=3

  1. 空樹(shù)，返回0
  2. 非空，且K == 1，返回1
  3. 非空，且K>1，轉(zhuǎn)換成左子樹(shù)K-1層節(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)K-1層節(jié)點(diǎn)個(gè)數(shù)
  • 代碼演示：
// 樹(shù)的第K層節(jié)點(diǎn)個(gè)數(shù)
// 1. 當(dāng)前樹(shù)的第K層 = 左子樹(shù)的第K-1層 + 右子樹(shù)的第K-1層
int TreeKSize(BT* root, int k)
{
	assert(k > 0);
	// 給出 所問(wèn) 問(wèn)題 能成成立的條件（所問(wèn)，問(wèn)題的的結(jié)束條件）
	if (root == NULL)
	{
		return 0;
	}

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

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

}
  • 遞歸圖：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言
?

???二叉樹(shù)的深度

  • ?思路：

此題同樣是運(yùn)用分治的思想來(lái)解決，要比較左子樹(shù)的高度和右子樹(shù)的高度，大的那個(gè)就+1，因?yàn)檫€有根結(jié)點(diǎn)也算1個(gè)高度。

  • 代碼演示：
// 樹(shù)的深度
int TreeDeep(BT* root)
{
    if(root==NULL)
    {
        return 0;
    }
    int left = TreeDeep(root->left);
    int right = TreeDeep(root->right);
    if(left>right)
    {
        return left+1;
    }
    else
    {
        return right+1;
    }

}
  • 遞歸圖：

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言
?

???二叉樹(shù)查找值為x的節(jié)點(diǎn)?

  • ?思路：

還是利用分治的思想，將其遞歸化成子問(wèn)題去解決

  1. 先去根結(jié)點(diǎn)尋找，是就返回此節(jié)點(diǎn)
  2. 此時(shí)去左子樹(shù)查找有無(wú)節(jié)點(diǎn)x
  3. 最后再去右子數(shù)去查找有無(wú)節(jié)點(diǎn)x
  4. 若左右子樹(shù)均找不到節(jié)點(diǎn)x，直接返回空
  • 代碼演示：
// 查詢 樹(shù)中的某一個(gè)節(jié)點(diǎn)是否存在
BT* TreeNode(BT* root,TreeDatatype x)
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->data==x)
    {
        return root;
    }
    BT* left = TreeNode(root->left,x);
    BT* right = TreeNode(root->right,x);

    if(left!=NULL)
    {
        return left;
    }
    if(right!=NULL)
    {
        return right;
    }
    return NULL;
}
  • 遞歸圖：

假設(shè)我們尋找的是數(shù)字5
從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言
?

???二叉樹(shù)的銷(xiāo)毀

  • ?思路：

銷(xiāo)毀的思想和遍歷類(lèi)似，如若我挨個(gè)遍歷的同時(shí)，沒(méi)遍歷一次就銷(xiāo)毀一次，豈不能達(dá)到效果，但是又會(huì)存在一個(gè)問(wèn)題，那就是你要采用什么樣的遍歷方式？倘若你采用前序遍歷，剛開(kāi)始就把根銷(xiāo)毀了，那么后面的子樹(shù)還怎么銷(xiāo)毀呢？因?yàn)榇藭r(shí)根沒(méi)了，子樹(shù)找不到了就，所以要采用倒著銷(xiāo)毀的規(guī)則，也就是后續(xù)的思想

  • 代碼演示：
// 二叉樹(shù)的銷(xiāo)毀
// 從后往前銷(xiāo)毀-------后續(xù)思想
// 進(jìn)行遍歷然后在銷(xiāo)毀
void DestoryTree(BT*root)
{
    if(root==NULL)
    {
        return;
    }
    DestoryTree(root->left);
    DestoryTree(root->right);
    free(root);
}

思想和后續(xù)遍歷類(lèi)似，不做遞歸圖演示。
?

??總代碼和演示圖

???代碼

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int TreeDatatype;

typedef struct BinaryTree
{
    struct BinaryTree* left;
    struct BinaryTree* right;
    TreeDatatype data;
}BT;


BT* BuyTreenode(TreeDatatype x)
{
    BT* tree = (BT*)malloc(sizeof(BT));

    if(tree==NULL)
    {
        perror(" fail");
        exit(-1);
    }
    tree->data = x;
    tree->left = tree->right = NULL;

    return tree;
}

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

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

    return node1;
}


// 前序遍歷：根 左 右
void PreOrder(BT* root)
{
    if(root==NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ",root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

// 中序遍歷
void InOrder(BT*root)
{
    if(root==NULL)
    {
        printf("NULL");
        return;
    }
    InOrder(root->left);
    printf("%d ",root->data);
    InOrder(root->right);
}


// 后序遍歷
void PastOrder(BT* root)
{
    if(root==NULL)
    {
        printf("NULL");
        return;
    }
    PastOrder(root->left);
    PastOrder(root->right);
    printf("%d ",root->data);
}


// 計(jì)算一顆樹(shù)的節(jié)點(diǎn)個(gè)數(shù)
int TreeSize(BT* root)
{
    if(root==NULL)
    {
        return 0;
    }

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

// 計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeveSize(BT* root)
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->left==NULL&&root->right==NULL)
    {
        return 1;
    }
    return TreeLeveSize(root->left)+TreeLeveSize(root->right);
}

// 計(jì)算葉子節(jié)點(diǎn)個(gè)數(shù)
// 遍歷 + 計(jì)數(shù)
void TreeLeveSize1(BT* root, int* count)
{
    if(root==NULL)
    {
        return ;
    }
    if(root->left==NULL&&root->right==NULL)
    {
        (*count)++;
    }
    TreeLeveSize1(root->left,count);
    TreeLeveSize1(root->right,count);

}

// 葉子節(jié)點(diǎn)個(gè)數(shù)
int TreeLeveSize2(BT*root)
{
    if(root==NULL)
    {
        return 0;
    }
    int left = TreeLeveSize2(root->left);
    int right = TreeLeveSize2(root->right);
    if(left==0&&right==0)
    {
        return 1;
    }
    return left+right;
}


// 樹(shù)的第 K 層的節(jié)點(diǎn)
int TreeKLeveSize(BT* root,int k)
{
    if(root==NULL)
    {
        return 0;
    }
    if(k==1)
    {
        return 1;
    }
    return TreeKLeveSize(root->left,k-1)+TreeKLeveSize(root->right,k-1);
}

// 樹(shù)的深度
int TreeDeep(BT* root)
{
    if(root==NULL)
    {
        return 0;
    }
    int left = TreeDeep(root->left);
    int right = TreeDeep(root->right);
    if(left>right)
    {
        return left+1;
    }
    else
    {
        return right+1;
    }

}


// 查詢 樹(shù)中的某一個(gè)節(jié)點(diǎn)是否存在
BT* TreeNode(BT* root,TreeDatatype x)
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->data==x)
    {
        return root;
    }
    BT* left = TreeNode(root->left,x);
    BT* right = TreeNode(root->right,x);

    if(left!=NULL)
    {
        return left;
    }
    if(right!=NULL)
    {
        return right;
    }
    return NULL;
}

// 二叉樹(shù)的銷(xiāo)毀
// 從后往前銷(xiāo)毀-------后續(xù)思想
// 進(jìn)行遍歷然后在銷(xiāo)毀
void DestoryTree(BT*root)
{
    if(root==NULL)
    {
        return;
    }
    DestoryTree(root->left);
    DestoryTree(root->right);
    free(root);
}



int main()
{
    BT* tree = CreatTree();

    printf("樹(shù)的前序遍歷 >\n");
    PreOrder(tree);
    printf("\n");
    printf("\n");
    printf("樹(shù)的中序遍歷 >\n");
    InOrder(tree);
    printf("\n");
    printf("\n");

    printf("樹(shù)的后序遍歷 >\n");
    PastOrder(tree);
    printf("\n");
    printf("\n");

    int size = 0;
    printf("樹(shù)的節(jié)點(diǎn)個(gè)數(shù)\n");
    size = TreeSize(tree);
    printf("%d\n",size);

    printf("\n");
    int sizeLeve = 0;
    printf("樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)\n");
    int i = 0;
    TreeLeveSize1(tree,&i);
    printf("%d\n",i);
    printf("\n");

    int SizeLeve = 0;
    printf("樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)1\n");
    SizeLeve = TreeLeveSize2(tree);
    printf("%d\n",SizeLeve);
    printf("\n");

    int ksize = 0;
    printf("樹(shù)的第K層節(jié)點(diǎn)個(gè)數(shù)\n");
    ksize = TreeKLeveSize(tree,3);
    printf("%d \n",ksize);
    printf("\n");

    int deep = 0;
    printf("樹(shù)的深度\n");
    deep = TreeDeep(tree);
    printf("%d \n",deep);
    printf("\n");
    printf("\n");

    BT* tre;
    int x;
    printf("請(qǐng)輸入你要在樹(shù)中查詢的數(shù)值：>\n");
    scanf("%d",&x);
    tre = TreeNode(tree,x);
    if(tre==NULL)
    {
        printf("沒(méi)有你要查詢的數(shù)據(jù)");
    }
    else
    {
         printf("查詢到了：%d\n",tre->data);
    }

    // 銷(xiāo)毀這顆樹(shù)
    DestoryTree(tree);
    tree = NULL;
    return 0;
}

??視圖
從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言

二、共勉

以下就是我對(duì)數(shù)據(jù)結(jié)構(gòu)---二叉樹(shù)遍歷的理解，如果有不懂和發(fā)現(xiàn)問(wèn)題的小伙伴，請(qǐng)?jiān)谠u(píng)論區(qū)說(shuō)出來(lái)哦，同時(shí)我還會(huì)繼續(xù)更新對(duì)數(shù)據(jù)結(jié)構(gòu)-------二叉樹(shù)的面試題型，請(qǐng)持續(xù)關(guān)注我哦?。。。?！??

從此節(jié)點(diǎn)開(kāi)始遍歷二叉樹(shù),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),算法,c語(yǔ)言文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-786627.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】二叉樹(shù)遍歷的實(shí)現(xiàn)（超詳細(xì)解析，小白必看系列）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來(lái)自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場(chǎng)。本站僅提供信息存儲(chǔ)空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請(qǐng)注明出處： 如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實(shí)不符，請(qǐng)點(diǎn)擊違法舉報(bào)進(jìn)行投訴反饋，一經(jīng)查實(shí)，立即刪除！

領(lǐng)支付寶紅包贊助服務(wù)器費(fèi)用

相關(guān)文章

覺(jué)得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

請(qǐng)作者喝杯咖啡吧~博客贊助

支付寶掃一掃領(lǐng)取紅包，優(yōu)惠每天領(lǐng)

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包