vlambda博客
学习文章列表

数据结构系列的文章我们之前已经说过数组，链表，哈希表以及队列等等，上一篇也简单的介绍下了树的概念，从今天开始，我们就进入二叉树的学习，这可是面试官最喜欢的问题之一，务必掌握牢固哦！

回顾树的那些事

在介绍二叉树之前，我们有必要再来看看关于树的一些关键性概念，毕竟，二叉树也是树嘛。

我们首先应该了解的就是树这种数据结构属于非线性结构，然后存储的数据具有一对多的关系，这是最最基本的概念了。

几个概念名词要分清

然后我们需要清楚关于树的一个关键性的概念名词。

节点：什么是节点呢？这个节点也有叫做结点，这两个应该没有区别吧，我看过不少文章，有的叫做节点，有的叫做结点，我觉得节点更加合适，因为我们喜欢使用Node来定义一个节点，Node一般翻译过来就是节点二字。

那啥是节点：

简单来说，树结构存储的每一个元素都叫做一个节点

也就是在树这种结构中存储的元素都叫做节点，然后根据有些节点的特殊位置可能会有不同的叫法。

比如根节点，根节点只有一个，最上面的那个节点，还有父节点，子节点和兄弟节点，这些其实都不难理解，属于树的基础知识，不了解的可以看这篇文章，有详细的介绍：来吧！一文彻底搞定数据结构之树！

除了节点，还有子树和空树的概念，以及节点的度和层次，树的高度或者说是深度，这些都可以在上面提到的这篇文章中找到，这里简单说下节点的度和层次，先看一个图：

度：对于一个节点而言，拥有的子树数称为节点的度（Degree）。比如，图中根节点 A 下分出了 3 个子树（BCD），所以，结点 A 的度为 3。

树的度：一棵树的度是树内各节点的度的最大值。图 中，各个节点的度的最大值为 3，所以，整棵树的度的值是 3。

另外再提下树的高度或者深度：

一棵树的深度（高度）是树中节点所在的最大的层次。注意这里说的是一个树的，而不是某个节点的，因为对于一个树而言，高度从下往上和深度从上往下都是一样的，但是对于某个节点而言高度和深度就不一样了

tips：关于这些基本概念，最好就是自己完全理解，知道是怎么一回事，而不是机械的去记忆，不然即使当时记住了，要不几天也就忘得差不多了

英文名字Binary Tree

对了，一定要记住二叉树的英文是Binary Tree😄，接下来我们开始探讨那些你需要牢记的关于二叉树的那些知识点。

二叉树的特点

任何一种数据机构都有它们自己的特点，这是区别于其他数据结构，以及为什么是这样的重点所在，正式由于这些特点才能规定它叫二叉树，而不是什么三叉树或者四叉树。

对于二叉树来说，我们从名字上就能知道，这玩意一定跟二有关，两个叉，在树这种结构中，叉其实就是节点，那么二叉，说白了不说就是两个节点嘛

二叉树的每个节点的度最大为2

还记得什么是度吧，就是每个节点拥有的子树数，说白了，就是一个节点下有几个子节点，对二叉树来说，最多有俩，最多拥有两个子树，这个其实好理解，就是一个节点，最多有两个分叉，所以这里你要知道这个怎么回事

然后我们继续说二叉树的另外一个特点：左右节点是有顺序的，这个啥意思嘞，就是对于二叉树来说，它的左右节点是有序的，不同顺序就不是同一个二叉树。我们继续看上面的图，假如以E为根节点，K和L为叶子节点是一颗二叉树，那么现在K在左，L在右，但是如果换换位置，K在右，L在左的话那就成了一个新的二叉树了。

这也是二叉树的一个特点。

然后依据上面这个特点，我们自然能够知道，即时某个节点只有一个子树，那么也得区分左右，不然就是两个不同的二叉树。

二叉树的性质

接下来我们继续分析二叉树的一些性质，其实吧，关于二叉树的性质，我看其他人写的文章介绍了好几个，觉得麻烦，有些觉得没必要啊，记住主要的两个不叫ok（也许以后会打脸）

所以嘞，我这里就说两个关于二叉树的性质，我们还要借助一个二叉树的图来看：

