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

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

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）

2年前作者：手法king分類：Toy博客閱讀(23)違法舉報(bào)

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

目錄

一，二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)

二，二叉鏈的接口實(shí)現(xiàn)

????????1，二叉鏈的創(chuàng)建

????????2，接口函數(shù)

????????3，動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)

????????4，創(chuàng)建二叉樹

????????5，前序遍歷

????????6，中序遍歷

????????7，后序遍歷

三，結(jié)點(diǎn)個(gè)數(shù)以及高度等

????????1，接口函數(shù)

????????2，結(jié)點(diǎn)個(gè)數(shù)

????????3，葉子結(jié)點(diǎn)個(gè)數(shù)

????????4，二叉樹高度

????????5，二叉樹第k層結(jié)點(diǎn)個(gè)數(shù)

????????6，二叉樹查找值為x的結(jié)點(diǎn)

一，二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關(guān)系；

通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址 。

鏈?zhǔn)浇Y(jié)構(gòu)又分為二叉鏈和三叉鏈，這里我們學(xué)習(xí)二叉鏈；

?二叉樹是：

1，空樹

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

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

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

?二叉鏈結(jié)構(gòu)圖示；

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

二，二叉鏈的接口實(shí)現(xiàn)

????????1，二叉鏈的創(chuàng)建

typedef int BTDataType;
//二叉鏈
typedef struct BinaryTreeNode
{
	BTDataType data; // 當(dāng)前結(jié)點(diǎn)值域	
	struct BinaryTreeNode* left; // 指向當(dāng)前結(jié)點(diǎn)左孩子
	struct BinaryTreeNode* right; // 指向當(dāng)前結(jié)點(diǎn)右孩子
}BTNode;

首先創(chuàng)建一個(gè)結(jié)構(gòu)體表示二叉鏈，data是當(dāng)前結(jié)點(diǎn)的值域，BTDataType是儲(chǔ)存的值的數(shù)據(jù)類型；

left是指向當(dāng)前結(jié)點(diǎn)左孩子，right是指向當(dāng)前結(jié)點(diǎn)右孩子；

這里的BTDataType是int的重命名，也可以說是數(shù)據(jù)類型的重命名，這樣統(tǒng)一化方便后續(xù)更改；

????????2，接口函數(shù)

//動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
BTNode* BuyNode(BTDataType x);
//創(chuàng)建二叉樹
BTNode* GreatBTree();
//前序遍歷
void PrevOrder(BTNode* root);
//中序遍歷
void InOrder(BTNode* root);
//后序遍歷
void PostOrder(BTNode* root);

這是以上要實(shí)現(xiàn)的接口函數(shù)；

????????3，動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)

//動(dòng)態(tài)創(chuàng)立新結(jié)點(diǎn)
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	assert(newnode);
	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}

后面創(chuàng)立新結(jié)點(diǎn)時(shí)直接調(diào)用此函數(shù)，一定要向堆區(qū)申請(qǐng)空間，這樣函數(shù)結(jié)束空間會(huì)保留不會(huì)被回收；

將data賦新值，left與right都指向空，再返回結(jié)點(diǎn)指針即可；

????????4，創(chuàng)建二叉樹

//創(chuàng)建二叉樹
BTNode* GreatBTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

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

	return node1;
}

然后我們申請(qǐng)結(jié)點(diǎn)來構(gòu)造二叉樹，通過鏈接將新結(jié)點(diǎn)鏈接起來；

創(chuàng)建的二叉樹結(jié)構(gòu)圖示如下：

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

????????5，前序遍歷

//前序遍歷
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

二叉樹的前序，中序，后續(xù)遍歷都是同一種思路：

1. 前序遍歷(Preorder Traversal 亦稱先序遍歷)——根結(jié)點(diǎn)---->左子樹--->右子樹

2. 中序遍歷(Inorder Traversal)——左子樹--->根結(jié)點(diǎn)--->右子樹

3. 后序遍歷(Postorder Traversal)——左子樹--->右子樹--->根結(jié)點(diǎn)

這里要用到遞歸思想：這里NULL用N表示，建議畫圖來理解，一層一層遍歷下去；

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

前序遍歷：

先訪問根結(jié)點(diǎn)（1）然后訪問其左子樹（2）；打印 1

此時(shí)根結(jié)點(diǎn)為（2）然后訪問其左子樹（3）；打印1 2

此時(shí)根結(jié)點(diǎn)為（3）然后訪問其左子樹（NULL）；打印1 2 3

此時(shí)根結(jié)點(diǎn)為（NULL）return NULL到（3），然后訪問（3）的右子樹（NULL）；打印1 2 3 N

