【数据结构】二叉树（遍历，递归）

发布时间：2024年01月18日

?🌈个人主页：秦jh__https://blog.csdn.net/qinjh_?spm=1010.2135.3001.5343
🔥?系列专栏：《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm=1001.2014.3001.5482

???

???前言

????💬 hello! 各位铁子们大家好哇。

? ? ? ? ? ? ?今日更新了树的遍历，递归的相关内容
????🎉 欢迎大家关注🔍点赞👍收藏??留言📝

二叉树遍历规则

前序遍历

?

注意：N代表空

分析：根据前序遍历的规则（根左右），先访问根1，然后左子树2，2的左子树3，3的左子树是N，右子树也是N，然后返回到2的右子树N，然后返回到1的右子树4，接着是4的左子树5，5的左右子树都是N，然后返回到4的右子树6，6的左右子树都是N。

中序遍历

分析：根据规则（左根右），1的左子树2，2的左子树3，3的左子树N，起始即为N，接着是根3，接着是3的右子树N，返回到根2，然后是2的右子树N，返回到根1，接着是1的右子树，以此类推。

?后序遍历

分析：过程变为左右根，其实质与前面两种一样。

递归结构遍历

上图是要遍历的树的模型。?

前序

假设树已构建好，下图是前序遍历的函数，执行后即可得到前序遍历的结果。

?下图是递归的流程图：

分析：开始先打印根1，然后递归调用根2，以此类推到3的左子树N。此时左子树遍历完，返回到3的右子树，每次调用完就返回到上一层的函数中。

上图是递归调用占用的大致空间，每次调用完函数，返回到上一层，上一层接着调用，就会重复利用之前销毁的空间，如果空间不足，能用多少是多少。因此，递归的空间复杂度是看递归的深度。?

中序

上图是中序遍历的函数，递归过程参考前序遍历过程。

后序遍历大致过程也同上，这里就不再写出。

?求节点个数

递归过程图如下：

分析：如果根结点为空，则返回0。此递归过程会先找出左子树的节点个数，当遇到空节点时就返回0，然后加上根结点自身数量1，返回到上一层，以此类推。

求叶子节点个数

?参考前面的递归过程理解。

?求树的高度

求第k层节点个数

分析：k-1目的是当到达第k层后，直接返回1到上一层?

文章来源:https://blog.csdn.net/qinjh_/article/details/135647509
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！