C++鏈式二叉樹深入分析

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

二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常的方法是鏈表中每個結點由三個域組成，數(shù)據(jù)域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址

二叉樹的結構和概念

二叉樹概念是：

1. 空樹

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

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

我們就手動創(chuàng)建一個二叉樹，用于學習二叉樹的訪問吧，結構如下：

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ù)上述的結構進行二叉樹的后續(xù)操作啦。

二叉樹的操作

學習二叉樹結構，最簡單的方式就是遍歷。

所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對二叉樹中的節(jié)點進行相應的操作，并且每個節(jié)點只操作一次。訪問結點所做的操作依賴于具體的應用問題。遍歷是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。

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

1. 前序遍歷(Preorder Traversal )——訪問根結點的操作發(fā)生在遍歷其左右子樹之前。

2. 中序遍歷(Inorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之中（間）。

3. 后序遍歷(Postorder Traversal)——訪問根結點的操作發(fā)生在遍歷其左右子樹之后。

由于被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

前序遍歷

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

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

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

中序遍歷和后序遍歷

這兩個遍歷和上面對比就是把訪問根的順序變了，不在詳細說了。

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

二叉樹的節(jié)點個數(shù)

我們接下來要求出二叉樹的節(jié)點個數(shù)。

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

2. 我們使用分治的思路，轉化為這個根+左子樹的節(jié)點+右子樹的節(jié)點

我們來一個個實現(xiàn)吧。

思路一：(不常用)

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

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

思路二：

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

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

求二叉樹葉子結點個數(shù)

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

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

求二叉樹的深度

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

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

在二叉樹查找為X的結點

我們在二叉樹中查找結點，可以使用前序遍歷，找到該節(jié)點時我們直接返回不用在查找。整體上采用前序遍歷，我們需要注意，在遍歷左右子樹時，我們應該保存節(jié)點的值方便返回。

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