二叉樹的前中后序遍歷

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

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

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

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

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

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

前序遍歷示意圖

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

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

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

遍歷二叉樹求二叉樹的結(jié)點個數(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);
}

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

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

遍歷二叉樹求二叉樹的葉子結(jié)點個數(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);
	}
}

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

遞歸求二叉樹的第k層的結(jié)點個數(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é)束條件是，當這個結(jié)點是空，不管k是不是1，都結(jié)束遞歸，另一個情況就是，此結(jié)點k是1，且不是空，表示這個結(jié)點就是所求的目標節(jié)點，無論結(jié)點下方是否還有結(jié)點都結(jié)束遞歸。

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

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

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

因為只是求出一個值為x的結(jié)點，所以若當前結(jié)點是x，或者其左子樹有x，都會結(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;
}

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

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

最新評論