0

Image Description

荆文征

Zhidu Inc.


你好,再见

大话数据结构 - 树 (6)

  • 小酒馆老板
  • /
  • 2018/1/5 10:19:0


H2

树的定义

之前我么你只在谈的是一对一的线性结构,可现实中,还有很多一对多的情况徐耀处理,所以我们需要研究这种一对多的数据结构—–“树”,考虑他的各种特性,来解决我们在编程中遇到的相关问题。

树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:(1)有且仅有一个特定的称为根(Root)的结点;(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,….Tm,其中每个节点本身又是一棵树,并且成为根的子树(SubTree)



Image Description
树示意图


树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义之中还用到了树的概念,这是一种比较新的定义方法。图6-2-2的子树T1和子树T2就是根结点A的子树。当然,D,G,H,I组成的树又是B为结点的子树,E,J组成的树是C为结点的子树。


Image Description
子树示意图


对于树的定义还需要强调两点:

  1. n>0 时根结点时唯一的,不可能存在多个跟结点,别和现实中的大树混在一起,现实中的树有很多的根须,那是真实的树,数据结构中的树只能有一个根结点
  2. m>0 时,子树的个数没有限制,但他们一定是互不相欠的。像图6-2-3中的两个结构就不符合树的定义,因为他们都有相交的子树。


    Image Description
    错误的树结构


H3

结点分类

树的结点包含一个数据元素及若干指向其子树的分之。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(Leaf)或终端结点;度不为0 的结点称为非终端结点或分之结点。除跟结点之外,分支结点也称为内部结点。树的度是树的个结点的度的最大值。 如图6-2-4所示,因为这棵树结点的度最大值D的度为3,所以树的度也为3。


Image Description
结点分类树度示意图


H3

结点间关系

结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent)。 嗯,为什么不是父或母,叫双亲呢?呵呵,对于结点来说,其父母同题,唯一的一个,所以只能称他为双亲了。同一个双亲的孩子之间称为(Slibling)。结点的祖先是从到该结点所经分枝上的所有结点。 所以对于H来说,D,B,A都是它的祖先。反之,以某结点为根的子树中的热一结点都称为该结点的子孙。


Image Description
结点关系示意图


H3

树的其他相关概念

结点的层次(Level)从根开始定义起,根为第一层,根的孩子为第二层。 所某结点在第l层,则其子树的根就在l+1层。其双亲在同一层的结点互为堂兄弟。 显然图6-2-6中的D,E,F是堂兄弟,而G,H,I,J也是。树中结点最大层次成为树的深度(Depth)或高度, 当前树的深度为4。


Image Description
树的深度高度示意图


如果将树中结点的各子树看成从左至右是有次序的,不能互换的,称为该树为有序树,否则称为无序树。
森林(Forest)是m(m>=0)棵互不相交的树的集合。对树中每个节点而言,其子树的集合即为森林。对于图6-2-1中的树而言,图6-2-2中的两颗子树其实就可以理解为森林。
对比线性表与树的结构,他们有很大的不同。
| 线性结构 | 树结构 |
| ————- |:————-:|
| 第一个元素:无前驱 | 根结点:无双亲,唯一 |
| 最后一个元素:无后继 | 叶结点:无孩子,可以多个 |
| 中间元素:一个前驱一个后继 | 中间结构:一个双亲多个孩子 |


H2

树的存储结构

说到存储结构,就会想到我们前面章节讲过的顺序存储和链式存储两种结构。
先来看看顺序存储结构,用一段地址连续的存储依次存储线性表的数据元素。这对于线性表来说自然是正常的,对于树这种一对多的结构呢?
树中某个节点的孩子可以是多个的,这就意味着,无论按照和中环许将书中所有节点存出道数组中,结点的存储位置都无法直接反映逻辑关系,你想想看,数据元素挨个的存储,谁是谁的双亲,谁是谁的孩子呢?简单的顺序存储结构是不能满足树的实现要求的。
不过充分利用顺序存储和链式存储结构的特点,完全可以实现对树的存储结构的表示。我们这里就要介绍三种不同的表示法:双亲表示法,孩子表示法,孩子兄弟表示法


