【数据结构】十分钟透彻了解各种二叉树的基础概念

一.基础知识

        为什么要用二叉树？

        因为找数据更有优势。详细请参考下面第三点：排序二叉树

        树长这样：

        

         二叉树长这样，因为只有两个分叉，所以叫二叉：

        

         二叉树的左子树、右子树和根：

        

        当然左子树右子树和根是相对的：

         

        因为一个节点需要保存左子树指针、右子树指针以及自身的数据信息，所以一般会用链表的数据结构方式进行存储连接（因为是二叉树用链表，所以叫二叉链表）：

        二叉树的遍历方式有三种：前、中、后序遍历，其实理解很简单，什么序代表的是根节点在哪个顺序被访问的意思：

         举个例子，下面的二叉树使用中序遍历流程是：

        在第一步中没得遍历了，所以第一个搜出来的结果就是“1”，在第二步中，因为还有很多层，所以继续对第二步进行前序遍历：

        这次中序遍历的第一步和第二步也穷尽了，所以迭代结果为“1 2 4”，按照遍历顺序，再对右子树进行前序遍历，会得出“5 7 8”，最后回到以“1”为根节点的二叉树中的右子树继续前序遍历，游客得到“ 3 6 ”的结果，所以整个中序遍历下来会得到“1 2 4 5 7 8 3 6 ”的结果，其他遍历方法以此类推。

        遍历最常用的算法就是递归算法，要注意不要陷入死循环就是了：

        好的，现在你已经学会二叉树的遍历方法了，来做道简单的题目测试以下吧~~（奸笑.jpg）

        PS：为避免直接看到答案，答案放在最后 。

 二.满二叉树和完全二叉树

        这种就叫满二叉树（或者叫完全二叉树）：

        

         但完全二叉树并不一定结点都是满的才算完全二叉树，比如下面这个也是完全二叉树：

        

        而下面这个就算是非完全二叉树：

        

        总结以上特点可以观察到三个规律：

• 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
• 完全二叉树的排列顺序是从上到下，从左到右
• 按照其他顺序排列的都算是非完全二叉树

 三.查找二叉树（排序二叉树）

        为啥要用排序二叉树？比如一组数据{89 48 112 20 56 51}，要在数组里面找到数据{56}，需要遍历5次 ：

        但是查找二叉树呢？只需要3次：

        因为该二叉树非常适合查找数据，所以就叫查找二叉树，那为什么也叫排序二叉树呢？因为在构建排序二叉树的时候，是按照一定规律来把数据进行排序的，而不是胡乱往里面塞。排序顺序就是左子树<根节点<右子树。你会发现上面那个排序二叉树的所有的节点都符合这个规律：

        在构造二叉树的时候就已经把数据按照一定规律放进去了，等需要用到的时候再按照一定规律拿出来，会节省很多时间。

四.平衡二叉树

        后来人们发现，查找二叉树并非完美，因为排序条件太过简单，导致二叉树在进行排序的时候会出现多种答案，比如数据{1 5 7 9 8 39 73 88} ，既可以构建成这样：

         也可以构建成这样：

         显然第一种二叉树排了跟没排一样，所以为了让二叉树更加接近第二种状态，添加多个排序条件，使得二叉树看起来更加地平衡，而不是一边倒，而这个查找二叉树的升级版又叫平衡二叉树。增加的条件如下：

1. 每个结点的平衡度（左子树的深度减右子树的深度）只能是 -1、0或者 1

         啥是深度？也就是二叉树有多少层，像下面这个图中的二叉树就有四层，所以深度为4：

        而构建一个完美的查找二叉树，需要每个根节点的左右子树深度之差不超过-1、0或者1，像下面这个查找二叉树就明显超出了：

        而下面这个的平衡度就很完美了：

 五.线索二叉树

        线索二叉树其实就是多了两个箭头，这两个箭头的名称分别叫做前驱和后续，分别指向结点的前后结点的：

         比如说前序线索二叉树，根据前序遍历规则遍历出来的数据为：

        所以你就会看到 结点D 有两个箭头分别指向了 B 和 E。

        至于为什么要用线索二叉树呢？因为二叉树是非线性的结构，用线索二叉树可以把非线性的二叉树变成线性结构：

        线索二叉树多了几个指针，使得二叉树具有像数组一样的线性结构：

六.最后

        其实还有一个二叉树叫哈夫曼二叉树，但是该树要说的话需要另开一篇，详细请查看：【数据结构】哈夫曼编码与最优二叉树（哈夫曼树），下面把开头问题的答案放上：

        有题目可以知道前序遍历是根左右，中序遍历是左根右，所以前序遍历中的第一个结点A肯定就是根节点，中序遍历里面A在中间，所以就能推断A的左边全是左子树，右边全是右子树：

        得出以下结论：

         

        接着推理，前序遍历中的B在第二个，中序遍历在第二个，可以推断出来H就是B的左子树：

        以此类推，你就会慢慢推断出来整个二叉树：