二叉樹的前中后序遍歷

所謂二叉樹遍歷(Traversal)是按照某種特定的規(guī)則，依次對(duì)二叉樹中的節(jié)點(diǎn)進(jìn)行相應(yīng)的操作，并且每個(gè)節(jié)點(diǎn)只操作一次。訪問結(jié)點(diǎn)所做的操作依賴于具體的應(yīng)用問題。

遍歷 是二叉樹上最重要的運(yùn)算之一，也是二叉樹上進(jìn)行其它運(yùn)算的基礎(chǔ)。

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

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

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

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

前序遍歷示意圖

// 二叉樹前序遍歷
void PreOrder(BTNode* root)
{
	if (root == nullptr)
	{
		cout << "# ";
		return;       // 空的話結(jié)束遞歸，輸出#來表示這是一個(gè)空結(jié)點(diǎn)
	}
	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 << " ";
}

其實(shí)前中后序遍歷的區(qū)別，只是在于，對(duì)這個(gè)結(jié)點(diǎn)進(jìn)行某些操作的時(shí)機(jī)，是在遍歷其左右子樹之前，之中還是之后。這個(gè)操作由具體要解決的問題決定。上方例子中是以打印為例。并且左子樹的遍歷通常都在其右子樹遍歷之前。

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

遍歷二叉樹求二叉樹的結(jié)點(diǎn)個(gè)數(shù)

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

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

如下圖，遞歸至3結(jié)點(diǎn)時(shí)，3結(jié)點(diǎn)返回1+leftsize+rightsize 顯然其左右返回0，所以3結(jié)點(diǎn)返回1，2結(jié)點(diǎn)的左返回1，然后求2結(jié)點(diǎn)的右個(gè)數(shù)，顯然返回0，2結(jié)點(diǎn)返回給1結(jié)點(diǎn)2，至此，1結(jié)點(diǎn)的左返回2，然后求1結(jié)點(diǎn)的右，4結(jié)點(diǎn)的左返回1，右返回1，4結(jié)點(diǎn)返回給1結(jié)點(diǎn)3，所以最終1結(jié)點(diǎn)返回1+2+3 = 6。 當(dāng)然，5和6結(jié)點(diǎn)都是求左右加1的這么一個(gè)步驟。

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

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

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

遞歸求二叉樹的第k層的結(jié)點(diǎn)個(gè)數(shù)

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

遞歸的結(jié)束條件是，當(dāng)這個(gè)結(jié)點(diǎn)是空，不管k是不是1，都結(jié)束遞歸，另一個(gè)情況就是，此結(jié)點(diǎn)k是1，且不是空，表示這個(gè)結(jié)點(diǎn)就是所求的目標(biāo)節(jié)點(diǎn)，無論結(jié)點(diǎn)下方是否還有結(jié)點(diǎn)都結(jié)束遞歸。

求二叉樹中data為x的結(jié)點(diǎn)

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

典型的前序遍歷，每到一個(gè)根節(jié)點(diǎn)，先判斷是否為空，非空則判斷是否為目標(biāo)結(jié)點(diǎn)，不是的話，就先去其左子樹找，左子樹沒有則去右子樹找，右子樹沒有則表示這顆二叉樹中無目標(biāo)節(jié)點(diǎn)，返回NULL。這個(gè)流程對(duì)于每顆二叉樹都適用。

因?yàn)橹皇乔蟪鲆粋€(gè)值為x的結(jié)點(diǎn)，所以若當(dāng)前結(jié)點(diǎn)是x，或者其左子樹有x，都會(huì)結(jié)束遞歸。不難理解。

求二叉樹的深度

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

對(duì)于1結(jié)點(diǎn)，返回1+左右子樹更深的那個(gè)子樹，其實(shí)完全可以遞歸至3然后往回思考，注意每一個(gè)結(jié)點(diǎn)都是遞歸求左子樹的深度之后才會(huì)遞歸求右子樹的深度。

到此這篇關(guān)于C語言進(jìn)階練習(xí)二叉樹的遞歸遍歷的文章就介紹到這了,更多相關(guān)C語言二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論