H3

双亲表示法

我们人可能因为种种原因,没有孩子,但无论是谁都不可能是从石头里蹦出来的,孙武哦那个显然不能算是人,所以人是一定要有父母的。树这种结构也不例外,除了跟结点外,其余每个结点,他不一定有孩子,但是一定有且仅有一个双亲。
我们假设以一组连续空间存储树的结点,同时 在每个结点中,附设一个指示器指示器双亲结点到链表中的位置。 也就是说,每个结点除了知道自己是谁以外,还知道他的双亲在哪里。他的结点结构为表6-4-1所示。


Image Description
双亲表示法第一示意图


其中datas是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标。
有了这样的结构定义,我们就可以来实现双亲表示法了。由于跟结点是没有双亲的,所以我们约定跟结点的位置域s设置为-1,这也就意味着,我们所有的结点都存有它双亲的位置。


Image Description
双亲表示法示意图


这样的存储结构,我们可以根据结点的parent指针很容易的找到他的双亲结点,所有的时间复杂度为O(1),直到parent为-1时,表示找到了数结点的根。可如果我们要知道结点的孩子是什么,对不起,请遍历整个结构才行。
这真是麻烦,能不能改进一下呢?
当然可以。我们增加一个结点最左边孩子的域,不妨叫他长子域,这样就可以很容易得到结点的孩子。如果没有孩子的结点,这个长子域就设置为-1.


Image Description
长子域示意图


对于有0个或一个孩子结点来说,这样的结构是解决了要找结点孩子的问题了。甚至是有两个孩子,直到长子是谁,另一个当然就是次子了。
另一个问题场景,我们很关注个兄弟之间的关系,双亲表示法无法体现这样的关系,那我们怎么办?嗯,可以增加一个右兄弟域来体现兄弟关系,也就是说,每个节点如果他存在右兄弟,则记录下右兄弟的下标。同样的,如果右兄弟不存在,则复制为-1.


Image Description
右兄弟示意图


但如果结点的孩子很多,超过了2个。我们有关注结点的双亲,有关注结点的孩子,还关注结点的兄弟,而且对时间遍历要求还比较高,那么我们还可以把此结构扩展为有双亲域,长子域,再有右兄弟域。存储结构的设计是一个非常灵活的过程。一个存储结构设计的是否合理,取决于基于该春初结构的运算是否适合,方便,时间复杂度好不好等。 注意也不是越多越好,有需要时在设计相应的结构。


H3

孩子表示法

换一种完全不同的考虑方法。由于树中每个节点可能有多颗子树,可以考虑用多重链表,即 每个节点都有多个指针域,其中每个指针指向一个子树的跟结点,我们就把这种放啊,叫做多重链表表示法。 不过,树的每个节点的树,也就是他的孩子格式视图不同的,所以可以设计两种方案来解决。
方案一
一种时指针域的个数就等于输的度,复习一下,树的度时各个节点度的最大值。结构如下


Image Description
指针域树的结构


其中data是数据域,child到childd是指针域,用来只想该结点的孩子结点。
对于图6-4-1来说,树的度是3,所以我们的指针域的个数是3,这种方法实现如下所示。


Image Description
链表指针域


这种方法对于树中各结点的度差异很大时,显然是浪费空间的,因为有很多的结点,他的指针域时空的。不过如果书的各结点度相差很小时,那就意味着开辟的空间被充分利用了,这是存储结构的缺点反而变成了优点。
既然很多指针域都可能为空,为什么不按需分配空间呢。于是我们有了第二种方案。
方案二
第二种方案每个节点指针域的个数等于该结点的度,我们专门去一个位置来存储结点指针域的个数


Image Description
指针域个数等结点的度


其中data为数据域,degree为度域,也就是存储该结点的孩子结点的个数,child1到childd为指针域,只想该结点各个孩子的结点。


Image Description
指针域等于度示意图


