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

 更新时间:2022年06月24日 09:24:15   作者:配的上了吗  
树是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树形象表示,本篇介绍二叉树的递归与非递归遍历的方法

二叉树的前中后序遍历

所谓二叉树遍历(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语言二叉树内容请搜索得牛网以前的文章或继续浏览下面的相关文章希望大家以后多多支持得牛网!

相关文章

  • C语言实现小型工资管理系统

    C语言实现小型工资管理系统

    这篇文章主要为大家详细介绍了C语言实现小型工资管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2022-02-02
  • 解决Qt设置QTextEdit行高的问题

    解决Qt设置QTextEdit行高的问题

    这篇文章介绍了Qt设置QTextEdit行高的方法,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
    2022-04-04
  • CMake编译中的库文件和头文件链接你了解吗

    CMake编译中的库文件和头文件链接你了解吗

    这篇文章主要为大家详细介绍了CMake编译中的库文件和头文件链接,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下,希望能够给你带来帮助
    2022-02-02
  • Linux 软件看门狗 watchdog使用介绍

    Linux 软件看门狗 watchdog使用介绍

    这篇文章主要介绍了Linux 软件看门狗 watchdog使用介绍,需要的朋友可以参考下
    2016-10-10
  • 浅谈使用C++多级指针存储海量qq号和密码

    浅谈使用C++多级指针存储海量qq号和密码

    这篇文章主要介绍了浅谈使用C++多级指针存储海量qq号和密码,分享了相关实例代码,具有一定借鉴价值,需要的朋友可以参考下
    2018-01-01
  • 关于vs strcpy_s()和strcat_s()用法探究

    关于vs strcpy_s()和strcat_s()用法探究

    这篇文章主要介绍了关于vs strcpy_s()strcat_s()用法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下
    2020-05-05
  • C语言实现查看进程是否存在的方法示例

    C语言实现查看进程是否存在的方法示例

    这篇文章主要介绍了C语言实现查看进程是否存在的方法,涉及C语言针对进程操作的相关实现技巧,需要的朋友可以参考下
    2017-07-07
  • C语言超详细讲解顺序表的各种操作

    C语言超详细讲解顺序表的各种操作

    大家好,今天给大家带来的是顺序表,我觉得顺序表还是有比较难理解的地方的,于是我就把这一块的内容全部整理到了一起,希望能够给刚刚进行学习数据结构的人带来一些帮助,或者是已经学过这块的朋友们带来更深的理解,我们现在就开始吧
    2022-05-05
  • 关于memcpy和memmove的一点重要说明

    关于memcpy和memmove的一点重要说明

    下面小编就为大家带来一篇关于memcpy和memmove的一点重要说明。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
    2016-12-12
  • 基于Opencv实现颜色识别

    基于Opencv实现颜色识别

    这篇文章主要为大家详细介绍了基于Opencv实现颜色识别,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2019-07-07

最新评论