接下来，我们将介绍另一个数据结构——树。 二叉树是树这一数据结构的一员。 接下来还介绍红黑树、2-3-4树等数据结构。 那为什么要用树呢？ 有什么优点？
虽然前面介绍了数组的数据结构，但是我们知道有序数组的检索很快，可以用二分法检索。 但是，要在有序数组中插入数据项，必须首先找到要插入数据项的位置，然后将所有插入位置后面的数据项向后移动一位，以便为新数据留出空间。 平均而言，移动N/2次需要时间。 同样，也可以删除数据。
然后介绍了另一个数据结构——链表。 因为链表插入和删除很快，所以只需要更改一些引用值，但查找数据会很慢。 这是因为无论搜索哪个数据，都必须遍历链表中的第一个数据项，直到找到所需的数据项。 此搜索也需要平均比较N/2次。
那么，希望同时具备数组检索快的优点和链表插入和删除快的优点的数据结构，树应运而生。
1、树
树是抽象数据类型(ADT )，模拟具有树结构性质的数据集合。 这是n(n0 )个有限节点通过连接它们的边缘构成具有层次关系的集合。 之所以把它叫做“树”，是因为它看起来像倒挂着的树。 也就是说，是因为根朝上，叶朝下。
、节点：上图中的圆圈，如a、b、c等表示节点。 节点通常表示几个实体，而在java面向对象的编程中，节点通常表示对象。
、边：连接节点的线称为边，边表示节点的关联关系。 通常，从一个节点到另一个节点的唯一方法是沿着有边的路前进。 在Java中通常表示引用。
树有很多种类。 上面的一个节点有额外的两个子节点的树称为多重树。 下面将介绍2-3-4树和外部存储器是多重树的示例。 每个节点最多只能有两个子节点的一种形式称为二叉树，这也是本博客介绍的重点。
树的一般术语
、路径：沿节点边在节点之间移动，经过的节点顺序称为“路径”。
、根：树梢节点称为根。 一棵树只有一根根。 要把一个节点和边的集合称为树，它必须存在于距离根的任何其他节点上，并且只有一条路径。 a是根节点。
)、父节点)当一个节点包含子节点时，将该节点称为该子节点的父节点； b是d的父节点。
、子节点(一个节点中包含的子树的根节点称为该节点的子节点； d是b的子节点。
、兄弟节点：具有相同父节点的节点相互称为兄弟节点； 例如，上图中的d和e相互称为兄弟节点。
、叶节点：无子节点的节点称为叶节点，也称为叶节点。 例如，上图中的a、e、f、g都是叶节点。
、子树：每个节点都可以是子树的根，其所有子节点、子节点的子节点等都包含在子树中。
、节点层次：从根开始定义，根为第一层，根的子节点为第二层。
、深度：对于任意节点n，n深度为根到n的唯一路径长度，根深度为0；
、高度：对于任意节点n，n的高度为n到一片树叶的最长路径长度，所有树叶的高度为0；
2、二叉树
二叉树：树的每个节点最多只有两个子节点
上图第一个图b的节点有DEF的三个子节点，称为多重树，而不是二叉树； 另一方面，第二张图中的每个节点最多只有两个节点。 是二叉树。 二叉树的子节点被称为“左子节点”和“右子节点”。 上图中的d、e分别是b的左子节点和右子节点。
给二叉树附加额外条件，可以得到一种特殊的二叉树，称为二叉树。
三叉搜索树如果左侧子树不空，则要求左侧子树的所有节点的值小于根节点的值； 在其右侧子树不为空的情况下，右侧子树的所有节点的值大于根节点的值； 其左、右子树也分别是两股排序树。
二叉搜索树作为数据结构，是如何工作的呢？ 以下内容介绍了查找节点、插入新节点、删除节点、遍历树等如何高效工作。
二叉树节点类：
二叉树的具体方法：
3、查找节点
要查找节点，必须从根节点遍历。
、搜索值大于当前节点值时，搜索右子树；
、搜索值与当前节点值相等，停止搜索(结束条件)；
、搜索值小于当前节点值时，搜索左子树；
用变量current保存当前搜索的节点。 参数key是要搜索的值，第一次搜索将根节点分配给当前节点。 在while循环中，将要搜索的值与当前保存的节点进行比较。 如果key小于当前节点，则搜索当前节点的左侧子节点；如果key大于当前节点，则搜索右侧子节点；如果key等于当前节点，则直接返回节点信息。 如果整个树的遍历是完整的，即current==null，则找不到查找值并返回null。
树的效率：寻找节点的时间取决于该节点所在的层数，每层最多有2n-1个节点，共n层有2n-1个节点时，时间复杂度为o(logn )，底数为2。
4、插入节点
要插入节点，必须首先找到要插入的位置。 与检索操作一样，由于两股检索树的特殊性，也需要插入的节点
从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置。5、遍历树
遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最常用的是中序遍历。
①、中序遍历:左子树——》根节点——》右子树
②、前序遍历:根节点——》左子树——》右子树
③、后序遍历:左子树——》右子树——》根节点
6、查找最大值和最小值
这没什么好说的，要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。
7、删除节点
删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。
1、该节点是叶节点(没有子节点)
2、该节点有一个子节点
3、该节点有两个子节点
下面我们分别对这三种情况进行讲解。
①、删除没有子节点的节点
要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。要删除的节点依然存在，但是它已经不是树的一部分了，由于Java语言的垃圾回收机制，我们不需要非得把节点本身删掉，一旦Java意识到程序不在与该节点有关联，就会自动把它清理出存储器。
删除节点，我们要先找到该节点，并记录该节点的父节点。在检查该节点是否有子节点。如果没有子节点，接着检查其是否是根节点，如果是根节点，只需要将其设置为null即可。如果不是根节点，是叶节点，那么断开父节点和其的关系即可。
②、删除有一个子节点的节点
删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。
③、删除有两个子节点的节点
当删除的节点存在两个子节点，那么删除之后，两个子节点的位置我们就没办法处理了。既然处理不了，我们就想到一种办法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？
我们知道二叉搜索树中的节点是按照关键字来进行排列的，某个节点的关键字次高节点是它的中序遍历后继节点。用后继节点来代替删除的节点，显然该二叉搜索树还是有序的。(这里用后继节点代替，如果该后继节点自己也有子节点，我们后面讨论。)
那么如何找到删除节点的中序后继节点呢？其实我们稍微分析，这实际上就是要找比删除节点关键值大的节点集合中最小的一个节点，只有这样代替删除节点后才能满足二叉搜索树的特性。
后继节点也就是：比删除节点大的最小节点。
算法：程序找到删除节点的右节点，(注意这里前提是删除节点存在左右两个子节点，如果不存在则是删除情况的前面两种)，然后转到该右节点的左子节点，依次顺着左子节点找下去，最后一个左子节点即是后继节点；如果该右节点没有左子节点，那么该右节点便是后继节点。
需要确定后继节点没有子节点，如果后继节点存在子节点，那么又要分情况讨论了。
①、后继节点是删除节点的右子节点
这种情况简单，只需要将后继节点表示的子树移到被删除节点的位置即可！
②、后继节点是删除节点的右子节点的左子节点
④、删除有必要吗？
通过上面的删除分类讨论，我们发现删除其实是挺复杂的，那么其实我们可以不用真正的删除该节点，只需要在Node类中增加一个标识字段isDelete，当该字段为true时，表示该节点已经删除，反正没有删除。那么我们在做比如find()等操作的时候，要先判断isDelete字段是否为true。这样删除的节点并不会改变树的结构。
8、二叉树的效率
从前面的大部分对树的操作来看，都需要从根节点到下一层一层的查找。
一颗满树，每层节点数大概为2n-1，那么最底层的节点个数比树的其它节点数多1，因此，查找、插入或删除节点的操作大约有一半都需要找到底层的节点，另外四分之一的节点在倒数第二层，依次类推。
总共N层共有2n-1个节点，那么时间复杂度为O(logn),底数为2。
在有1000000 个数据项的无序数组和链表中，查找数据项平均会比较500000 次，但是在有1000000个节点的二叉树中，只需要20次或更少的比较即可。
有序数组可以很快的找到数据项，但是插入数据项的平均需要移动 500000 次数据项，在 1000000 个节点的二叉树中插入数据项需要20次或更少比较，在加上很短的时间来连接数据项。
同样，从 1000000 个数据项的数组中删除一个数据项平均需要移动 500000 个数据项，而在 1000000 个节点的二叉树中删除节点只需要20次或更少的次数来找到他，然后在花一点时间来找到它的后继节点，一点时间来断开节点以及连接后继节点。
所以，树对所有常用数据结构的操作都有很高的效率。
遍历可能不如其他操作快，但是在大型数据库中，遍历是很少使用的操作，它更常用于程序中的辅助算法来解析算术或其它表达式。
9、用数组表示树
用数组表示树，那么节点是存在数组中的，节点在数组中的位置对应于它在树中的位置。下标为 0 的节点是根，下标为 1 的节点是根的左子节点，以此类推，按照从左到右的顺序存储树的每一层。
树中的每个位置，无论是否存在节点，都对应于数组中的一个位置，树中没有节点的在数组中用0或者null表示。
假设节点的索引值为index，那么节点的左子节点是 2*index+1，节点的右子节点是 2*index+2，它的父节点是 (index-1)/2。
在大多数情况下，使用数组表示树效率是很低的，不满的节点和删除掉的节点都会在数组中留下洞，浪费存储空间。更坏的是，删除节点如果要移动子树的话，子树中的每个节点都要移到数组中新的位置，这是很费时的。
不过如果不允许删除操作，数组表示可能会很有用，尤其是因为某种原因要动态的为每个字节分配空间非常耗时。
10、完整的BinaryTree代码
Node.java
Tree.java
BinaryTree.java
11、ssdjr(Huffman)编码
我们知道计算机里每个字符在没有压缩的文本文件中由一个字节(比如ASCII码)或两个字节(比如Unicode,这个编码在各种语言中通用)表示，在这些方案中，每个字符需要相同的位数。
有很多压缩数据的方法，就是减少表示最常用字符的位数量，比如英语中，E是最常用的字母，我们可以只用两位01来表示，2位有四种组合：00、01、10、11，那么我们可以用这四种组合表示四种常用的字符吗？
答案是不可以的，因为在编码序列中是没有空格或其他特殊字符存在的，全都是有0和1构成的序列，比如E用01来表示，X用01011000表示，那么在解码的时候就弄不清楚01是表示E还是表示X的起始部分，所以在编码的时候就定下了一个规则：每个代码都不能是其它代码的前缀。
①、ssdjr编码
二叉树中有一种特别的树——ssdjr树(最优二叉树)，其通过某种规则(权值)来构造出一ssdjr二叉树，在这个二叉树中，只有叶子节点才是有效的数据节点(很重要)，其他的非叶子节点是为了构造出ssdjr而引入的！
ssdjr编码是一个通过ssdjr树进行的一种编码，一般情况下，以字符：‘0’与‘1’表示。编码的实现过程很简单，只要实现ssdjr树，通过遍历ssdjr树，规定向左子树遍历一个节点编码为“0”，向右遍历一个节点编码为“1”，结束条件就是遍历到叶子节点！因为上面说过：ssdjr树叶子节点才是有效数据节点！
我们用01表示S，用00表示空格后，就不能用01和11表示某个字符了，因为它们是其它字符的前缀。在看三位的组合，分别有000,001,010,100,101,110和111，A是010，I是110，为什么没有其它三位的组合了呢？因为已知是不能用01和11开始的组合了，那么就减少了四种选择，同时011用于U和换行符的开始，111用于E和Y的开始，这样就只剩下2个三位的组合了，同理可以理解为什么只有三个四位的代码可用。
所以对于消息：SUSIE SAYS IT IS EASY
ssdjr编码为：100111110110111100100101110100011001100011010001111010101110
②、ssdjr解码
如果收到上面的一串ssdjr编码，怎么解码呢？消息中出现的字符在ssdjr树中是叶节点，也就是没有子节点，如下图：它们在消息中出现的频率越高，在树中的位置就越高，每个圆圈外面的数字就是频率，非叶节点外面的数字是它子节点数字的和。
每个字符都从根开始，如果遇到0，就向左走到下一个节点，如果遇到1，就向右。比如字符A是010，那么先向左，再向右，再向左，就找到了A，其它的依次类推。
12、总结
树是由边和节点构成，根节点是树最顶端的节点，它没有父节点；二叉树中，最多有两个子节点；某个节点的左子树每个节点都比该节点的关键字值小，右子树的每个节点都比该节点的关键字值大，那么这种树称为二叉搜索树，其查找、插入、删除的时间复杂度都为logN；可以通过前序遍历、中序遍历、后序遍历来遍历树，前序是根节点-hldyj，中序是左子树-根节点-右子树，后序是hldyj-根节点；删除一个节点只需要断开指向它的引用即可；ssdjr树是二叉树，用于数据压缩算法，最经常出现的字符编码位数最少，很少出现的字符编码位数多一些。