C++鏈?zhǔn)蕉鏄?shù)深入分析

更新時(shí)間：2022年06月07日 10:28:19 作者：沙漠下的胡楊

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來(lái)表示一棵二叉樹(shù)，即用鏈來(lái)指示元素的邏輯關(guān)系。通常的方法是鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，數(shù)據(jù)域和左右指針域，左右指針?lè)謩e用來(lái)給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址

之前我們的重點(diǎn)學(xué)習(xí)二叉樹(shù)都是完全二叉樹(shù)，接下來(lái)我們來(lái)說(shuō)下普通二叉樹(shù)，普通的二叉樹(shù)如果我們使用數(shù)組存儲(chǔ)，那么會(huì)浪費(fèi)相當(dāng)多的空間的，所以我們選擇鏈表存儲(chǔ)，我們先再來(lái)復(fù)習(xí)下二叉樹(shù)的結(jié)構(gòu)吧。

二叉樹(shù)的結(jié)構(gòu)和概念

二叉樹(shù)概念是：

1. 空樹(shù)

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

從概念中可以看出，二叉樹(shù)定義是遞歸式的。

我們就手動(dòng)創(chuàng)建一個(gè)二叉樹(shù)，用于學(xué)習(xí)二叉樹(shù)的訪問(wèn)吧，結(jié)構(gòu)如下：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType* x)
{
	BTNode* NewNode = (BTNode*)malloc(sizeof(BTNode));
	assert(NewNode);
	NewNode->data = x;
	NewNode->left = NULL;
	NewNode->right = NULL;
	return NewNode;
}
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;
}

我們可以根據(jù)上述的結(jié)構(gòu)進(jìn)行二叉樹(shù)的后續(xù)操作啦。

二叉樹(shù)的操作

學(xué)習(xí)二叉樹(shù)結(jié)構(gòu)，最簡(jiǎn)單的方式就是遍歷。

所謂二叉樹(shù)遍歷(Traversal)是按照某種特定的規(guī)則，依次對(duì)二叉樹(shù)中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問(wèn)結(jié)點(diǎn)所做的操作依賴(lài)于具體的應(yīng)用問(wèn)題。遍歷是二叉樹(shù)上最重要的運(yùn)算之一，也是二叉樹(shù)上進(jìn)行其它運(yùn)算的基礎(chǔ)。

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

1. 前序遍歷(Preorder Traversal )——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前。

2. 中序遍歷(Inorder Traversal)——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之中（間）。

3. 后序遍歷(Postorder Traversal)——訪問(wèn)根結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后。

由于被訪問(wèn)的結(jié)點(diǎn)必是某子樹(shù)的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹(shù)和根的右子樹(shù)。NLR、LNR和LRN分別又稱(chēng)為先根遍歷、中根遍歷和后根遍歷。

前序遍歷

我們都知道二叉樹(shù)我們可以分為根左子樹(shù) 右子樹(shù)，這三個(gè)部分，我們先序遍歷，就是先訪問(wèn)二叉樹(shù)的根，在訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)，如果訪問(wèn)到空樹(shù)我們使用 ‘*’ 代替，我們用代碼控制下：

我們自己創(chuàng)建的二叉樹(shù)的圖如下：

void Preorder(BTNode* root)
{
	if (root == NULL)
	{
		printf("* ");//空樹(shù)打印 * 
		return ;
	}
	printf("%d ", root->data);//先訪問(wèn) 根
	Preorder(root->left);//再訪問(wèn)左子樹(shù)
	Preorder(root->right);//最后訪問(wèn)右子樹(shù)
}

中序遍歷和后序遍歷

這兩個(gè)遍歷和上面對(duì)比就是把訪問(wèn)根的順序變了，不在詳細(xì)說(shuō)了。

void Inorder(BTNode* root)//中序遍歷
{
	if (root == NULL)
	{
		printf("* ");//空樹(shù)打印 * 
		return;
	}
	Preorder(root->left);//先訪問(wèn)左子樹(shù)
	printf("%d ", root->data);//再訪問(wèn) 根
	Preorder(root->right);//最后訪問(wèn)右子樹(shù)
}
void Postorder(BTNode* root)//后序遍歷
{
	if (root == NULL)
	{
		printf("* ");//空樹(shù)打印 * 
		return;
	}
	Preorder(root->left);//先訪問(wèn)左子樹(shù)
	Preorder(root->right);//再訪問(wèn)右子樹(shù)
	printf("%d ", root->data);//最后訪問(wèn) 根
}

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