非空二叉树的第i层，最多有2的i-1次方个节点，i是大于等于1的

咋样，对照着上面的图，自己试试看看是不是这么回事，然后还有这么一条性质：

在高度为h的二叉树上最多有2的h次方减一个节点

当然，二叉树的性质可不止这些，不过嘞，我这里也可以把他们全部补全，只要看看别人写的总结的，拿过来不就得了，但是觉得没啥意思，这里的性质先记住这两条，其实你只要熟悉二叉树长啥样，就能应付这些。

你想想，关于这块是不是会给你来个判断题，比如说：在高度为h的二叉树上最多有2的h次方减一个节点，你说对不对😂

这块先这么学就得了，毕竟下面还有几个让你糊涂的玩意嘞！

几种二叉树，容易糊涂

对于二叉树来说，它有几种特殊的形态，比如真二叉树，满二叉树和完全二叉树，这几个概念不知道大家听过没有。满二叉树的出场率应该搞一点吧，这几种二叉树可真的是会让人搞糊涂啊，特别容易张冠李戴（哈哈，突然想起来这个词）

所以嘞，接下来我绝不是简单的机械的去介绍这几种二叉树的定义，这样说了没啥意思，谁都会，网上搜搜，看看定义不就得了，也不至于在这里听我废话啊，所以，我得跟大家说说我的理解，我是怎么理解这几种二叉树的，有什么好的无别方法没有。

真二叉树

首先看看什么是真二叉树，真一般就是对应着假吧，这里说真二叉树，大致是不是在强调真的有两个叉呢？😂如果没有俩叉是不是就是假的了。

其实我们就可以这样理解，所谓的真二叉树，意思就是所有的节点的度要么是0，要么都是2，你看看，这说的不就是二叉树吗？（可不是哦）

啥是二叉树（忘了说？）

我们上面说了二叉树的特点啊，性质啊，好像还没说啥是二叉树嘞？那啥是二叉树啊？二叉树肯定是树，只不过是一种特殊的树，对于二叉树来说，它的节点最多有两个孩子节点，注意这里说的是最多有两个，那么，可能有一个，也可能一个都没有。

不行，得把重点强调一下：

对于二叉树来说，它的节点最多有两个孩子节点，注意这里说的是最多有两个，那么，可能有一个，也可能一个都没有。

然后你再看什么是真二叉树？

所有的节点的度要么是0，要么都是2

整出来区别了吧

庆哥你竟然坑人？

等等……我说的对吗？好像有问题啊，我们再来看看什么是真二叉树：

所有的节点的度要么是0，要么都是2

然后再看看图，好像没啥问题啊，好像也有问题啊，怎么回事嘞？实际上，我上面说的是错的，我们这里要注意叶子节点啊，你想想，既然是叶子节点，那它肯定没有子节点啦，所以上面那个即是二叉树，也是真二叉树，因为这货人家已经是叶子节点了

这个只能是二叉树（节点可以有一个子节点），但是却不是真二叉树了，因为真二叉树要求，除了叶子节点，要么一个叉没有（成了叶子节点），要么你就俩叉。

仔细想想明白了没有，上面故意说错，不是有意误导大家，只是为了让大家记忆的更加深刻，不知道大家体会到了我的良苦用心没😂

满二叉树

接下来我们来看看啥又是满二叉树，我们先来猜猜，这里的形容词应该是一个“满”字，那意思就是全部都是的意思吧，大概就是这样，那放到二叉树里面，是不是说这里的叉都是满的，对于二叉树来说，就是满不也就俩叉吗？

哦哦，晓得了，也就是每个节点都是俩叉（注意，凡是这样说，我们都是不把叶子节点包含在内的），但是，如果这样的话，好像就成了真二叉树了吧。

等等，这上面可都是我们猜的啊，那实际的是咋回事嘞？

满二叉树：所有节点的度要么都是0 ，要么都是2，这个其实就是真二叉树的定义，但是满二叉树多了一个条件，就是满二叉树还要求所有的叶子节点都在最后一层

你看，我们知道了什么是真二叉树之后再看这个定义，觉得没啥难理解的吧，这里相比较真二叉树来说就多了这么一个条件：

