深入理解二叉树的特点

前言

在计算机科学中,二叉树(Binary tree)是一个连通的无环图,每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。最顶层的节点称为root节点,也就是根节点。每个具有1个或者2个的子节点的节点称为父节点,没有子节点的节点称为叶子节点。拥有同一个父节点的节点称为兄弟节点。

一些术语

深度: 从根节点到指定节点的边的个数

高度: 从指定节点到叶子节点的边的个数

树的高度: 指的是根节点的高度,也即根节点到最深叶子节点的边的个数。

满二叉树: 指的是树中每个节点有必须有0个或者2个子节点的二叉树。如下:

完全二叉树:是指在二叉树里面除了最下面的2层节点之外,之上的节点都必须有2个孩子节点,最底层的叶子节点没有孩子,在倒数第二层的节点可以拥有0,1,2个孩子节点,此外,最底层级别的节点添加必须从左到右,不能跳跃。如下:

完全二叉树是非常特别的树,它尽可能的保证了均衡性,拥有N个节点的完全二叉树的的高度最大是O(log N),这里可以很容易观察到规律,如:N= 1 + 2 + 4 + 8 + 2的h次方 ,求高度h=2(h+1)次方-1求对数=O(log n)。

注:时间复杂度O里面,通常忽略掉常数项。

树结构的优点

主要优点如下:

(1)树结构可以反映数据里面的结构化关系。

(2)树结构常常用来代表层级和等级

(3)树结构提供了高效的插入和搜索。(与HashMap的区别在于Tree结构可以提供范围检索,排序等额外优点)

(4)树结构是非常灵活的,可以付出很小的代价移动一颗子树。

满二叉树 VS 完全二叉树

(一) 不是每一个满二叉树都是完全二叉树

(1) 满二叉树的叶子节点可以出现在任何级别,完全二叉树只能出现最底层的两个级别。

(2) 满二叉树最底层的级别的添加,不需要从左到右

(二)不是每一个完全二叉树都是一个满二叉树

(1)完全二叉树的节点可以拥有0,1,2 个孩子节点,而满二叉树只能是0或者2个。

(三)用来做二叉搜索树

当使用满二叉树或者完全二叉树来做二叉搜索树的时候,树的均衡性至关重要,节点的深度决定了找到一个具体的节点,需要经过几次查询,从这一点看完全二叉树是更适合的,因为它更加均衡,但其缺点是在删除或者添加节点时,需要重新调整结构,这样就有可能导致一大批节点移动,这是它的不足之处。因此出现了一些改进的拥有不错平衡能力的树结构,如红黑树和AVL树,实际上它们是在满二叉树基础上并加入了额外的约束来保证平衡性。比如在红黑树里面,为了保证满足满二叉树的特点,其所有节点都有两个子节点,尽管其中的一个或两个可能是空叶子(用null表示),这个后续在细说。

树的遍历

遍历指的是访问整颗树的所有节点,由于树是一个非线性的数据结构,所以这儿没有唯一的遍历方式,大体上可分为两种遍历类型: (一) 深度优先遍历

深度优先遍历又分为三种策略:

(1)前序遍历 (先根节点,然后左孩子和右孩子)

(2)中序遍历 (先左孩子,然后父节点和右孩子)

(3)后序遍历 (先左孩子,然后右孩子和父节点)

(二) 广度优先遍历

广度优先遍历仅仅只有一种策略按层级顺序遍历,遍历的顺序是从顶到底,从左到右。

如下图使用不同的遍历输出:

前序: 8, 5, 9, 7, 1, 12, 2, 4, 11, 3

中序: 9, 5, 1, 7, 2, 12, 8, 4, 3, 11

后序: 9, 1, 2, 12, 7, 5, 3, 11, 4, 8

层级顺序:8, 5, 4, 9, 7, 11, 1, 12, 3, 2

我相信除了层级遍历比较好理解外,深度遍历的三种方式都不太好理解,尽管我们在实现的时候使用递归方式,可以写出来非常简洁的代码,但是如果不理解原理,还是非常抽象,其实树的遍历,是图论里面一种遍历形式。这里面有一个著名的问题叫一笔画问题(也称欧拉回路),一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题,也提出了一笔画定理,顺带解决了一笔画问题[1]。一般认为,欧拉的研究是图论的开端。

对于有向图来说,一笔画不仅指遍历所有边,而且要遵循正确的方向。严谨地说,一个连通有向图 G有欧拉路径,指存在一个顶点,从它出发,沿着有向边的方向,可以不重复地遍历图中所有的边。有向图的欧拉回路则是指可以从某一顶点开始,沿有向边的方向不重复地遍历所有边,然后回到原来出发的顶点。定理不理解无所谓,我们看看如何将书遍历问题转化成了图遍历问题,从而可以快速写出上面的三种深度遍历的结果。

我们将上面的树遍历,转化为使用欧拉回路进行对二叉树的散步,其中每条边都是一道墙,你不能横穿。在此步骤中,先后从左侧,底部,右侧开始散步,分别可得到前序遍历,中序遍历,后序遍历的结果。图示如下:

前序遍历:

中序遍历:

后序遍历:

注意上面的图里面,大黑圆点的地方是遍历开始的地方,一定要把树的每一条边当成是实体墙,是不能横穿的,然后从起点开始,沿着指定有序的路线散步,走一圈之后再返回到起点的时候,就遍历完成。注意某一节点可以经过两次遍历,因为是在墙的两侧散步。 通过转化成空间的方式来理解树 的遍历,其实是非常直观的。如果掌握了这种方式,就可以很快给一个二叉树画出各种遍历的结果。

最后在广度优先的层级遍历中,这个其实最容易理解,就是沿着从上到下,从左到右的顺序连线即可。

总结

本文主要了讲解了关于二叉树的基本理论知识,这些基础知识是我们后续研究更高级的树结构的基石,如二叉搜索树,红黑树,跳跃表等。这些高级的数据结构在很多编程语言的底层库里面都有对应的实现,掌握了这些结构的原理,将更有助于我们开发,调优,排错。

参考链接:

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html

https://www.quora.com/What-is-the-difference-between-complete-and-full-binary-trees

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2019-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券