数据结构总结之tree

最近要准备面试，复习和准备一下数据结构的相关知识，这里总结树的相关知识。

大二学数据结构的时候，我就很不喜欢某些书中对一些数据结构的描述，比如说栈的特点是先进后出，这听上去很对，其实一点用没有。

我就比较喜欢这样的描述，栈的作用是保存状态，队列的作用是做缓存，而树呢，其展开的特性，就是为了查找。

不仅仅是结构

在c中我们可能用结构体来定义一棵树，而在c++，java这样的面向对象语言中，我们可能用类来表示一棵树，但是我在这一节来解释一下，我们的思维一定要开阔，我的意思是说，不仅仅是我们定义了一棵树，才会有一棵树。

比如看下面的二分查找的递归实现：

int BSearch(elemtype a[],elemtype x,int low,int high)
/*在下届为low，上界为high的数组a中折半查找数据元素x*/
{
    int mid;

    if(low>high) return -1;

    mid=(low+high)/2;

    if(x==a[mid]) return mid;

    if(x<a[mid]) return(BSearch(a,x,low,mid-1));

    else return(BSearch(a,x,mid+1,high));
}

我们没有定义一棵树吧？但是这个递归调用，在栈中自己生长出来一棵树，然后把它释放了。

常见的树的种类

这里总结常见的树形结构，以下是一些定义。

二叉树：每个节点最多含有两个子树的树称为二叉树。

完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。

满二叉树：对于上述的完全二叉树，如果去掉其第d层的所有节点，那么剩下的部分就构成一个满二叉树（此时该满二叉树的深度为d-1）。

树的三种表示法：双亲表示法，孩子表示法，孩子兄弟表示法。

这里主要总结讨论下二叉树的表示法，因为二叉树是比较常用的。

二叉树的存储一般分两种：顺序存储和二叉链表。

对于完全二叉树，用顺序存储是非常方便的。非完全二叉树可能会浪费大量空间。

而二叉链表，又是前序遍历，中序遍历，后序遍历，和其它二叉树算法常用的数据结构表示，因为它是一种递归表示法。

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

堆

堆（也叫优先队列），是一棵完全二叉树，它的特点是父节点的值大于（小于）两个子节点的值（分别称为大顶堆和小顶堆）。它常用于管理算法执行过程中的信息，应用场景包括堆排序，优先队列等。

可以看出堆在取最值时，复杂度是O(1)。还需要注意的是堆只需要满足父节点大于两个子节点，而子节点之间没有要求。

建堆(由无序序列构建一个堆)：

首先要注意，建堆的过程，主要操作对从第一个元素开始的length/2个元素，而且是反向操作，比如一个序列有7个元素，那么建堆的过程，就是这样的顺序:3，2，1。

检查这个元素是否符合堆的定义，比如大顶堆，要比左右两个孩子大，如果不符合，那就把他与比他大的孩子进行交换。需要注意的是交换之后，下面的平衡也可能被破坏，这就需要再次调整平衡。

堆排序:

如果我们在之前在线性表上建立好的堆上进行堆排序，那么就是将未排序部分的首尾元素互换，首先我们将最值放到了排序部分，其次需要调整使剩余元素变成一个新堆。

分析总结

堆排序运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。

建堆过程中的比较次数：O(n)。

堆排序的时间复杂度为O(nlogn)。

霍夫曼树

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

构造霍夫曼树：

这里有一篇文章讲解如何构造霍夫曼树:

怎么画出哈夫曼树

一定要留心这句话:如果两个数的和正好是下一步的两个最小数的其中的一个那么这个树直接往上生长就可以了。如果这两个数的和比较大不是下一步的两个最小数的其中一个那么，就并列生长。

霍夫曼编码:

霍夫曼编码的构造步骤:

1. 检查字符在数据中的出现频率。
2. 构建哈夫曼树。
3. 创建哈夫曼编码表。
4. 生成编码后结果

霍夫曼编码的优点，首先你可以想到，因为霍夫曼树的特性，所以使用越频繁的，编码长度越短，再者因为所有字符都是哈夫曼树中的叶子节点，所以每个字符所在的叶子节点的路径都不会有重叠部分，这个特征能够保证解码的唯一性，不会产生歧义（在解码时只需要找到叶子节点即可完成当前字符的解码）。

二叉查找树

其实从折半查找，就能理解，为什么树这个数据结构很适合查找。

首先最基础的是二叉查找树(二叉搜索树，二叉排序树):

它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

构造方法:

调整方法:

从结构特性上可以看出，要查找某个元素是一件非常快的事，类似于折半查找的游走选择。

但是实际情况并不如此，比如说如果如果构造出来的二叉树并不是很“匀称”，二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n),那么在查找某些元素的时候效率不会很高，这个时候就需要平衡二叉树了。

平衡二叉树（AVL树）

平衡二叉树是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

下面是平衡二叉树的几种实现

AVL

红黑树

SBT

B树们

B树作为查找树的一种和之前的查找树不同的是，它与硬件是相关的。在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块(block)中某数据时，首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构。这种结构可以使得在查找过程中，IO次数尽量的少。

B树

B树又叫平衡多路查找树,这里的多路可以理解为平衡多叉树。

首先这里有一篇很不错的文章：从B 树、B+ 树、B* 树谈到R 树

B+

B+-Tree是应文件系统所需而产生的一种B-tree的变形树。

一棵m阶的B+树和m阶的B树的差异在于：

1. 有n棵子树的结点中含有n个关键字； (而B 树是n棵子树有n-1个关键字)
2. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
3. 所有的非终端结点可以看成是索引部分 ，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

B+树比B树更适合实际应用中操作系统的文件索引和数据库索引

B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。