数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)

简介: 数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)

设想一下二叉树要用什么样的方式来存储,一种是用数组,一种是用链表。

顺序存储结构

用数组,也就是用顺序存储结构,比较合适的就是用于完全二叉树:


按从上至下,从左到右顺序存储n个节点的完全二叉树。 其中的节点父子关系会满足:

  • 非根节点(序号 > 1)的父节点的序号是[i / 2]
  • 节点(序号为i)的左孩子节点的序号是[2i],(若2i <= n,否则没有左孩子)
  • 节点(序号为i)的右孩子节点的序号是[2i+1],(若2i+1 <= n,否则没有右孩子)

一般的二叉树也可以采用这种结构,但是会造成空间浪费。

这样简单的一个二叉树要浪费两个空间,再复杂一些的二叉树浪费的空间就会多得多了。 总结:用数组来表示是可行的,但如果一般的二叉树跟对应的完全二叉树相比,缺的节点很多的话,会造成一定的空间浪费。

链表存储结构

链表存储就是用之前的儿子-兄弟表示法,定义两个指针域就可以表示二叉树了。

typedef int ElementType;
typedef struct TreeNode
{
  ElementType data;
  struct TreeNode* Left;
  struct TreeNode* Right;
}TreeNode;

二叉树的递归遍历

先序递归遍历

遍历过程为:

  1. 访问根节点
  2. 先序遍历其左子树
  3. 先序遍历其右子树

先序遍历的序列为:A B D F E C G H I

中序递归遍历

遍历过程为:

  1. 中序遍历其左子树
  2. 访问根节点
  3. 中序遍历其右子树

可以脑子里过一遍,下面再公布正确的中序遍历的序列。

中序遍历的序列为:D B E F A G H C I

后序递归遍历

遍历过程为:

  1. 后序遍历其左子树
  2. 后序遍历其右子树
  3. 访问根节点

同样先自己写出后序遍历的序列,对照后面的正确序列。

后序遍历的序列为:D E F B H G I C A

在先序、中序和后序的遍历过程中,它们经过节点的路线其实是一样的(路线会在之后的非递归遍历中提到)

都是按这个顺序,只是访问各节点的时机不同。

下面就看看各方式遍历下,访问节点的时机分别是怎样的。

首先要清楚,沿着路线,对每个节点都会访问三次:

所谓先序、中序和后序,就是说:先序是在第一次经过节点时就将节点访问、中序是在第二次经过节点时将节点访问、而后序就是在第三次经过节点时将节点访问。

故有了:

先序遍历路线图

 

中序遍历路线图

后序遍历路线图


end



目录
相关文章
|
25天前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
46 1
|
25天前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
38 0
|
4天前
|
存储
【数据结构】树和二叉树的概念及结构
数据结构——树和二叉树的概念及结构
23 3
【数据结构】树和二叉树的概念及结构
|
12天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
10天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
14 1
|
12天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
12天前
|
机器学习/深度学习 数据采集 监控
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
**神经网络与AI学习概览** - 探讨神经网络设计,包括MLP、RNN、CNN,激活函数如ReLU,以及隐藏层设计,强调网络结构与任务匹配。 - 参数初始化与优化涉及Xavier/He初始化,权重和偏置初始化,优化算法如SGD、Adam,针对不同场景选择。 - 学习率调整与正则化,如动态学习率、L1/L2正则化、早停法和Dropout,以改善训练和泛化。
10 0
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
|
25天前
|
存储 NoSQL 安全
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
34 1
|
17天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
25天前
|
算法 Java
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
15 0

热门文章

最新文章