此時(shí)根結(jié)點(diǎn)為（NULL）return NULL到（3），此時(shí)對(duì)（3）也就是對(duì)（2）的左子樹的訪問結(jié)束了，然后訪問（2）的右子樹（NULL)；打印1 2 3 N N

此時(shí)根結(jié)點(diǎn)為（NULL）return NULL到（2），此時(shí)對(duì)（2）也就是對(duì)（1）的左子樹訪問結(jié)束了，然后訪問（1）的右子樹（4）；打印1 2 3 N N N

此時(shí)根結(jié)點(diǎn)為（4）然后訪問其左子樹（5）；打印1 2 3 N N N 4

此時(shí)根結(jié)點(diǎn)為（5）然后訪問其左子樹（NULL）；打印1 2 3 N N N 4 5

此時(shí)根結(jié)點(diǎn)為（NULL）return NULL到（5）然后訪問（5）的右子樹（NULL）；打印1 2 3 N N N 4 5 N

此時(shí)根結(jié)點(diǎn)為（NULL）return NULL到（5）此時(shí)對(duì)（5）也就是對(duì)（4）的左子樹的訪問結(jié)束了，然后訪問（4）的右子樹（6）；打印 1 2 3 N N N 4 5 N N

此時(shí)根結(jié)點(diǎn)為（6）然后訪問其左子樹（NULL）；打印1 2 3 N N N 4 5 N N 6

此時(shí)根結(jié)點(diǎn)為（NULL）return NULL到（6）然后訪問（6）的右子樹（NULL）；打印1 2 3 N N N 4 5 N N 6 N

此時(shí)根結(jié)點(diǎn)為（NULL）return NULL到（6），此時(shí)對(duì)（6）也就是對(duì)（4）的右子樹的訪問結(jié)束了，此時(shí)對(duì)（4）也就是對(duì)（1）的右子樹的訪問結(jié)束了，此時(shí)對(duì)（1）的訪問也結(jié)束了，前序遍歷也就結(jié)束了；打印1 2 3 N N N 4 5 N N 6 N N

圖解思路示例：

? ??【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

BTNode* root = GreatBTree();
//前序遍歷
PrevOrder(root);

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

這就是前序遍歷；

????????6，中序遍歷

//中序遍歷
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

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

跟前序遍歷思路一致，就是換了一下訪問的順序，按照前序遍歷的思路來就完事了；

//中序遍歷
InOrder(root);
printf("\n");

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

????????7，后序遍歷

//后序遍歷
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

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

思路還是一致的，就是換了一下訪問順序，前，中，后序遍歷的思路都是一致的，只要搞清楚其中一個(gè)就全部拿捏了；

//后續(xù)遍歷
PostOrder(root);
printf("\n");

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)?這里對(duì)二叉鏈的基礎(chǔ)遍歷就實(shí)現(xiàn)完全了，有人說還有一個(gè)層序遍歷，這個(gè)遍歷需要用到隊(duì)列，目前C語言階段實(shí)現(xiàn)太過于繁瑣，后序博主會(huì)補(bǔ)上；

三，結(jié)點(diǎn)個(gè)數(shù)以及高度等

像此類問題也都是遞歸問題，更加看重我們對(duì)函數(shù)棧幀的理解；

????????1，接口函數(shù)

//結(jié)點(diǎn)個(gè)數(shù)
int	SumNode(BTNode* root);
//葉子結(jié)點(diǎn)個(gè)數(shù)
int LeafNode(BTNode* root);
//二叉樹高度
int HeightTree(BTNode* root);
//二叉樹第k層結(jié)點(diǎn)個(gè)數(shù)
int BTreeLeveSize(BTNode* root, int k);
//二叉樹查找值為x的結(jié)點(diǎn)
BTNode* BTreeFine(BTNode* root, int x);

以上是要實(shí)現(xiàn)的函數(shù)；

????????2，結(jié)點(diǎn)個(gè)數(shù)

//結(jié)點(diǎn)個(gè)數(shù)
int SumNode(BTNode* root)
{
	return root == NULL ? 0 : SumNode(root->left) + SumNode(root->right) + 1;
}

遞歸其實(shí)說難也難，說不難也不難，是有技巧在里面的；

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

1，大事化小：根結(jié)點(diǎn)為（1）的二叉樹的結(jié)點(diǎn)總和==>左子樹（2）的結(jié)點(diǎn)總和加上右子樹（4）的結(jié)點(diǎn)總和再加上本身的結(jié)點(diǎn)個(gè)數(shù)1，然后根結(jié)點(diǎn)為（2）的結(jié)點(diǎn)總和==>左子樹（3）的總和加上NULL加1，這就是規(guī)律；【（1）=（2）+（4）+1 】

