##1.树

  • 树(Tree)的定义:n(n~0)个结点的有限集,n=0时称为空树
  • 结点的度:结点拥有的子树数称为结点的度 (Degree)
  • 树的度:是树内各结点的度的最大值
  • 树的深度:树中结点的最大层次称为树的深度(Depth)或高度

2.二叉树

  • 二叉树(Binary Tree):由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成,空树也是空二叉树
  • 左斜树:所有的结点都只有左子树的二叉树叫左斜树
  • 右斜树:所有结点都是只有右子树的二叉树叫右斜树
  • 满二叉树:在一棵二叉树中,所有分支结点都存在左子树和右子树,并且所有叶子都在同一层
    • 叶子只能出现在最下一层,出现在其他层就不可能达成平衡
    • 非叶子结点的度一定是2
    • 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多
  • 完全二叉树:在一棵二叉树中,所有叶子节点都在最后一层或倒数第二层,且最后一层的叶子节点在左边连续,倒数第二层的结点在右边连续,(连续不是数值上的连续,而是从左到右(从右到左)不间断有结点出现。
    • 叶子结点只能出现在最下两层
    • 如果结点度为1 ,则该结点只有左孩子,即不存在只有右子树的情况
    • 同样结点数的二叉树,完全二叉树的深度最小
  • 满二叉树一定是完全二叉树,但是完全二叉树不是满二叉树

2.1二叉树的特点

  • 每个结点最多有两棵子树(没有子树或者有一棵子树都是可以的),所以二叉树中不存在度大于2的结点
  • 左子树和右子树是有顺序的,次序不能任意颠倒(一般左边小,右边大)
  • 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树(尤其在斜数中)

2.2 二叉树的性质

  • 性质1:在二叉树的第i层上至多有$2^{i-1}$ (i>=1)个结点
  • 性质2:深度为k的二叉树至多有$2^k-1$ (k>=1)个结点
  • 性质3: 对任何一棵二叉树T,如果其终端结点数为$n_0$,度为2的结点数为$n_2$,则$n_0 = n_2 + 1$
  • 性质4: 具有n个结点的完全二叉树的深度为$[log_2 n+1]$([x]表示不大于x的最大整数)
  • 性质5: 如果对一棵有n个结点的完全二叉树(其深度为$[log_2 n+1]$)的结点按层序编号(从第1层到第$[log_2 n+1]$+1层,每层从左到右),对任一结点i(1<=i<=n)有:
    • 如果i=1,则结点i是二叉树的根,无双亲; 如果i>1,则其双亲是结点[i/2]
    • 如果2i>=n,则结点i无左孩子(结点i为叶子结点) ;否则其左孩子是结点2i
    • 如果2i+1>=n,则结点i无右孩子;否则其右孩子是结点2i+1

2.3 二叉树的遍历

若二叉树为空,则空操作返回。

  • 前序遍历:先输出当前结点(根节点),然后递归遍历左子树、右子树。顺序是ABDGHCEIF

  • 中序遍历:先递归遍历左子树,然后输出当前结点(根节点),最后递归遍历右子树,顺序是GDHBAEICF

  • 后序遍历:先递归遍历左子树,然后递归遍历右子树,最后输出当前结点(根节点)。顺序是GHDBIEFCA

  • 层序遍历:从树的第一层(根结点)开始访问,从上而下逐层遍历,在同一层中按从左到右的顺序对结点逐个访问,顺序是ABCDEFGHI

PS:前三种遍历方式的不同就在于啥时候输出当前节点而已。

3.线索二叉树

  • 线索二叉树是对上述所讲二叉树的一种改进,改进的地方在于每个节点的指针域。上述二叉树有很多节点的指针域并没有充分利用,而线索二叉树将这些没有被利用的指针域,指向该节点的前驱和后继节点(遍历时的顺序),这种指向前驱和后继的指针称为线索,相应的二叉树就称为线索二叉树(Threaded Binary Tree)
  • 线索化是对二叉树以某种次序遍历使其变为线索二叉树的过程。实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该叉树时才能得到,所以线索化的过程就是在遍历的过程中修改空指针的过程

上图是二叉树线索化的结果,每个节点的结构如下:

  • data:数据域
  • lchild:左指针,当ltag为0时指向左孩子节点,当ltag为1时指向自己的前驱结点
  • rchild:右指针,当rtag为0时指向右孩子节点,当rtag为1时指向自己的后继结点

PS:如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继,那么采用线索二叉链表的存储结构就是非常不错的选择。

3.赫夫曼树

赫夫曼树是带权路径长度(WPL)最小的二叉树,也叫做最优二叉树。

  • 路径长度:从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称做路径长度
  • 树的路径长度:从树根到每一结点的路径长度之和
  • 带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积之和;
  • 树的带权路径长度:树中所有叶子结点的带权路径长度之和

比如下面两个二叉树,分支上的数值代表该节点的权值:

  • 二叉树a:WPL=5X1+15X2+40X3+30X4+10X4=315
  • 二叉树b:WPL=5X3+15X3+40X2+30X2+10X2=220

由此我们可以看出二叉树b的WPL最小,它是赫夫曼树。

###3.1赫夫曼树的构建

  1. 将有权值的叶子结点按照权值大小,从小到大排成有序数列。
  2. 取头两个最小权值的节点构成一颗新的二叉树,左边节点权值大于右边,该二叉树的根节点的权值是左右子结点权值之和
  3. 从序列中删除刚取出的两个结点,然后将新构建的二叉树的根节点插入有序数列,同样要保持从小到大的顺序。
  4. 重复1-3步,直到有序数列中只有一个节点,该节点就是构建成的赫夫曼树的根节点

3.2赫夫曼树的应用

最主要的应用就是赫夫曼编码,该编码可以起到无损压缩数据的作用。

假如有一串数据需要发送:“BADCADFEED”,如果用二进制对该数据进行编码的话,按照ASCII码表,最终的编码是:001000011010000011101100100011,那么对方接收到该编码后的数据后可以使用3位一分来进行译码。但是如果数据量很大,这样编码解码起来就会非常浪费时间空间。

假如我们传送的数据中,有很多重复的数据,比如每个字母出现的频率是:A 27,B 8,C 15,D 15,E 30,F 5。那么把每一个字母当做节点,把相应的频率当做权值,那么按照前述方法构建这样一颗赫夫曼树:

左图是最初构建后的状态,如果我们把每个节点的左子树权值设为0,右子数权值设为1,那么可以得到右图改进版的赫夫曼树。然后我们就可以得到一份赫夫曼编码表,按照这份编码表对内容进行编码时就起到了无损压缩的作用:

PS:赫夫曼编码是一种前缀编码,也就是每一个元素的编码,都不是另一个元素编码的前缀,这样在解码的时候就不会出现错误。

4.二叉查找(排序)树

###4.1 概念介绍

在数据结构中,用于存储数据的结构主要是有数组、链表。但是这二者都各有利弊

对于数组而言:

  • 数组(无需排序):添加快,查找慢
  • 数组(需要排序):查找可用二分查找算法,提高速度;但是为了保证数组的有序,添加元素时需要挪动其他元素的位置,拖慢速度。

对于链表来说,无论是否需要保持顺序,查找起来都很慢,但是添加数据比数组快,因为无需挪动元素,只需要添加指向就可以了。

除了这两种存储结构之外,有没有一种查找快,插入也快的结构呢?有的,那就是二叉排序树(Binary Sort Tree)。对于二叉排序树的任何一个非叶子结点来说,其左子节点要比当前节点小,右子结点要比当前结点大。如果有相同值的节点要插入,那么放在当前结点的左右都可。如下图是一颗BST:

4.2 二叉排序树的结点删除

情况一:删除叶子节点(如2,5,9,12)

  • 找到要删除的节点
  • 找到要删除节点的父结点
  • 判断要删除节点属于父结点的左子节点还是右子结点
  • 根据上一步,将父结点的左(右)子结点置空

情况二:删除只有一个子结点的结点(如1,3)

  • 找到要删除的节点
  • 找到要删除节点的父结点
  • 判断当前节点是有左子节点还是有右子结点
  • 判断当前节点属于父结点的左子节点还是右子结点
  • 根据2、3步,将父结点的左(右)子结点设置为当前节点的左(右)子结点

情况三:删除有两个子结点的结点(如7,3,10)

  • 找到要删除的节点
  • 找到要删除节点的父结点
  • 找到该节点右子树中最小的结点的值,用一个临时变量保存起来(如删除节点10,那么右子树最小节点的值就是12)
  • 删除最小节点
  • 将要删除节点的值设置为临时变量的值

注意事项:在情况二中,有一个特殊情况,也就是一种特殊的二叉树,该二叉树只有两个结点,一个根节点还有一个左(右)子结点。在这种情况下我们删除根节点的时候,需要进行判断。因为此时的根节点,也就是我们要删除的只有一个节点的目标节点,它是没有父结点的,按照之前的步骤,程序会爆出空指针异常,因此在这一步我们需要加一个判断,如果目标节点没有父结点,那么直接将根节点设置为目标节点的左(右)子结点就可以了。

5.平衡二叉树

###5.1概念介绍

上一节将的二叉查找树虽然即可以快速插入,又可以快速查找,但仍有一中情况会减慢操作速度。也就是该二叉树不平衡的时候,什么叫不平衡呢?我们看下图:

以上是三个二叉树,我们以根节点为出发点,看一下这三个二叉树的平衡情况:

  • 左:该根节点左子树的深度是2,右子树深度是1,高度差为1
  • 中:该根节点左子树的深度是2,右子树深度是2,高度差为0
  • 右:该根节点左子树的深度是3,右子树深度是1,高度差为2

我们把左右两颗子树的高度差的绝对值不超过1的二叉树称为平衡二叉树(Balance Binary Tree),又叫做AVL树。毫无疑问,上面三个树中第三个不是平衡二叉树。

平衡二叉树的左右两个子树也都是一颗平衡二叉树,要想使一个二叉树达到平衡,常用的方法有红黑树、AVL、替罪羊树、Treap、伸展树。

###5.2 左旋转

当右子树的高度高于(差值大于1)左子树的高度时,我们可以用左旋转的操作让该不平衡二叉树变得平衡。如下是一个待改善的不AVL:

我们依次进行下列操作:

  • 创建一个新的结点,将此新结点的值设置为根节点的值
  • 把新结点的左子树设置为根节点的左子树
  • 把新结点的右子树设置为根节点的右子树的左子树
  • 把根节点的值设置为根节点的右子树的值
  • 把根节点的右子树设置为右子树的右子树
  • 把根节点的左子树设置为新结点

可得到平衡二叉树,相当于架空了根节点的右子结点

5.3 右旋转

当左子树的高度高于(差值大于1)右子树的高度时,我们可以用右旋转的操作让该不平衡二叉树变得平衡。如下是一个待改善的不AVL:

我们依次进行下列操作:

  • 创建一个新的结点,将此新结点的值设置为根节点的值
  • 把新结点的右子树设置为根节点的右子树
  • 把新结点的左子树设置为根节点的左子树的右子树
  • 把根节点的值设置为根节点的左子树的值
  • 把根节点的左子树设置为左子树的左子树
  • 把根节点的右子树设置为新结点

可得到平衡二叉树,相当于架空了根节点的左子结点

5.4 双旋转

从根节点出发,如果根节点的左子树的右子树的高度大于左子树的高度,比如下面这棵树,节点7是根节点的根节点的左子树,但是该节点的右节点的高度大于左节点的高度,对这样的一棵树,仅仅针对根节点进行左旋转或右旋转是不够的,我们应该先对节点7进行左旋转,再对根节点10进行右旋转,才能达到平衡的效果。

只针对根节点进行右旋转的效果:

6.多叉树

###6.1 概念介绍

二叉树的操作效率确实比较高,但也是在一定数据量的前提之前,如果数据足够多,也就意味着有更多的节点,从而引发出如下的问题:

  • 构建二叉树需要多次进行i/o操作,由于结点数量多,所以速度会有所影响
  • 节点多会导致二叉树的高度很大,从而影响操作速度。

怎样解决呢?那就是使用多叉树。

多叉树(Multiway Tree)允许每个节点有多个数据项和更多的子结点,它通过重新组织节点,减少树的高度,能对二叉树进行优化。比如2-3树、2-3-4树。

6.2 B树

2-3树是最简单的B树结构,其结构如下图所示,

2-3树的特点有:

  • 所有节点都在同一层,这也是所有B树的的特点
  • 有两个子结点的节点叫做二节点,二节点要么没有子结点,要么有两个子结点
  • 有三个子结点的节点叫做三节点,三节点要么没有子结点,要么有三个子结点
  • 2-3树是由二节点和三节点组成的树

MySQL的某种索引就是基于B树或者B+树的,B树的结构形如下图

B树的特点:

  • B树的阶:节点的最多子结点的个数,比如2-3树的阶是3,2-3-4树的阶是4
  • B树的所有节点(叶子节点和非叶子节点)都存放可被检索的数据(这是和B+树的最重要区别)
  • 搜索可在非叶子节点结束
  • 搜索的性能等价于在关键字全集中做二分查找

6.3 B+树

B+树的结构形如下图:

它与B树的区别如下:

  • 数据项都存放在叶子节点(稠密索引),非叶子节点只是索引(稀疏索引)
  • 更适合文件系统的索引
  • 性能也等于在关键字集中做二分查找

###6.4 B*树

B*树和B+树之间的区别在于,B*树的兄弟索引之间有指向。

它的特点有:

  • B*树分配新结点的概率比B+树要低,空间使用率高

参考资料

  • 《大话数据结构》
  • 尚硅谷-韩顺平图解Java数据结构和算法