数据结构与算法整理总结---二叉树

我们⾸先来看,什么是“树”?再完备的定义,都没有图直观。所以我在图中画了⼏棵“树”。你来看看,这些“树”都有什么特征?

数据结构与算法整理总结---二叉树

你有没有发现,“树”这种数据结构真的很像我们现实⽣活中的“树”,这⾥⾯每个元素我们叫作“节点”;⽤来连线相邻节点之间的关系,我们叫作“⽗⼦关系”。

⽐如下⾯这幅图,A节点就是B节点的⽗节点,B节点是A节点的⼦节点。B、C、D这三个节点的⽗节点是同⼀个节点,所以它们之间互称为兄弟节点。我们把没有⽗节点的节点叫作根节点,也就是图中的节点E。我们把没有⼦节点的节点叫作叶⼦节点或者叶节点,⽐如图中的G、H、I、J、K、L都是叶⼦节点。

数据结构与算法整理总结---二叉树

除此之外,关于“树”,还有三个⽐较相似的概念:⾼度(Height)、深度(Depth)、层(Level)。它们的定义是这样的:

数据结构与算法整理总结---二叉树

数据结构与算法整理总结---二叉树

⼆叉树(Binary Tree)

⼆叉树,顾名思义,每个节点最多有两个“叉”,也就是两个⼦节点,分别是左⼦节点和右⼦节点。不过,⼆叉树并不要求每个节点都有两个⼦节点,有的节点只有左⼦节点,有的节点只有右⼦节点。我画的这⼏个都是⼆叉树。以此类推,你可以想象⼀下四叉树、⼋叉树⻓什么样⼦。

数据结构与算法整理总结---二叉树

这个图⾥⾯,有两个⽐较特殊的⼆叉树,分别是编号2和编号3这两个。其中,编号2的⼆叉树中,叶⼦节点全都在最底层,除了叶⼦节点之外,每个节点都有左右两个⼦节点,这种⼆叉树就叫作满⼆叉树。

编号3的⼆叉树中,叶⼦节点都在最底下两层,最后⼀层的叶⼦节点都靠左排列,并且除了最后⼀层,其他层的节点个数都要达到最⼤,这种⼆叉树叫作完全⼆叉树。

满⼆叉树很好理解,也很好识别,但是完全⼆叉树,有的⼈可能就分不清了。我画了⼏个完全⼆叉树和⾮完全⼆叉树的例⼦,你可以对⽐着看看。

数据结构与算法整理总结---二叉树

满⼆叉树的特征⾮常明显,我们把它单独拎出来讲,这个可以理解。但是完全⼆叉树的特征不怎么明显啊,单从⻓相上来看,完全⼆叉树并没有特别特殊的地⽅啊,更像是“芸芸众树”中的⼀种。

那我们为什么还要特意把它拎出来讲呢?为什么偏偏把最后⼀层的叶⼦节点靠左排列的叫完全⼆叉树?如果靠右排列就不能叫完全⼆叉树了吗?这个定义的由来或者说⽬的在哪⾥?

要理解完全⼆叉树定义的由来,我们需要先了解,如何表示(或者存储)⼀棵⼆叉树?

想要存储⼀棵⼆叉树,我们有两种⽅法,⼀种是基于指针或者引⽤的⼆叉链式存储法,⼀种是基于数组的顺序存储法。

我们先来看⽐较简单、直观的链式存储法。从图中你应该可以很清楚地看到,每个节点有三个字段,其中⼀个存储数据,另外两个是指向左右⼦节点的指针。我们只要拎住根节点,就可以通过左右⼦节点的指针,把整棵树都串起来。这种存储⽅式我们⽐较常⽤。⼤部分⼆叉树代码都是通过这种结构来实现的。

数据结构与算法整理总结---二叉树

我们再来看,基于数组的顺序存储法。我们把根节点存储在下标i = 1的位置,那左⼦节点存储在下标2 * i = 2的位置,右⼦节点存储在2 * i + 1 = 3的位置。以此类推,B节点的左⼦节点存储在2 * i = 2 * 2 = 4的位置,右⼦节点存储在2 * i + 1 = 2 * 2 +1 = 5的位置。

数据结构与算法整理总结---二叉树

如果节点X存储在数组中下标为i的位置,下标为2 * i 的位置存储的就是左⼦节点,下标为2 * i + 1的位置存储的就是右⼦节点。反过来,下标为i/2的位置存储就是它的⽗节点。通过这种⽅式,我们只要知道根节点存储的位置(⼀般情况下,为了⽅便计算⼦节点,根节点会存储在下标为1的位置),这样就可以通过下标计算,把整棵树都串起来。

不过,我刚刚举的例⼦是⼀棵完全⼆叉树,所以仅仅“浪费”了⼀个下标为0的存储位置。如果是⾮完全⼆叉树,其实会浪费⽐较多的数组存储空间。你可以看我举的下⾯这个例⼦。

数据结构与算法整理总结---二叉树

所以,如果某棵⼆叉树是⼀棵完全⼆叉树,那⽤数组存储⽆疑是最节省内存的⼀种⽅式。因为数组的存储⽅式并不需要像链式存储法那样,要存储额外的左右⼦节点的指针。这也是为什么完全⼆叉树会单独拎出来的原因,也是为什么完全⼆叉树要求最后⼀层的⼦节点都靠左的原因。

⼆叉树的遍历

如何将所有节点都遍历打印出来呢?经典的⽅法有三种,前序遍历、中序遍历和后序遍历。其中,前、中、后序,表示的是节点与它的左右⼦树节点遍历打印的先后顺序。

前序遍历是指,对于树中的任意节点来说,先打印这个节点,然后再打印它的左⼦树,最后打印它的右⼦树。

中序遍历是指,对于树中的任意节点来说,先打印它的左⼦树,然后再打印它本身,最后打印它的右⼦树。

后序遍历是指,对于树中的任意节点来说,先打印它的左⼦树,然后再打印它的右⼦树,最后打印这个节点本身。

数据结构与算法整理总结---二叉树

实际上,⼆叉树的前、中、后序遍历就是⼀个递归的过程。⽐如,前序遍历,其实就是先打印根节点,然后再递归地打印左⼦树,最后递归地打印右⼦树。

写递归代码的关键,就是看能不能写出递推公式,⽽写递推公式的关键就是,如果要解决问题A,就假设⼦问题B、C已经解决,然后再来看如何利⽤B、C来解决A。所以,我们可以把前、中、后序遍历的递推公式都写出来。

数据结构与算法整理总结---二叉树

前⾯画的前、中、后序遍历的顺序图,可以看出来,每个节点最多会被访问两次,所以遍历操作的时间复杂度,跟节点的个数n成正⽐,也就是说⼆叉树遍历的时间复杂度是O(n)。

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!