专栏首页我是攻城师深入理解二叉树的特点

深入理解二叉树的特点

前言

在计算机科学中,二叉树(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),作者:攻城师在路上

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构之(树)

    在计算机科学中,树(英语:tree)是一种非线性的抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0...

    我是攻城师
  • 图形数据库之Neo4j核心概念介绍(二)

    我是攻城师
  • 5分钟轻松理解二叉树的深度遍历策略

    我们知道普通的线性数据结构如链表,数组等,遍历方式单一,都是从头到尾遍历就行,但树这种数据结构却不一样,我们从一个节点出发,下一个节点却有可能遇到多个分支路径,...

    我是攻城师
  • 详解算法之重建二叉树

    从今天开始,公众号陆陆续续开始插写用动画形式展现算法题,如剑指offer、Leedcode里经典面试题型,同时也会更新数据结构与算法基础、网络原理等知识。

    帅地
  • 二叉树的重建

    在http://blog.csdn.net/hacker_zhidian/article/details/60586445这篇文章中我们看了一下二叉树的四种遍历...

    指点
  • 二叉树的四种遍历算法

    二叉树在作为一种重要的数据结构,它的很多算法的思想在很多地方都用到了,比如说大名鼎鼎的 STL 算法模板,里面的优先队列(priority_queue)、集合(...

    指点
  • 每天一算:二叉树的层次遍历

    五分钟学算法
  • 数据结构(七)

    在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常...

    可爱见见
  • 二叉树非递归版的中序遍历算法

    本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有,分而治之,搜索,动态规划,回溯,贪心等,结合这些思想再去思考如今很火的大数据,云计算和机器学习,...

    double
  • 算法与数据结构(三) 二叉树的遍历及其线索化(Swift版)

    前面两篇博客介绍了线性表的顺序存储与链式存储以及对应的操作,并且还聊了栈与队列的相关内容。本篇博客我们就继续聊数据结构的相关东西,并且所涉及的相关Demo依然使...

    lizelu

扫码关注云+社区

领取腾讯云代金券