C语言进阶练习二叉树的递归遍历

2022-11-13 10:11:04 遍历递归进阶

二叉树的前中后序遍历

所谓二叉树遍历(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然后往回思考，注意每一个结点都是递归求左子树的深度之后才会递归求右子树的深度。

到此这篇关于C语言进阶练习二叉树的递归遍历的文章就介绍到这了,更多相关C语言二叉树内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！