这种方法克服了浪费空间的缺点,对空间利用率很高了,但是由于每个节点的链表是不相同的结构,加上要维护结点的度的数值,在运算上就会带来时间上的损耗。
能否有更好的方法,既可以减少控制真的浪诶又能使结点结构相同。
仔细观察,我们为了要遍历政客书,把每个节点放在一个舒徐存储结构的数组是合理的,但每个结点的孩子的有多少是不确定的,所以我们在对每个节点的孩子建立一个单链表体现他们的关系。
这就是我们要将的孩子表示法。具体实现办法是,把每个节点的孩子结点排序起来,以单链表做存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序排序规则,存放斤一个一维数组中。


Image Description
孩子表示法示意图


为此,设计两种结点结构,一种是孩子链表的孩子结构。


Image Description
孩子表示法孩子结构示意图


其中child是数据域,用来存储某个节点在表头数组中的下标。next是指针域,用来存储只想某结点的下一个孩子结点的指针。
另一个是表头数组的表头结构。


Image Description
孩子表示法表头结构示意图


其中data是数据域,存储某结点的数据信息,firstchild 是头指针域,存储钙及诶单孩子链表的头指针。
这样的结构对于我们要茶渣某个节点的某个孩子,或者找某个节点的兄弟,只徐耀查找这个结点的孩子单链表即可。对于遍历政客书也是很方便的,对头结点的数组循环即可。
但是,这也存在着问题,我如何知道某个节点的双亲是谁呢?比较麻烦,徐耀整合树遍历才行,难道就不可以把双亲表示法和孩子表示法综合一下吗?当然是可以的


Image Description
双亲表示法孩子表示法结合示意图


我们把这种方法称为双亲孩子表示法,应该算是孩子表示法的改进。


H3

孩子兄弟表示法

刚才分别从双亲的角度和从孩子的角度研究书的存储结构,如果我们从树结点的兄弟的角度又会如何呢?当然,对于树这样的层级结构来说,只研究结点的兄弟是不行的,我们观察后发现。任意一棵树,他的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,我们设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。


Image Description
存储示意图


其中data是数据域,firstchild为指针域,存储该结点的第一个孩子结点的存储地址,rightsib是指针域,存储该结点的右兄弟结点的存储地址。


Image Description
孩子兄弟表示法示意图


这种表示法,给查找某个节点的某个孩子带来了方便,只需要通过firstchild找到该结点的长子,然后再通过的长子结点的rightsib找到他的二弟,接着一直下去,直到找到具体的孩子。当然,如果想要找到某个结点的双亲,这个表示法也是有缺陷的。怎么办呢啊你?
嗯,如果真的有必要,完全可以再增加一个parent指针域来解决快速查找双亲的问题。
其实这个表示法的最大好处是它把一个复杂的树变成了一个二叉树


Image Description
孩子兄弟表示法二叉树


H2

二叉树的定义

对于在某个阶段都是两种结果的情形,比如开和关,0和1,真和假,上和下等,都适合用树状结构来建模,而这种书是一种很特殊的树状结构,叫做二叉树。

二叉树(Binary Tree)是n(n>=0)个基点的有限集合,该集合或者为空集(称为空二叉树),或者有一个根结点和两个互不相交的,分别称为跟结点的左子树和右子树的二叉树组成。

图6-5-2就是一颗二叉树,而图6-2-1的树,因为D结点有三个子树,所以他不是二叉树。


Image Description
二叉树示意图


H3

二叉树的特点

二叉树的特点有:

  • 每个节点最多有两颗子树,所以二叉树中不存在度大于2的结点。注意不是只有两个子树,而是最多有。没有子树或者有一颗子树都是可以的。
  • 左子树和右子树是有顺序的,次序不能任意颠倒。就像人是双手,双脚,但是左手和右手 左脚和右脚是不一样的 。
  • 即使树中的某个及诶单只有一个子树,也要区分他们是左子树还是右子树。

二叉树具有五种基本形态:

  1. 空二叉树
  2. 只有一个跟结点
  3. 根结点只有左子树
  4. 根结点只有右子树
  5. 根结点既有左子树又有右子树

