认真学习数据结构之树

树形结构是一种层级式的数据结构，由顶点（节点）和连接它们的边组成。 树类似于图，但区分树和图的重要特征是树中不存在环路。

常见的树的类型有：N元树、平衡树、二叉树、二叉搜索树、AVL树、红黑树、2-3树。还有一些特殊的比如完全二叉树、满二叉树。

每个节点有零个或多个子节点，没有父节点的节点称为根节点，每一个非根节点有且只有一个父节点。除了根节点外，每个子节点可以分为多个不相交的子树。

【1】什么是树

树可以这样定义：树是由根节点和若干颗子树构成的。

树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。

如下是总结的一些特征：

空集合也是树，称为空树。

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；

节点的度：一个节点含有的子节点的个数称为该节点的度；

树的度：一棵树中，最大的节点的度称为树的度；

叶节点或终端节点：度为0的节点称为叶节点；

非终端节点或分支节点：度不为0的节点；

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

兄弟节点：具有相同父节点的节点互称为兄弟节点；

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；

堂兄弟节点：双亲在同一层的节点互为堂兄弟；

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

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

森林：由棵互不相交的树的集合称为森林。

如下图所示，该树的高度为4，树的度为2

【2】树的种类

① 无序树&有序树

树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树。

树中任意节点的子结点之间有顺序关系，这种树称为有序树。

一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的。如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序。而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的

② 二叉树

二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

二叉树的性质

性质1：二叉树的第i层上至多有2^(i-1)（i≥1）个节点 。

性质2：深度为h的二叉树中至多含有2^h-1个节点 。

性质3：若在任意一棵二叉树中，有n个叶子节点，有m个度为2的节点，则必有n=m+1 。

性质4：具有n个节点的满二叉树深为log2n+1。

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点 。

当i>1时，该节点的双亲节点的编号为i/2 。

若2i≤n，则有编号为2i的左节点，否则没有左节点 。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点 。

满二叉树

如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树 。

完全二叉树

深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树 。

完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1 。

③ 二叉查找树（BST:Binary Search Tree）

又名二叉搜索树，二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：

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

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

左、右子树也分别为二叉排序树；

没有键值相等的节点（因此，插入的时候一定是叶子节点）。

也就是二叉查找树是对左右子树结点值大小做了限制。

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势。所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

存在的问题

它有一个问题，就是容易偏向某一侧，这样就像一个链表结构了，失去了树结构的优点，查找时间会变坏，从O(logN)退化为O(N)。

④ 平衡树(Balance Tree，BT)

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1。

常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。

平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。

⑤ AVL树

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

AVL树本质上还是一棵二叉搜索树，它的特点是：

• 本身首先是一棵二叉搜索树。
• 带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）故而又称二叉平衡搜索树。

AVL树好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

⑥ 2-3树

2-3树是在原来AVL树的基础上提出一种新的树结构，我们都知道二叉搜索树可以加速查询操作，而AVL树在二叉搜索树的基础上限制了高度差（树高 <= 1），从而使得AVL高度平衡。

但是根据前面所介绍，AVL树在插入、删除操作方面会引起结构的变化，从而导致结构的多次调整（左旋右旋）。那有没有绝对平衡的一种树呢？没有高度差也不会有平衡因子，没有平衡因子就不会调整旋转操作。2-3树正是一种绝对平衡的树，任意结点到它所有的叶子结点的深度都是相等的。

2-3树不是二叉树，其节点可拥有3个孩子，2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶节点都在同一层上。不过，2-3树与满二叉树相似。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。

2-3树是一种绝对平衡的树，任意节点到它所有的叶子节点的深度都是相等的。

一颗2-3树或为一颗空树，或有以下节点组成：

2-节点，含有一个元素和两个子树（左右子树），左子树所有元素的值均小于它父节点，右子树所有元素的值均大于它父节点；

3-节点，还有两个元素和三个子树（左中右子树），左子树所有元素的值均小于它父节点，中子树所有元素的值都位于父节点两个元素之间，右子树所有元素的值均大于它父节点；

子树也是空树、2-节点或者3-节点；

没有元素相等的节点。

所有叶节点都在同一层

⑦ 哈夫曼树（最优二叉树）

带权路径最短的二叉树称为哈夫曼树或最优二叉树。

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明哈夫曼树的WPL是最小的。

⑧ 红黑树

与AVL一样，红黑树（Red Black Tree） 是一种自平衡二叉查找树。

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。

需要说明的是红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。

红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。 在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

结点是红色或黑色。

根结点是黑色。

所有叶子都是黑色。（叶子是NIL结点）

每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。

因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

因为红黑树是一种特化的二叉查找树，所以红黑树上的只读操作与普通二叉查找树相同。

【3】树的遍历

遍历表达法有4种方法：先序遍历、中序遍历、后序遍历、层次遍历。

例如下图(-父节点是叶子的根)：

• 其先序遍历（又称先根遍历）为ABDECF（根-左-右）
• 其中序遍历（又称中根遍历）为DBEAFC（左-根-右）（仅二叉树有中序遍历）
• 其后序遍历（又称后根遍历）为DEBFCA（左-右-根）
• 其层次遍历为ABCDEF（同广度优先搜索）