一、树

树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。把它叫做“树”是因为它常看起来像一棵倒挂的树，也就是说它常是根朝上，而叶朝下的。

1.树的定义：

树是 N(N≥ 0) 个结点的有限集。当 N=0 时，称为空树。在任意一棵树非空树中应满足：

(1) 有且仅有一个特定的称为根 (root) 的结点；

(2) 当 N > 1 时，其余结点可分为 M（M>0）个互不相交的有限集T1，T2，T3...Tm，其中每一个集合本身又是一颗树，并且称为根的子树(SubTree) 。

2.树的基本概念：

1. 结点：包含一个数据元素及若干指向其子树的分支；

2.结点的度：一个结点拥有的子树的数目；

3.叶子或终端结点：度为0的结点；

4.非终端结点或分支结点：度不为0的结点；

5.树的度：树内各结点的度的最大值；

6.孩子结点或子结点：结点的子树的根称为该结点的孩子结点或子结点；

7.双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的双亲结点或父结点；

8.兄弟结点：同一个双亲的孩子之间互称兄弟；

9.祖先结点：从根到该结点所经分支上的所有结点；

10.子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙；

11.堂兄弟结点：其双亲在同一层的结点互为堂兄弟；

12.结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第层．则其子树的根就在第层；

13.树的深度或高度：树中结点的最大层次；

14.森林：由M（M>0）棵互不相交的树的集合称为森林;

15.有序树和无序树：树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树；

16.路径和路径长度：路径是由树中的两个结点之间的结点序列构成的。而路径长度是路径上所经过的边的个数。

二、二叉树

1.二叉树定义：

二叉树 (Binary Tree)的特点是每个结点至多只有两棵子树 （即二叉树中不存在度大于2的结点），分别称为左子树和右子树。二叉树是一种递归的数据结构，可以是空树（即没有任何结点），或者是由根结点及其左右子树组成。并且，二叉树的子树有左右之分，其次序不能任意颠倒。

2.二叉树的特点：

（1）每个结点最多有两个子结点，分别称为左子结点和右子结点。

（2）左子树和右子树都是二叉树，它们本身也可以是空树。

（3）二叉树的结点结构包含一个数据元素和指向左右子树的指针。

3. 二叉树有多种类型：

     包括：二叉排序树、完全二叉树、满二叉树、平衡二叉树等。

 二叉树示例

三、二叉排序树（二叉搜索树）

1、定义：

二叉排序树(Binary Sort Tree)，也称为二叉查找树或二叉搜索树。其或者是一棵空树；或者是具有下列性质的二叉树 [5]：

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）它的左、右子树也分别为二叉排序树。

其中叶结点除外的所有结点均含有两个子树的树被称为满二叉树。除最后一层外，所有层都是满结点，且最后一层缺右边连续结点的二叉树称为完全二叉树。

二叉搜索树 

2、特点：

二叉排序树的特性使得在其中进行搜索、插入和删除操作时具有较高的效率。

四、满二叉树

1、定义：

对于一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 h  ，且结点总数是  -1 ，则它就就是满二叉树 。

 叶结点除外的所有结点均含有两个子树的树被称为满二叉树 。

2、满二叉树特点：

可以对满二叉树按层序编号：约定编号从根结点（根结点编号为1）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 i  的结点，若有双亲，则其双亲为 i/2 ，若有左孩子，则左孩子为 2i ，若有右孩子，则右孩子为 2i+1 。满二叉树示例，如下图所示：

五、完全二叉树

1、定义：

对于二叉排序树， 除最后一层外，所有层都是满结点，且最后一层缺右边连续结点的二叉树称为完全二叉树。

2、完全二叉树特点

• 如果树的深度为k ;
• 则至少有 个节点；
• 最多具有  个节点。

六、平衡二叉树

1、定义：

平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的任意结点的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

2、特点：

若将二叉树上结点的平衡因子BF(Balance Factor)定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的[1]。平衡二叉树示例，如下图所示：

 七、红黑树

1、定义

为了保持平衡二叉树（AVL树）的平衡性，插入和删除操作后，非常频繁地调整全树整体拓扑结构，代价较大。为此在AVL树的平衡标准上进一步放宽条件，引入了红黑树（Red-Black Tree）的结构 。

一棵红黑树是满足如下红黑性质的二叉排序树 ：

（1）每个结点是红色，或是黑色的；

（2）根结点是黑色；

（3）叶子结点（虚构的外部结点、NULL结点）都是黑色的；

（4）不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色的）；

（5）对每个结点、从该结点到任一叶子结点的简单路径上，所含黑结点的数量相同。

如果插入和删除操作较少，查找操作较多，采用AVL树比较合适，否则使用红黑树更为合适。但由于维护这种高度平衡所付出的代价比获得的收益大得多，因此红黑树的实际应用更广泛，C++中的map和set（Java中TreeMap和TreeSet就是用红黑树实现的 [5]）。红黑树示例，如下图所示：

八、哈夫曼树

1、定义：

哈夫曼树（Huffman Tree）是一种特殊的二叉树，用于数据压缩中的哈夫曼编码（Huffman Coding）算法。哈夫曼树的构建基于字符出现的频率，通常用于压缩数据，使得出现频率高的字符使用较短的编码，而出现频率低的字符使用较长的编码，从而达到压缩数据的目的。

2、构建哈夫曼树

构建哈夫曼树的步骤包括：

（1）统计字符频率：首先，统计待压缩的数据中每个字符出现的频率。

（2）构建哈夫曼树：根据字符频率构建一棵哈夫曼树。构建的过程是通过将出现频率最低的两个结点合并为一个新结点，新结点的频率为原结点频率之和，并将新结点插入到树中，重复这一过程直到只剩下一个根结点为止。

（3）生成编码：对于哈夫曼树中的每个字符，从根结点开始沿着路径向下，每次移动到左子结点则表示该字符编码中添加一个 0，每次移动到右子结点则表示添加一个 1，直到到达叶子结点。这样，每个字符都可以对应一个唯一的编码。

（4）数据压缩：将原始数据中的每个字符替换为对应的哈夫曼编码，从而实现数据的压缩。

哈夫曼树示例，如下图所示：

九、B树

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜素树 。B树类似于红黑树，但它们在降低磁盘 I/0操作数方面要更好一些。许多数据库系统使用B树或者B树的变种来存储信息 。

B树与红黑树的不同之处在于B树的结点可以有很多孩子，从数个到数千个，能够保持较低的高度并且保持数据的有序性，从而提高了数据的检索效率和存储效率 。

B树示例，如下图所示：

十、B+树

 1、定义

B+树是一种常见的B树变种，类似于B树，但在某些方面有所不同。例如：B+树的非叶子结点只包含键值，不存储实际数据。相比之下，B树的非叶子结点不仅包含键值，还包含对应的数据；由于B+树的叶子结点是通过指针相连的有序链表，因此范围查询的性能更好。相比之下，B树需要进行中序遍历来查找范围内的键值。

B+树通常用于数据库系统和文件系统中，特别是用于实现索引结构 。

B+树示例，如下图所示：