应该说这五种状态还是比较好理解的。接下来我们来考虑下只有三个结点的二叉树会有几种形态呢?
若只从形态上考虑,三个节点的树只有两种情况,那就是图6-5-4中的有两层的树1和有三层的后四种的任意一种,但是对于二叉树来说由于区分左右,所以就演变了五种形态


Image Description
只有三个结点的五种形态


H3

特殊二叉树

我们再来介绍一些特殊的二叉树。这些书可能暂时你不能理解他有什么用处,但先了解一下,以后会提到他们的实际用途。

  1. 斜树
    顾名思义,斜树一定要斜的,但是往哪儿斜是有讲究的。所有的及诶单都只有左子树的二叉树叫做左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。 图6-5-4中的树2就是左斜树。树5就是右斜树。斜树有很明显的特点,就是每一层都只有一个及诶单,结点的个数和二叉树的深度是相同的。
    有人会想这还叫树呀,与我们的线性结构不是一样吗。对的其实线性结构就可以理解为树的一种及其特殊的表现形式
  2. 满二叉树
    苏东坡曾有诗云:“人有悲欢离合,月有阴晴圆缺,此事古难全”。意思就是说完美是理想,不完美才是人生。我们通过通常的例子也都是左高右低,参差不齐的二叉树,那是否存在完美的二叉树呢?
    在一棵二叉树中,如果所有分之结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树被称为满二叉树


    Image Description
    满二叉树


    但是每个节点都存在左右子树,不能算是满二叉树,还比徐耀所有的叶子都在同一层,这就能做到整颗树的平衡。因此,满二叉树的特点有:
    1. 叶子只能出现在最下一层,出现在其他层就不可能达到平衡了。
    2. 非叶子结点的度一定是2,否则就是缺胳膊少腿了
    3. 在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多
  3. 完全二叉树
    对一棵树具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点于同样深度的满二叉树的编号为i的结点的在二叉树中位置完全相同,则这颗二叉树被称为完全二叉树。


    Image Description
    完全二叉树


    这是一种有些理解难度的特殊二叉树。
    首先要从字面上区分,“完全”和“满”的差异,满二叉树一定是一颗完全二叉树,但完全二叉树不一定是满的
    其次,完全二叉树的所有节点与同样深度的满二叉树,他们按层序编号相同的结点,是一一对应的。这里有个关键词是按层序编号,像图6-5-7中的树1,因为5结点没有左子树,却又右子树,那就使得按层序编号的第10个编号空荡了


    Image Description
    分析完全二叉树特点


    从这里我也可以得出一些完全二叉树的特点:
    1. 叶子结点只能出现在最下两层
    2. 最下层的叶子一定集中在左部连续位置
    3. 倒数二层,如有叶子结点,一定都在右部连续位置
    4. 如果结点度为1,则该结点只有左孩子,既不存在只有右子树的情况。
    5. 同样结点的二叉树,完全二叉树的结点最小
      从上面的例子,也给了我们一个判断某二叉树是否是完全二叉树的办法,那就是看着书的示意图,心中默默给每个节点按照满二叉树的结构储层编号,如果编号出现空档,就书评不是完全二叉树,否则就是。

H2

二叉树的性质

二叉树有一些徐耀并记住的特性,以便于我们更好的使用它。


H3

二叉树性质1

性质1: 在二叉树的第i层至少有2i-1个结点(i>=1)。
这个性质很好记忆,观察一下图6-5-5。
第一层是跟结点,只有一个,所以2^{1-1}即2^{0}=1。
第二层有两个

通过数据归纳法的论证,可以很容易地得出在二叉树第i层上至少有2^{i-1}个结点(i>=1)的结论。


H3

二叉树性质2