我們接下來(lái)要求出二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)。

1. 我們使用計(jì)數(shù)器進(jìn)行操作。缺點(diǎn)：每次使用前全局變量要置為0，比較麻煩。

2. 我們使用分治的思路，轉(zhuǎn)化為這個(gè)根+左子樹(shù)的節(jié)點(diǎn)+右子樹(shù)的節(jié)點(diǎn)

我們來(lái)一個(gè)個(gè)實(shí)現(xiàn)吧。

思路一：(不常用)

我們定義一個(gè)全局變量size，使用前序遍歷，然后把其中打印部分去掉換成 ++size即可，我們要在每次使用該函數(shù)時(shí)，手動(dòng)把我們定義的全局變量置為0。

int size；
void TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size++;//計(jì)數(shù)器
	TreeSize(root->left);//訪問(wèn)左子樹(shù)
	TreeSize(root->right);//訪問(wèn)右子樹(shù)
}
int main()
{
	BTNode* root = CreatBinaryTree();
	size = 0;
	TreeSize(root);
	printf("TreeSize = %d\n", size);
	return 0;
}

思路二：

我們可以使用分治的思想轉(zhuǎn)化為求該節(jié)點(diǎn)的左子樹(shù)+右子數(shù)+根，如果為NULL，就返回0.

int TreeSize2(BTNode* root)
{
	if (root == NULL)//為NULL返回0
	{
		return 0;
	}
	return TreeSize2(root->left) + TreeSize2(root->right) + 1;
}

求二叉樹(shù)葉子結(jié)點(diǎn)個(gè)數(shù)

要求葉子結(jié)點(diǎn)，就是左右的子樹(shù)都是空樹(shù)，才是一個(gè)葉子節(jié)點(diǎn)，我們可以轉(zhuǎn)化為求左子樹(shù)的葉子+右子樹(shù)的葉子。

int TreeLeafSize(BTNode* root)//求葉子節(jié)點(diǎn)
{
	if (root == NULL)//空樹(shù)返回0
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)//左子樹(shù)為空并且右子樹(shù)為空返回1
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

求二叉樹(shù)的深度

我們還是采用分治的思想，我們先求出左子樹(shù)的高度，再求出右子樹(shù)的高度，進(jìn)行對(duì)比，比較時(shí)不要忘了自身也是有高度的，最后把二叉樹(shù)拆到最小的空樹(shù)時(shí)返回0就好啦。

int TreeDepth(BTNode* root)
{
	if (root == NULL)//空樹(shù)返回0
	{
		return 0;
	}
	int Leftdepth = TreeDepth(root->left);//求出左邊高度
	int Rightdepth = TreeDepth(root->right);//求出右邊高度
	return Leftdepth > Rightdepth ? Leftdepth + 1 : Rightdepth + 1;//返回時(shí)加上自身返回
}

在二叉樹(shù)查找為X的結(jié)點(diǎn)

我們?cè)诙鏄?shù)中查找結(jié)點(diǎn)，可以使用前序遍歷，找到該節(jié)點(diǎn)時(shí)我們直接返回不用在查找。整體上采用前序遍歷，我們需要注意，在遍歷左右子樹(shù)時(shí)，我們應(yīng)該保存節(jié)點(diǎn)的值方便返回。

BTNode* TreeFind(BTNode* root, BTDataType x)//查找二叉樹(shù)中值為x的節(jié)點(diǎn)
{
	if (root == NULL)//為空返回空
	{
		return NULL;
	}
	if (root->data == x)//相等就返回節(jié)點(diǎn)
	{
		return root;
	}
	BTNode* RetLeft = TreeFind(root->left, x);//保存左節(jié)點(diǎn)值，方便直接返回
	if (RetLeft)
	{
		return RetLeft;
	}
	BTNode* RetRight = TreeFind(root->right, x);//保存右節(jié)點(diǎn)值，方便直接返回
	if (RetRight)
	{
		return RetRight;
	}
	return NULL;//都找不到返回NULL
}