2，結(jié)束條件，當(dāng)結(jié)點(diǎn)為NULL時(shí)返回0；

//結(jié)點(diǎn)個(gè)數(shù)
printf("%d\n", SumNode(root));

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

????????3，葉子結(jié)點(diǎn)個(gè)數(shù)

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

?【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

大事化小：求根結(jié)點(diǎn)為（1）的二叉樹的葉子節(jié)點(diǎn)的個(gè)數(shù)==>其左子樹（2）加上其右子樹（4）的葉子節(jié)點(diǎn)的個(gè)數(shù)；【（1）=（2）+（4）】

結(jié)束條件：當(dāng)結(jié)點(diǎn)為NULL時(shí)返回0，當(dāng)結(jié)點(diǎn)的左右子樹都為NULL時(shí)返回1；

????????4，二叉樹高度

//二叉樹高度
int HeightTree(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left = HeightTree(root->left);
	int right = HeightTree(root->right);
	return left > right ? left + 1 : right + 1;
}

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

大事化小：求根結(jié)點(diǎn)為（1）的二叉樹的高度==>其左子樹（2）與右子樹（4）中高的一顆的高度加上本身的高度1；【（1）=（2）>（4）？（2）+1：（4）+1 】

結(jié)束條件：當(dāng)結(jié)點(diǎn)為NULL時(shí)返回0；

//二叉樹高度
printf("%d\n", HeightTree(root));

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

????????5，二叉樹第k層結(jié)點(diǎn)個(gè)數(shù)

//二叉樹第k層結(jié)點(diǎn)個(gè)數(shù)
int BTreeLeveSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BTreeLeveSize(root->left, k - 1)  + BTreeLeveSize(root->right, k - 1);
}

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

大事化小：求根結(jié)點(diǎn)為（1）的二叉樹第K層的結(jié)點(diǎn)個(gè)數(shù)==>其左子樹（2）加上右子樹（4）中第K-1層結(jié)點(diǎn)的個(gè)數(shù)；【（1）=（2）+（4）】

結(jié)束條件：當(dāng)結(jié)點(diǎn)為NULL時(shí)返回0，當(dāng)K等于1時(shí)返回1；

//二叉樹第k層結(jié)點(diǎn)個(gè)數(shù)
printf("%d\n", BTreeLeveSize(root,3));

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

????????6，二叉樹查找值為x的結(jié)點(diǎn)

//二叉樹查找值為x的結(jié)點(diǎn)
BTNode* BTreeFine(BTNode* root, int x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	if (BTreeFine(root->left, x) == NULL)
	{
		return BTreeFine(root->right, x);
	}
	else
	{
		return BTreeFine(root->left, x);
	}
}

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

大事化小：查找根結(jié)點(diǎn)為（1）的二叉樹中值為x的結(jié)點(diǎn)==>查找其左子樹（2）與右子樹（4）中值為x的結(jié)點(diǎn)；

結(jié)束條件：當(dāng)結(jié)點(diǎn)為NULL時(shí)返回NULL，當(dāng)結(jié)點(diǎn)的值為x時(shí)返回該結(jié)點(diǎn)；

思路：所以當(dāng)其中一個(gè)子樹不為NULL時(shí)就是所求的結(jié)點(diǎn)，如果左子樹不為空則返回左子樹的結(jié)點(diǎn)，否則返回右子樹的結(jié)點(diǎn)，如果左右都為空那也返回右子樹的結(jié)點(diǎn)；

//二叉樹查找值為x的結(jié)點(diǎn)
BTNode* ret = BTreeFine(root, 6);
printf("%d\n", ret->data);

ret = BTreeFine(root, 3);
printf("%d\n", ret->data);

【數(shù)據(jù)結(jié)構(gòu)】二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)（三）,數(shù)據(jù)結(jié)構(gòu)

到這里就結(jié)束了，通過這些題目也充分的認(rèn)識(shí)了二叉樹（遞歸樹），這就是遞歸算法，還是要多畫圖來理解，遞歸基層的知識(shí)就是函數(shù)棧幀的創(chuàng)建與銷毀；

第三階段就到這里了，這階段帶大家了解一下二叉樹（遞歸樹）的遞歸思想；

后面博主會(huì)陸續(xù)更新；

如有不足之處歡迎來補(bǔ)充交流！

完結(jié)。。文章來源地址http://www.zghlxwxcb.cn/news/detail-720957.html

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

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點(diǎn)僅代表作者本人，不代表本站立場。本站僅提供信息存儲(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)文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

博客贊助

微信掃一掃打賞

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

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

二維碼1

領(lǐng)取紅包

二維碼2

領(lǐng)紅包