日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C++鏈式二叉樹深入分析_C 語言

作者：沙漠下的胡楊 ? 更新時間： 2022-08-01 編程語言

之前我們的重點學習二叉樹都是完全二叉樹，接下來我們來說下普通二叉樹，普通的二叉樹如果我們使用數組存儲，那么會浪費相當多的空間的，所以我們選擇鏈表存儲，我們先再來復習下二叉樹的結構吧。

二叉樹的結構和概念

二叉樹概念是：

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 = %d\n", 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
}

原文鏈接：https://blog.csdn.net/m0_64770095/article/details/125128447

欄目分類
最近更新