满二叉树还要求所有的叶子节点都在最后一层

这个最后一层怎么理解？这属于基础知识吧，知道怎么分层吧，再来看看

这你可得注意啦，上面图中的可不是二叉树哦，只是让你看看怎么分层的，所以这一个自然不是满二叉树

到了这里你再想我下面说的这句话对不对？

满二叉树属于真二叉树

这肯定是对的啊，因为所谓的满二叉树就是在真二叉树的基础之上增加条件而来的，要知道一旦增加条件就是把范围缩小了，那肯定属于之前没有增加条件的那个大范围之内啦。

所以还有一点，在同样高度的二叉树中，满二叉树的叶子节点和总结点树一定是最多的，满二叉树一定是真二叉树，但是反过来就不行了，真二叉树不一定是满二叉树

简单来说啊，满二叉树的每个分支都是满的，而且所有叶子节点都在同一层级，不然就是真二叉树。

完全二叉树

好了，我们继续来说说这最后的一种特殊二叉树---完全二叉树，说实在的，这三个当中就属这个完全二叉树有点难捉摸，因为它的这个概念吧说的有点神乎其神的😂

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

你看看，你看看，这说的让我不知所措啊，简单来说啊，是这样滴：

对于完全二叉树来说，叶子节点只会出现在最后2层，且最后一层的叶子节点都靠左对齐。

这里我想再说一个概念，那就是叶子节点成对出现，啥意思嘞，碎玉二叉树来说，节点的子节点最多为俩，一个节点下的两个节点可以说成是成对出现，比如这样

对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

我们先把一个满二叉树编号，顺序以根节点开始，自上而下，从左到右

然后我们再看这个二叉树编上号

然后与上面那个满二叉树做对比看看

经过了这么些分析，应该已经知道什么是完全二叉树了吧，我们看看，这些小总结：

1、完全二叉树从根节点到倒数第二层一定是一棵满二叉树

2、满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树

然后其实对于完全二叉树还有这么些个性质：

1. 度为1的节点只有左子树

2. 度为1的节点要么是1个，要么是0个

3. 同样节点数量的二叉树，安全二叉树的高度最小

三种特殊二叉树的区别于联系

首先看真二叉树和满二叉树，这个都要求每个分支节点都是满的，也就是每个节点都有两个叉，也就是左右孩子节点，当然，叶子节点除外，满足这个就是真二叉树，如果在此条件上再加上一个条件，所有叶子节点在同一层级，那就是满二叉树。

也就是说，除叶子节点，每个节点都有左右孩子节点，那就是真二叉树。
如果除此之外，所有叶子节点又都在一个层级，那就是满二叉树

对于完全二叉树，叶子节点只能在最后两层，且除了最后一层的叶子节点，其他节点都是满的，也就是如果倒数第二层也有叶子节点，那一定是左右孩子节点齐全的（成对出现），最后一层的叶子节点可以是不满的，但是只能是左孩子

好啦，这三个货，大家要好好理解理解哦！

如何存储二叉树

这相对来说是个难点，需要动脑子思考，不然不好理解

首先要知道，数据结构分为物理结构和逻辑结构，像数组这种数据结构就属于物理结构，人家是怎么样的就在内存中怎么存储，但是对于逻辑结构比如这里的二叉树，貌似就没法直接存了，不过逻辑结构的数据结构可以使用多种物理结构来存储

一般来说，就是数组和链表，这俩万能啊，很多东东的底层貌似都有这俩货。

所以对于二叉树也是一样的，可以使用链表和数组来存储。

使用链表来存储

使用链表来存储树结构数据，好像是最直观的了，看个图

回顾一下链表的知识，链表也就是一个接一个，每个链表节点包含一个data变量和一个next指针，这里对于二叉树来说，包含两个next指针，因为要指向左右孩子节点。

我们接下来再看使用数组怎么来存储二叉树

使用数组来存储

数组相对来说，就没有那么直观了，要想理解二叉树的数组的存储方式，必须先在脑海中建立这样的一个观念：

那就是，二叉树的每个节点从跟节点开始都有自己对应的编号

为啥，数组不是有下标吗？一一对应啊这是。

这个该怎么存储，看图

