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

2022-06-07 14:00:05

二元樹的結構和概念

二元樹概念是：

1. 空樹

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

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

我們就手動建立一個二元樹，用於學習二元樹的存取吧，結構如下：

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;
}

我們可以根據上述的結構進行二元樹的後續操作啦。

二元樹的操作

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

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

按照規則，二元樹的遍歷有：前序/中序/後序的遞迴結構遍歷：

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

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

3. 後序遍歷(Postorder Traversal)——存取根結點的操作發生在遍歷其左右子樹之後。

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

前序遍歷

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

我們自己建立的二元樹的圖如下：

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);//最後存取 根
}

二元樹的節點個數

我們接下來要求出二元樹的節點個數。

1. 我們使用計數器進行操作。缺點：每次使用前全域性變數要置為0，比較麻煩。

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

我們來一個個實現吧。

思路一：(不常用)

我們定義一個全域性變數size，使用前序遍歷，然後把其中列印部分去掉換成 ++size即可，我們要在每次使用該函數時，手動把我們定義的全域性變數置為0。

int size；
void TreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	size++;//計數器
	TreeSize(root->left);//存取左子樹
	TreeSize(root->right);//存取右子樹
}
int main()
{
	BTNode* root = CreatBinaryTree();
	size = 0;
	TreeSize(root);
	printf("TreeSize = %dn", size);
	return 0;
}

思路二：

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

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

求二元樹葉子結點個數

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

int TreeLeafSize(BTNode* root)//求葉子節點
{
	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的結點

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

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

到此這篇關於C++鏈式二元樹深入分析的文章就介紹到這了,更多相關C++鏈式二元樹內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！