前言

??個(gè)人主頁：@小沈熬夜禿頭中????
??小編介紹：歡迎來到我的亂七八糟小星球??
??專欄：數(shù)據(jù)結(jié)構(gòu)
??本章內(nèi)容：手撕鏈?zhǔn)蕉鏄?br> 送給各位??：我從沒覺得孤獨(dú) 說的浪漫點(diǎn) 我完全自由
記得 評論?? +點(diǎn)贊?? +收藏?? +關(guān)注??哦~

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

??一、二叉樹鏈?zhǔn)浇Y(jié)構(gòu)的實(shí)現(xiàn)

??1.1 前置說明

在學(xué)習(xí)二叉樹的基本操作前，需先要?jiǎng)?chuàng)建一棵二叉樹，然后才能學(xué)習(xí)其相關(guān)的基本操作。由于現(xiàn)在大家對二叉樹結(jié)構(gòu)掌握還不夠深入，為了降低大家學(xué)習(xí)成本，此處手動(dòng)快速創(chuàng)建一棵簡單的二叉樹，快速進(jìn)入二叉樹操作學(xué)習(xí)，等二叉樹結(jié)構(gòu)了解的差不多時(shí)，我們反過頭再來研究二叉樹真正的創(chuàng)建方式。

??快速創(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 NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	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;
}

注意：上述代碼并不是創(chuàng)建二叉樹的方式，真正創(chuàng)建二叉樹方式后序詳解重點(diǎn)講解。
再看二叉樹基本操作前，再回顧下二叉樹的概念:

二叉樹是：

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

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

??1.2 二叉樹的遍歷的時(shí)間、空間復(fù)雜度

時(shí)間復(fù)雜度：O(N)
空間復(fù)雜度：O(h)—h是高度范圍是【logN,N】

??1.3 二叉樹的遍歷

??1.3.1 前序、中序以及后序遍歷：

學(xué)習(xí)二叉樹結(jié)構(gòu)，最簡單的方式就是遍歷。所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。 遍歷是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。
由于被訪問的結(jié)點(diǎn)必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

按照規(guī)則，二叉樹的遍歷有：前序/中序/后序的遞歸結(jié)構(gòu)遍歷：

??1.3.2 前序遍歷:

(Preorder Traversal 亦稱先序遍歷)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前(根 -> 左子樹 -> 右子樹)。

??代碼：

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

??流程圖：

結(jié)果：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

??1.3.3 后序遍歷

(Postorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后(左子樹 -> 右子樹 -> 根)。

??代碼：

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

??流程圖：

只畫了部分，具體和第一個(gè)前序一樣的流程只不過注意到底是先走哪里
結(jié)果：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

??1.3.4 中序遍歷：就不畫流程圖了具體即上有興趣可以自己畫一下

(Inorder Traversal)——訪問根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中間(左子樹 -> 根 -> 右子樹)。
結(jié)果：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

??代碼：

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

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

??1.4.1 錯(cuò)誤示范一(代碼)：

??代碼：

void BTreeSzie(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	int size = 0;
	size++;
	BTreeSzie(root->left );
	BTreeSzie(root->right );
}

??流程圖：

??1.4.2 錯(cuò)誤示范二(代碼)：

??代碼：

經(jīng)過錯(cuò)誤示范一想要改進(jìn)就可能想到static—C語言關(guān)鍵字
雖然解決了size每次調(diào)用重定義的錯(cuò)誤但是我們并不能拿到size,因?yàn)閟ize是局部變量，為了解決這個(gè)問題，就可能想到返回值的做法，但是返回值會(huì)導(dǎo)致調(diào)用多次這個(gè)函數(shù)時(shí)，static一直向后面增加而外面也不能局部變量置零

int BTreeSzie(BTNode* root)
{
	static int size = 0;
	printf("%p,%d\n", &size,size);
	if (root == NULL)
	{
		return size;
	}
	size++;
	BTreeSzie(root->left );
	BTreeSzie(root->right );
	return size;
}

??流程圖:

通過打印size的地址和值可以得知static解決了錯(cuò)誤示范一中的問題

但是出現(xiàn)多次調(diào)用還是會(huì)出現(xiàn)累加現(xiàn)象同時(shí)不能在下一次調(diào)用這個(gè)函數(shù)時(shí)將size置零，因?yàn)樗且粋€(gè)局部變量。

??1.4.3 正確代碼第一種(方式)：定義全局變量

??代碼：

int size = 0;
void BTreeSzie(BTNode* root)
{
	if (root == NULL)
	{
		return size;
	}
	size++;
	BTreeSzie(root->left);
	BTreeSzie(root->right);
	return size;
}

??流程圖:

多次調(diào)用可以在第二次調(diào)用時(shí)將第一次數(shù)據(jù)置零

??1.4.4 正確代碼第二種(方式)：

??代碼：

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

??流程圖:

??二、全部代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>

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 NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTNode* CreatBinaryTree()
{
	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;
}


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

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

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

//二叉樹節(jié)點(diǎn)個(gè)數(shù) --- 遍歷計(jì)數(shù)
//int size = 0;
//void BTreeSzie(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left);
//	BTreeSzie(root->right);
//	return size;
//}

//int BTreeSzie(BTNode* root)
//{
//	static int size = 0;
//	//printf("%p,%d\n", &size,size);
//	if (root == NULL)
//	{
//		return size;
//	}
//	size++;
//	BTreeSzie(root->left );
//	BTreeSzie(root->right );
//	return size;
//}


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


int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	//printf("BTreeSize:%d\n", BTreeSzie(root));
	/*BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);
	size = 0;
	BTreeSzie(root);
	printf("BTreeSize:%d\n", size);*/

	printf("BTreeSize:%d\n", BTreeSzie(root));
	return 0;
}

??總結(jié)

??Ending,今天的鏈?zhǔn)蕉鏄?/mark>的內(nèi)容就到此結(jié)束啦~，如果后續(xù)想了解更多，就請關(guān)注我吧，一鍵三連哦 ~文章來源地址http://www.zghlxwxcb.cn/news/detail-466127.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】---幾分鐘簡單幾步學(xué)會(huì)手撕鏈?zhǔn)蕉鏄?上)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！