为啥要这样嘞，因为这样可以保持和二叉树的位置一一对应，这样我们就能按照二叉树的一些性质去定位二叉树中的某些节点了。

然后就有下面这一些公式可以方便求解二叉树的父节点和左右节点

如果一个父节点的下标是index，那么它的的左节点下标就是2index+1 右节点下标就是2index+2

反过来是一样的道理

如果一个左节点的下标是leftindex 那么它的父节点就是（leftindex-1）/2

但是这里你就会发现，对于这样的表示，如果一个二叉树，很多位置都是空的，那对应的数组位置也是空的，而数组申请内存空间，一旦申请，不会改变，那就浪费内存空间了

所以得考虑，什么样的二叉树适合用数组来存储！

好啦好啦，就说到这啦，毕竟下面还有很多嘞！

二叉树的应用

我们上面巴拉巴拉说了一大堆，那么这个二叉树到底有啥用啊，还搞的怪麻烦，在实际中，二叉树的作用主要有两部分：

1、用于查找
2、用于维持相对顺序

啥意思嘞，听我慢慢解释。

用于查找

二叉树的每个节点其实都可以看做是个索引，所以二叉树这种数据结构很适合用来查找，这里有一种特殊的二叉树结构，叫二叉查找树，主要作用就是用来进行查找的

既然是二叉树的一种特殊结构，那相对二叉树还是有些不同的地方的：

1、如果左子树不为空，那么左子树上所有节点的值均小于根节点的值
2、如果右子树不为空，那么右子树上所有节点的值均大于根节点的值
3、左右子树也都是二叉查找树

也就是规定了节点上的值，左边的都比根节点小，右边的都比根节点大，这样的话就会产生两个极值，左下角的是最小的那个，右下角是最大的那个

以此，就可以比较快速的查找一个值，可以把要查找的值与根节点的值进行比较，然后看是与左节点比较，还是与有节点比较，有一种猜数，大了还是小了的那种意思。

关于二叉查找树，我们以后会单独介绍的。

用于维持相对顺序

二叉茶查找树对节点的值有了规定，因此，节点的数据都是有顺序的，所以二叉查找树还叫做二叉排序树，这里的维持相对顺序啥意思嘞

就是如果你要新插入一个新的值的话还是要按照这个规定把新值放到合适的位置上

但是在插入的时候可能会出现的一个问题就是全部插入到左节点上了，比如根节点是10，然后插入9,8,7,6,5,4就会变成这个样子

二叉树的遍历

接下来就到了二叉树的遍历这块了，关于这块其实首要任务就是搞清楚几个比较容易混淆的遍历方式，也不是混淆，就是容易忘记😂

对于二叉树的遍历可以分为两种方式，一种是按照节点位置的关系去遍历，还有一种是按宏观角度去遍历，在宏观的……我去，还是看个图吧

前序遍历

前序遍历记住输出顺序是：根节点，左子树，右子树

按照这个顺序去遍历，这里还要理解的一点就是，比如遍历到根节点，然后去遍历根节点的左子树，当遍历完左子树以后不是马上去遍历右子树，而是看看左子树是否还有左子树，理解这个相当重要。

中序遍历

输出顺序：左子树，根节点，右子树

对于中序遍历的理解同前序遍历，另外需要补充一点，遍历是从根节点开始按照顺序遍历，看看图：

后序遍历

输出顺序是左子树、右子树、根节点。

继续看看图：

层序遍历

层序遍历听着不好理解，但是实际的输出顺序最好理解，就是按照从根节点到各个节点的层次关系一次输出，还记得之前给满二叉树编号吗？

从根节点开始，从上到下，从左到右

深度优先与广度优先

这里简单说下深度优先与广度优先，这是咋么个意思嘞？

深度优先，深度深度，就是深入的意思，类似一头扎到底的那个意思

至于广度优先嘛，广度优先讲究的是一个横切面，广度，面要广，不要一头扎到底，和深度优先正好相反！

好啦，到了这里就差不多了，理解了上面这些，出去跟面试官扯皮没问题了，但是，如果让你上手写代码，那你就挂了，别担心，后面会出一篇专门讲二叉树相关的各种代码编码的，比如各种遍历，以及存储等等！

END

Java面试题专栏