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

學無先后，達者為師

網站首頁 編程語言 正文

C語言進階練習二叉樹的遞歸遍歷_C 語言

作者：配的上了嗎 ? 更新時間： 2022-08-17 編程語言

二叉樹的前中后序遍歷

所謂二叉樹遍歷(Traversal)是按照某種特定的規則，依次對二叉樹中的節點進行相應的操作，并且每個節點只操作一次。訪問結點所做的操作依賴于具體的應用問題。

遍歷 是二叉樹上最重要的運算之一，也是二叉樹上進行其它運算的基礎。

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

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

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

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

前序遍歷示意圖

// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
	if (root == nullptr)
	{
		cout << "# ";
		return;       // 空的話結束遞歸，輸出#來表示這是一個空結點
	}
	cout << root->data << " ";
	PreOrder(root->left);
	PreOrder(root->right);
}
// 二叉樹中序遍歷
void InOrder(BTNode* root)
{
	if (root == nullptr)
	{
		cout << "# ";
		return;
	}
	InOrder(root->left);
	cout << root->data << " ";
	InOrder(root->right);
}
// 二叉樹后序遍歷
void PostOrder(BTNode* root)
{
	if (root == nullptr)
	{
		cout << "# ";
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	cout << root->data << " ";
}

其實前中后序遍歷的區別，只是在于，對這個結點進行某些操作的時機，是在遍歷其左右子樹之前，之中還是之后。這個操作由具體要解決的問題決定。上方例子中是以打印為例。并且左子樹的遍歷通常都在其右子樹遍歷之前。

就是，把每個非空的根節點看作一個二叉樹，進行同樣的操作就是二叉樹的遞歸遍歷。這些二叉樹的遞歸遍歷之間有一定的順序。遞歸的結束條件是，這個結點為空，為空則不進行下一步遞歸。形如結點3，它的左右子樹為空，在這里結束此處的遞歸，然后返回給上一層。

遍歷二叉樹求二叉樹的結點個數

int count = 0;
void TreeSize1(BTNode* root)
{
	if (root == nullptr)
		return;
	++::count;
	TreeSize1(root->left);
	TreeSize1(root->right);
}
int TreeSize2(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + TreeSize2(root->left) + TreeSize2(root->right);
}

兩種遍歷方式，顯然第二種更好，其實可以直接從遞歸，然后第一次遞歸到底部，開始思考這個計算過程。

如下圖，遞歸至3結點時，3結點返回1+leftsize+rightsize 顯然其左右返回0，所以3結點返回1，2結點的左返回1，然后求2結點的右個數，顯然返回0，2結點返回給1結點2，至此，1結點的左返回2，然后求1結點的右，4結點的左返回1，右返回1，4結點返回給1結點3，所以最終1結點返回1+2+3 = 6。 當然，5和6結點都是求左右加1的這么一個步驟。

遍歷二叉樹求二叉樹的葉子結點個數

int LeafTreeNode(BTNode* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		return LeafTreeNode(root->left) + LeafTreeNode(root->right);
	}
}

也是非常好理解的，不是葉子，不是空，代表其左右子樹至少有一個子樹不為空，則返回其左右子樹的葉子節點個數，典型的分治思想。如下圖，對于1結點，返回其左右子樹的葉子節點個數之和即可，空返回0是防止結點2的右子樹，這樣2結點才能正確地返回給1結點1。

遞歸求二叉樹的第k層的結點個數

int TreeKLevel(BTNode* root, int k)   //求第k層
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

遞歸的結束條件是，當這個結點是空，不管k是不是1，都結束遞歸，另一個情況就是，此結點k是1，且不是空，表示這個結點就是所求的目標節點，無論結點下方是否還有結點都結束遞歸。

求二叉樹中data為x的結點

BTNode* TreeFind(BTNode* root, BTDataType 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。這個流程對于每顆二叉樹都適用。

因為只是求出一個值為x的結點，所以若當前結點是x，或者其左子樹有x，都會結束遞歸。不難理解。

求二叉樹的深度

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

對于1結點，返回1+左右子樹更深的那個子樹，其實完全可以遞歸至3然后往回思考，注意每一個結點都是遞歸求左子樹的深度之后才會遞歸求右子樹的深度。

原文鏈接：https://blog.csdn.net/i777777777777777/article/details/125042819

欄目分類
最近更新