树转化为二叉树_深入理解二叉树的特点

前言

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

一些术语

深度&＃xff1a; 从根节点到指定节点的边的个数

高度&＃xff1a; 从指定节点到叶子节点的边的个数

树的高度&＃xff1a; 指的是根节点的高度&＃xff0c;也即根节点到最深叶子节点的边的个数。

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

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

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

注&＃xff1a;时间复杂度O里面&＃xff0c;通常忽略掉常数项。

树结构的优点

主要优点如下&＃xff1a;

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

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

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

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

满二叉树 VS 完全二叉树

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

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

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

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

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

(三)用来做二叉搜索树

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

树的遍历

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

深度优先遍历又分为三种策略&＃xff1a;

(1)前序遍历 (先根节点&＃xff0c;然后左孩子和右孩子)

(2)中序遍历 (先左孩子&＃xff0c;然后父节点和右孩子)

(3)后序遍历 (先左孩子&＃xff0c;然后右孩子和父节点)

(二) 广度优先遍历

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

如下图使用不同的遍历输出&＃xff1a;

前序&＃xff1a; 8, 5, 9, 7, 1, 12, 2, 4, 11, 3

中序&＃xff1a; 9, 5, 1, 7, 2, 12, 8, 4, 3, 11

后序&＃xff1a; 9, 1, 2, 12, 7, 5, 3, 11, 4, 8

层级顺序&＃xff1a;8, 5, 4, 9, 7, 11, 1, 12, 3, 2

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

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

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

前序遍历&＃xff1a;

中序遍历&＃xff1a;

后序遍历&＃xff1a;

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

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

总结

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

参考链接&＃xff1a;

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