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

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

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

(2) 当时，其余结点可分为个互不相交的有限集，其中每一个集合本身又是一颗树，并且称为根的子树(SubTree)。

树在不同领域也有不同的定义。

1、在数学中，树是一种无向图，其中不存在环路（即无回路），且任意两个结点之间有且仅有一条简单路径相连。这种定义主要用于图论和离散数学中，用于研究树的性质和特征。

2、在操作系统中，树是一种用于表示文件系统的结构，其中根目录位于树的顶部，子目录和文件位于根目录下。这种定义主要用于操作系统设计和文件管理。

3、在数据库中，树是一种用于表示层次关系的数据结构，树结构常用于实现数据库的索引、表示层次数据关系（如组织结构、分类目录）以及优化查询操作。这种定义主要用于数据库设计和数据管理，以提高数据检索效率和结构化数据的存储。

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

二叉树的特点包括：

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

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

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

二叉树有多种类型，包括：二叉排序树、完全二叉树、满二叉树、平衡二叉树等。二叉树在计算机科学中有着广泛的应用，其简单的结构和丰富的操作使得它成为了许多其他数据结构和算法的基础。二叉树示例，如下图所示：

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

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

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

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

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

二叉排序树的特性使得在其中进行搜索、插入和删除操作时具有较高的效率。因此，二叉排序树常被用于实现集合、字典等数据结构，也用于构建符号表、数据库索引等应用。然而，需要注意的是，二叉排序树的性能取决于其树形态的平衡性，如果树的高度较大，则操作的效率可能会下降，这时可以考虑使用平衡二叉树来解决这个问题，例如AVL树、红黑树等。二叉排序树示例，如下图所示：

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

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

对于一个高度为，有个结点的二叉树，当且仅当其每个结点都与高度为的满二叉树中编号为的结点一一对应时，称为完全二叉树。完全二叉树示例，如下图所示：

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

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

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

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

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

（2）根结点是黑色；

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

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

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

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

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

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

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

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

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

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

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

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

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

B+树通常用于数据库系统和文件系统中，特别是用于实现索引结构。B+树示例，如下图所示：

对于二叉树，常用的遍历方式包括：先序遍历、中序遍历、后序遍历和层次遍历。

若二叉树为空，则什么也不做；否则，

（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树。

若二叉树为空，则什么也不做；否则，

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

若二叉树为空，则什么也不做；否则，

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

（1）首先借助一个队列，先将二叉树根结点入队，然后出队，访问出队结点；

（2） 若它有左子树，则将左子树根结点入队；

（3） 若它有右子树，则将右子树根结点入队；

（4） 然后出队，访问出队结点。如此反复，直到队列为空[1,5]。

例如：如下图所示：

其先序遍历为ABDECF（根-左-右）

其中序遍历为DBEAFC（左-根-右）（仅二叉树有中序遍历）

其后序遍历为DEBFCA（左-右-根）

其层次遍历为ABCDEF

树的遍历是指用某种方式访问树中的每个结点，且仅访问一次。主要有三种方式：

例如：如下图所示：

其先根遍历为ABEFGCDHI

其后根遍历为EFGBCHIDA

其层次遍历为ABCDEFGHI

双亲表示法采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。树的双亲表示法示例，如下图所示。

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时个结点就有个孩子链表（叶子结点的孩子链表为空表）。树的孩子表示法示例，如下图所示。

孩子兄弟表示法又称二叉树表示法，即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针，及指向结点下一个兄弟结点的指针（沿此域可以找到结点的所有兄弟结点）。优点是方便实现树转换为二叉树的操作。树的孩子兄弟表示法示例，如下图所示。