欢迎访问欧博网址!

首页快讯正文

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历

admin2020-05-0819

前文传送门:

「一本正经的聊数据结构(1):时间复杂度」

「一本正经的聊数据结构(2):数组与向量」

「一本正经的聊数据结构(3):栈和行列」

「一本正经的聊数据结构(4):树」

存储结构

前面的内容我们先容了树和二叉树的一些基础观点,树是数据结构中的重中之重,而二叉树又是树结构中的重点。

一直以来,包罗我上学的年月,对树和二叉树的掌握都是模棱两可,希望能通过这篇文章可以给列位讲清楚这些疑难点。

二叉树的存储结构分为两种,一种是顺序存储结构,另一种是链式存储结构

顺序存储结构

顺序存储结构就是使用一维数组存储二叉树中的节点,而且节点的存储位置,就是数组的下标索引。

存储在一维数组中的样子如下:

这个示例是一个 完全二叉树 的示例, 完全二叉树 所对应的顺序存储恰好填满整个数组,然则若是二叉树不是 完全二叉树 的时刻,接纳顺序存储又是怎样的呢?

下图中浅色结点示意结点不存在:

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历 第1张

存储在一维数组中的样子如下:

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历 第2张

其中, 示意数组中此位置没有存储结点。可以看到,使用顺序存储已经造成了空间虚耗的情形。

若是是极端的右斜二叉树,顺序存储情形会若何呢?

如下:

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历 第3张

存储在一维数组中的样子如下:

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历 第4张

可以看到,在顺序存储结构下,极端的右斜二叉树存储造成了存储空间的极大的虚耗。

以是顺序存储方式一样平常适合完全二叉树。

链式存储结构

顺序存储结构有些无法知足二叉树的存储,那么我们思量使用链式存储结构。

二叉树每个节点最多会有两个孩子,因此,可以将结点数据结构界说为一个数据和两个指针域。如下:

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历 第5张

那么适才我们的谁人完全二叉树的存储结构就可以这么展现:

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历 第6张

遍历

二叉树的 遍历 是指从二叉树的根结点出发,根据某种顺序依次接见二叉树中的所有结点,使得每个结点被接见一次,且仅被接见一次。

二叉树的遍历依据接见顺序可以分为四种方式:

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 条理遍历

前序遍历

简朴来讲, 前序遍历 就是由根节点最先,当第一次到达结点时就输出结点数据,根据先向左在向右的偏向接见。

照样用这个完全二叉树举例子:

淮安百姓网:一本正经的聊数据结构(5):二叉树的存储结构与遍历 第7张

当他举行前序遍历的时刻,接见顺序如下:

从根结点出发,则第一次到达结点 A ,故输出 A ;

继续向左接见,第一次接见结点 B ,故输出 B ;

根据同样规则,输出 D ,输出 H ;

当到达叶子结点H,返回到 D ,此时已经是第二次到达 D ,故不在输出 D ,进而向 D 右子树接见, D 右子树不为空,则接见至 I ,第一次到达 I ,则输出 I ;

I 为叶子结点,则返回到 D , D 左右子树已经接见完毕,则返回到 B ,进而到 B 右子树,第一次到达 E ,故输出 E ;

向E左子树,故输出 J ;

根据同样的接见规则,继续输出 C 、 F 、 G 。

以是,这个完全二叉树的前序遍历效果为: ABDHIEJCFG

中序遍历

中序遍历 就是从二叉树的根结点出发,当第二次到达结点时就输出结点数据,根据先向左在向右的偏向接见。

照样上面的完全二叉树,接见顺序如下:

从根结点出发,则第一次到达结点 A ,不输出 A ,继续向左接见,第一次接见结点 B ,不输出 B ;继续到达 D , H ;

到达 H , H 左子树为空,则返回到 H ,此时第二次接见 H ,故输出 H ;

H 右子树为空,则返回至 D ,此时第二次到达 D ,故输出 D ;

由 D 返回至 B ,第二次到达 B ,故输出 B ;

根据同样规则继续接见,输出 J 、 E 、 A 、 F 、 C 、 G ;

以是,中序遍历的效果为: HDIBJEAFCG

后序遍历

后序遍历 就是从二叉树的根结点出发,当第三次到达结点时就输出结点数据,根据先向左在向右的偏向接见。

后序遍历 的接见顺序如下:

从根结点出发,则第一次到达结点 A ,不输出 A ,继续向左接见,第一次接见结点 B ,不输出 B ;继续到达 D , H ;

到达 H , H 左子树为空,则返回到 H ,此时第二次接见 H ,不输出 H ;

H 右子树为空,则返回至 H ,此时第三次到达 H ,故输出 H ;

由 H 返回至 D ,第二次到达 D ,不输出 D ;

继续接见至 I , I 左右子树均为空,故第三次接见 I 时,输出 I ;

返回至 D ,此时第三次到达 D ,故输出 D ;

根据同样规则继续接见,输出 J 、 E 、 B 、 F 、 G 、 C , A ;

以是,后序遍历的效果为: HIDJEBFGCA

条理遍历

条理遍历 就是根据树的条理自上而下的遍历二叉树。

条理遍历的接见顺序如下:

从根节点出发,第一个到达节点 A ,直接输出 A ;

继续向左接见,到达节点 B ,输出节点 B ,继续接见节点的右节点 C ,输出节点 C ,此时,第二层接见竣事,继续接见第三层;

接见节点 B 的左节点 D ,输出 D ,继续接见节点 B 的右节点 E ,输出节点 E ;

剩下依次接见节点 F 、 G 、 H 、 I 、 J 。

以是条理遍历的效果为: ABCDEFGHIJ

小结

本文先容了二叉树的存储结构以及四种遍历方式,列位看完了应该对二叉树有一个开端的认知,若是不涉及一些变种的二叉树,仅二叉树的基础内容而言,照样比较简朴的,希望列位同砚能够自己思索下,在大脑中能确立出一个二叉树的模子,利便后面的学习。

参考

https://www.jianshu.com/p/bf73c8d50dc2

,

申博Sunbet

申博Sunbet www.sunbet.xyz是Sunbet指定的Sunbet官网,Sunbet提供Sunbet(Sunbet)、Sunbet、申博代理合作等业务。

转载声明:本站发布文章及版权归原作者所有,转载本站文章请注明文章来源自欧博网址!

本文链接:http://www.cx11yx.cn/post/985.html