性质2: 深度为k的二叉树至少有2^{k}-1个结点(k>=1)
注意这里一定要看清楚,是2^{k}后在减去1,而不是2^{k-1}。以前很多同学不能完全戒,这样去记忆,就容易把性质1和2弄混淆了。
深度为k的意思就是k有两层树。我们先来看简单的
如果有一层,至多1=2^{0}-1个结点
如果有两层,至多1+2=3=2^{2}-1各结点
….
通过数据归纳法的论证,可以得出,如果有k层,此二叉树之多有2^{k}-1个结点。


H3

二叉树性质3

性质3:对任何一颗二叉树T,如果其终端结点树为n{0},度为2的结点n{2},则n{0}=n{2}+1。
终端结点其实就是叶子结点树,而一颗二叉树,除了叶子结点树,剩下的就是度1或2的几点输了,我们设n{1}为度是1的结点树。则树T的结点总数n=n{0}+n{1}+n{2}。
比如图6-6-1的例子,结点总数为10,他是由A,B,C,D等度为2结点,F,G,H,I等度为0的叶子结点和E这个度为1的及诶单组成。综合为4+1+5=10.


Image Description
二叉树性质3


我们换个角度,再数一数他的链接线数,由于跟结点只有分支出去,没有分支进来,所以分之嫌总数为结点总数减去1.图6-6-1就是9个分支。对于ABCD结点来说,他们都有两个分支线出去,而E结点只有一个分支线出去。所以总分支线为4x2+1x1=9.
用袋鼠表达就是分支线总数=n-1=n{1}+2n{2}结论就是n{0}=n_{2}+1.


H3

二叉树性质4

性质4:具有n个结点的完全二叉树的深度为[Log_{2n}]+1([x]表示不大于x的最大整数)。
由二叉树的定义我们可以知道,深度为k的满二叉树的结点n一定是Sk-1.因为这个是最多的结点个数。那么对于n=2k-1倒退得到满二叉树的度数为k=log2(n+1),比如说结点为15的满二叉树,度为4.
完全二叉树我们已经提到,它是一颗觉有n个结点的二叉树,若按层序编号,与其同样深度的满二叉树编号几点在二叉树位置完全相同,那他就是完全二叉树。也就是说,它的叶子结点只会出现爱着妳最下面的两层。
它的结点树一定少雨等于同样读书的满二叉树的结点树2k-1但一定不会多余2k-1-1,


H3

二叉树性质5

性质5:如果对一颗由n个结点的完全而二叉树(其深度为[log2n]+1)的结点按层序变化

…. 性质这里蒙蔽了。。有时间再说


H2

二叉树的存储结构


H3

二叉树的顺序存储结构

前面我们已经谈到了树的存储结构,并且谈到顺序存储结构对树这种一对多的关系结构实现起来是比较困难的。但是二叉树是一种特殊的树,由于它的特殊性,使得用顺序存储结构也可以实现。
二叉树的顺序存储结构就是用一位数组存储二叉树中的结点,并且结点的存储位置,也就是鼠标的下标要能体现节点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系等。
先来看看完全二叉树的顺序存储,一颗完全二叉树如6-7-1所示。


Image Description
完全二叉树顺序存储示意图


将这颗二叉树村入数组中,相应的下标对应起同样的位置。


Image Description
完全二叉树顺序存储结构


这些看出俄安全二叉树的优越性来了吗。由于它定义的严格,所以用顺序结构也可以表现出二叉树的结构来,当然对于一般的二叉树,筋骨按层序编号不能反映逻辑关系,但是可以按前完全二叉树编号只不过,把不存在的结点设置为“^”而已。如图6-7-3.注意浅色结点表示不存在


Image Description
非完全二叉树顺序存储


考虑一种极端的情况,一颗深度为k的右斜树,他只有k各结点,却要分配2k-1个存储但愿空间,这显然是对存储空间的浪费。所以顺序存储结构一般只用于完全二叉树。


Image Description
特殊情况对于存储空间的浪费


H3

二叉链表

既然顺序存储适用性不强,我们就要考虑链式存储结构。二叉树每个节点最多有两个孩子,所以为她设计一个数据域和两个指针域是比较自然的想法,我们成这样的链表叫做二叉链表。


Image Description
二叉链表结构示意图


其中data是数据域,ichild和richild都是指针域,分别存放左孩子和右孩子的指针。


Image Description
二叉链示意图


就如同树的存储结构中讨论的一样,如果有徐耀,还可以再增加一个只想起双亲的指针域,那样我们称之为s三叉链表,由于与树的存储结构类似,这里就不详述了。


H2

遍历二叉树


H3

二叉树遍历原理

假设,我手头头20长100元和2000张1元的奖券,同时撒向了空中,大家比赛开谁最终见得最多。如果是你你会怎么办?
相信所有的同学都会说鲜见100原单额。

二叉树的遍历(Traversing binary tree)是指从很结点出发,按照某种需一次访问二叉树中所有节点,使得每个节点被访问一次且仅访问一次。

这里有两个关键词,访问和次序。
访问其实要跟根据实际的需要来确定具体做什么,比如每个结点哦度进行相关计算,输出打印等,它算作是一个抽象操作。在这里我们可以简单的嘉定就是输出结点的数据信息。
二叉树的遍历次序不同于线性结构,最多也就是从头至尾,循环,双向等见扽遍历方式。树的结点之间不存在唯一的前驱和后继的关系,在访问一个节点后,下一个被访问的结点面临着不同的选择。就像你人生的道路上。由于选择方式的不同,遍历的次序就完全不同了。


H3

二叉树遍历方法

二叉树遍历方式恶意很多,如果我们限制了从左到右的习惯方式,那么主要就分为四种。

  1. 前序遍历
    规则是若二叉树为空,则空操作返回,否则先访问跟结点,在遍历左子树,在前序遍历右子树。遍历的舒徐是ABDHCEIF。


    Image Description
    前序遍历示意图

  2. 中序遍历
    规则是若树为空,则空操作返回,否则从跟结点开始(注意并不是先访问跟结点),中序遍历跟结点的左子树,然后是访问跟结点,最后中序遍历右子树。所以遍历的顺序是 GDHBAEICF。


    Image Description
    中序遍历示意图

  3. 后序遍历
    规则是若树为空,则空操作返回,否则就从左到右先叶子后结点的方式遍历访问左右子树,最后访问跟结点。遍历的顺序是GHDBIEFCA。


    Image Description
    后序遍历示意图

  4. 层序遍历
    规则是若树为空,则空操作返回,否则丛书的第一层,也就是跟结点开始访问,从上而下储层便利。从左到右顺序对结点出个访问。ABCDEFGHI。


    Image Description
    层序遍历示意图

我们同图形的方式来表现书的结构,应该说是非常直观和容易理解,但是对于计算机来说,她只有循环,判断等方式来处理,也就是说,他只会处理线性序列,而我们刚才提到的四种变方法,其实就是把树中的结点变成某种意义的线性序列,这就给程序的实现带来了好处。
另外不同的遍历提供了对结点一次护理的分不同方式,可以在遍历过程中对结点进行各种处理。


H2

排序算法

在排序之前,先让我们建立一些数据

class TreeNode{

    /// 存储的值
    var value:String

    /// 左子树和右子树
    var leftTreeNode:TreeNode?
    var rightTreeNode:TreeNode?

    private init(value:String) {
        self.value = value
    }

    private func setLeft(treeNode:TreeNode?) -> TreeNode {
        self.leftTreeNode = treeNode
        return self
    }


    private func setRight(treeNode:TreeNode?) -> TreeNode {
        self.rightTreeNode = treeNode
        return self
    }

    /// 初始化后的数据源 单例
    static let rootTreeNode: TreeNode = {

        let AtreeNode = TreeNode(value: "A")
        let BtreeNode = TreeNode(value: "B")
        let CtreeNode = TreeNode(value: "C")
        let DtreeNode = TreeNode(value: "D")
        let EtreeNode = TreeNode(value: "E")
        let FtreeNode = TreeNode(value: "F")
        let GtreeNode = TreeNode(value: "G")
        let HtreeNode = TreeNode(value: "H")
        let ItreeNode = TreeNode(value: "I")

        AtreeNode.setLeft(treeNode: BtreeNode).setRight(treeNode: CtreeNode)
        BtreeNode.setLeft(treeNode: DtreeNode)
        CtreeNode.setLeft(treeNode: EtreeNode).setRight(treeNode: FtreeNode)
        DtreeNode.setLeft(treeNode: GtreeNode).setRight(treeNode: HtreeNode)
        EtreeNode.setRight(treeNode: ItreeNode)

        return AtreeNode
    }()
}

我们通过上面的代码获取到的rootTreeNode 就是图 6-8-2 掩饰的数据结构了。接下来让我们一次实验这些不同的排序算法把


H3

前序遍历算法

/// 前序遍历算法
extension TreeNode {

    func preOrderTraverse(){

        print(self.value)
        self.leftTreeNode?.preOrderTraverse()
        self.rightTreeNode?.preOrderTraverse()
    }
}

print("-----preOrderTraverse-------")
TreeNode.rootTreeNode.preOrderTraverse()

打印结果

-----preOrderTraverse-------
A
B
D
H
K
E
C
F
I
G
J

前序算法,其实就是先遍历所有的左子树,在遍历了左子树没有了之后,就前往上一层的遍历右子树,之后继续循环


H3

中序遍历方法

/// 中序遍历算法
extension TreeNode {

    func inOrderTraverse(){

        self.leftTreeNode?.inOrderTraverse()
        print(self.value)
        self.rightTreeNode?.inOrderTraverse()
    }
}

print("-----inOrderTraverse-------")
TreeNode.rootTreeNode.inOrderTraverse()

打印结果

-----inOrderTraverse-------
H
K
D
B
E
A
F
I
C
G
J

中序就是顺序错开一点,循环遍历直到找到最左叶开始打印,之后遍历回来


H3

后序遍历方法

/// 后序遍历算法
extension TreeNode {

    func postOrderTraverse(){

        self.leftTreeNode?.postOrderTraverse()
        self.rightTreeNode?.postOrderTraverse()
        print(self.value)
    }
}

print("-----postOrderTraverse-------")
TreeNode.rootTreeNode.postOrderTraverse()

打印结果

-----postOrderTraverse-------
K
H
D
E
B
I
F
J
G
C
A

H3

层序遍历算法


/// 层序遍历算法
extension TreeNode{

    func cengOrderTraverse(){
        var treeNodes = [self]
        while treeNodes.count > 0 {
            guard let selfNode = treeNodes.last else {
                return
            }
            if let rn = selfNode.leftTreeNode {
                treeNodes.insert(rn, at: 0)
            }
            if let ln = selfNode.rightTreeNode {
                treeNodes.insert(ln, at: 0)
            }
            print(selfNode.value)
            treeNodes.removeLast()
        }
    }
}

print("-----cengOrderTraverse-------")
TreeNode.rootTreeNode.cengOrderTraverse()

打印结果

-----cengOrderTraverse-------
A
B。
C
D
E
F
G
H
I
J
K

H2

二叉树的创建

…… 暂时搁置


H2

线索二叉树


H3

线索二叉树原理

我们现在提倡节约型社会,一切都应该节约为本。对待我们的程序也不例外,能不浪费的时间或空间偶应该考虑节省,我们再来考虑6-10-1,会发现指针域并不是都充分的利用了,有许许多多的”^”,也就是空指针域的存在,这实在不是好现象,应该要想办法利用起来。


Image Description
二叉树利用率低示意图


首先我们要来看看这空指针有多少个呢?对于一个有n个绩点的二叉链表,每个节点有志向左右孩子的两个指针域,所以一共是2n个指针域,而n个结点的二叉树一共有n-1条分支线数,也就是说,其实是存在2n-(n-1)=n+1个空指针域。这些空间不怒出任何事物,白白地浪费着内存的资源。
另一方面,我们左遍历时,遍历了之后,我们可以知道。
可以这是建立过的基础之上的,在二叉链表上,我们只能知道每个节点只想起左右

专栏: 数据结构
标签: 数据结构 计算机基础