Java数据结构和算法（十）——二叉树
接下来咱们将会介绍另一种数据结构——树。二叉树是树这种数据结构的一员，后面咱们还会介绍红黑树，2-3-4树等数据结构。那么为何要使用树？它有什么优势？java
前面咱们介绍数组的数据结构，咱们知道对于有序数组，查找很快，并介绍能够经过二分法查找，可是想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，而后将全部插入位置后面的数据项所有向后移动一位，来给新数据腾出空间，平均来说要移动N/2次，这是很费时的。同理，删除数据也是。算法
而后咱们介绍了另一种数据结构——链表，链表的插入和删除很快，咱们只须要改变一些引用值就好了，可是查找数据却很慢了，由于无论咱们查找什么数据，都须要从链表的第一个数据项开始，遍历到找到所需数据项为止，这个查找也是平均须要比较N/2次。数据库
那么咱们就但愿一种数据结构能同时具有数组查找快的优势以及链表插入和删除快的优势，因而 树 诞生了。编程
一、树
树（tree）是一种抽象数据类型（ADT），用来模拟具备树状结构性质的数据集合。它是由n（n>0）个有限节点经过链接它们的边组成一个具备层次关系的集合。把它叫作“树”是由于它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。数组
①、节点：上图的圆圈，好比A,B,C等都是表示节点。节点通常表明一些实体，在java面向对象编程中，节点通常表明对象。数据结构
②、边：链接节点的线称为边，边表示节点的关联关系。通常从一个节点到另外一个节点的惟一方法就是沿着一条顺着有边的道路前进。在Java当中一般表示引用。ide
树有不少种，向上面的一个节点有多余两个的子节点的树，称为多路树，后面会讲解2-3-4树和外部存储都是多路树的例子。而每一个节点最多只能有两个子节点的一种形式称为二叉树，这也是本篇博客讲解的重点。post
树的经常使用术语
①、路径：顺着节点的边从一个节点走到另外一个节点，所通过的节点的顺序排列就称为“路径”。this
②、根：树顶端的节点称为根。一棵树只有一个根，若是要把一个节点和边的集合称为树，那么从根到其余任何一个节点都必须有且只有一条路径。A是根节点。编码
③、父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；B是D的父节点。
④、子节点：一个节点含有的子树的根节点称为该节点的子节点；D是B的子节点。
⑤、兄弟节点：具备相同父节点的节点互称为兄弟节点；好比上图的D和E就互称为兄弟节点。
⑥、叶节点：没有子节点的节点称为叶节点，也叫叶子节点，好比上图的H、E、F、G都是叶子节点。
⑦、子树：每一个节点均可以做为子树的根，它和它全部的子节点、子节点的子节点等都包含在子树中。
⑧、节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推。
⑨、深度：对于任意节点n,n的深度为从根到n的惟一路径长，根的深度为0；
⑩、高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，全部树叶的高度为0；
二、二叉树
二叉树：树的每一个节点最多只能有两个子节点
上图的第一幅图B节点有DEF三个子节点，就不是二叉树，称为多路树；而第二幅图每一个节点最多只有两个节点，是二叉树，而且二叉树的子节点称为“左子节点”和“右子节点”。上图的D,E分别是B的左子节点和右子节点。
若是咱们给二叉树加一个额外的条件，就能够获得一种被称做二叉搜索树(binary search tree)的特殊二叉树。
二叉搜索树要求：若它的左子树不空，则左子树上全部结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上全部结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉搜索树做为一种数据结构，那么它是如何工做的呢？它查找一个节点，插入一个新节点，以及删除一个节点，遍历树等工做效率如何，下面咱们来一一介绍。
二叉树的节点类：
package com.ys.tree;
public class Node {
private Object data; //节点数据
private Node leftChild; //左子节点的引用
private Node rightChild; //右子节点的引用
//打印节点内容
public void display(){
System.out.println(data);
}
}
二叉树的具体方法：
package com.ys.tree;
public interface Tree {
//查找节点
public Node find(Object key);
//插入新节点
public boolean insert(Object key);
//删除节点
public boolean delete(Object key);
//Other Method......
}
三、查找节点
查找某个节点，咱们必须从根节点开始遍历。
①、查找值比当前节点值大，则搜索右子树；
②、查找值等于当前节点值，中止搜索（终止条件）；
③、查找值小于当前节点值，则搜索左子树；
//查找节点
public Node find(int key) {
Node current = root;
while(current != null){
if(current.data > key){//当前值比查找值大，搜索左子树
current = current.leftChild;
}else if(current.data < key){//当前值比查找值小，搜索右子树
current = current.rightChild;
}else{
return current;
}
}
return null;//遍历完整个树没找到，返回null
}
用变量current来保存当前查找的节点，参数key是要查找的值，刚开始查找将根节点赋值到current。接在在while循环中，将要查找的值和current保存的节点进行对比。若是key小于当前节点，则搜索当前节点的左子节点，若是大于，则搜索右子节点，若是等于，则直接返回节点信息。当整个树遍历彻底，即current == null，那么说明没找到查找值，返回null。
树的效率：查找节点的时间取决于这个节点所在的层数，每一层最多有2n-1个节点，总共N层共有2n-1个节点，那么时间复杂度为O(logN),底数为2。
我看评论有对这里的时间复杂度不理解，这里解释一下，O(logN)，N表示的是二叉树节点的总数，而不是层数。
四、插入节点
要插入节点，必须先找到插入的位置。与查找操做类似，因为二叉搜索树的特殊性，待插入的节点也须要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置，在比较的过程当中要注意保存父节点的信息 及 待插入的位置是父节点的左子树仍是右子树，才能插入到正确的位置。
//插入节点
public boolean insert(int data) {
Node newNode = new Node(data);
if(root == null){//当前树为空树，没有任何节点
root = newNode;
return true;
}else{
Node current = root;
Node parentNode = null;
while(current != null){
parentNode = current;
if(current.data > data){//当前值比插入值大，搜索左子节点
current = current.leftChild;
if(current == null){//左子节点为空，直接将新值插入到该节点
parentNode.leftChild = newNode;
return true;
}
}else{
current = current.rightChild;
if(current == null){//右子节点为空，直接将新值插入到该节点
parentNode.rightChild = newNode;
return true;
}
}
}
}
return false;
}
五、遍历树
遍历树是根据一种特定的顺序访问树的每个节点。比较经常使用的有前序遍历，中序遍历和后序遍历。而二叉搜索树最经常使用的是中序遍历。
①、中序遍历:左子树——》根节点——》右子树
②、前序遍历:根节点——》左子树——》右子树
③、后序遍历:左子树——》右子树——》根节点
//中序遍历
public void infixOrder(Node current){
if(current != null){
infixOrder(current.leftChild);
System.out.print(current.data+" ");
infixOrder(current.rightChild);
}
}
//前序遍历
public void preOrder(Node current){
if(current != null){
System.out.print(current.data+" ");
preOrder(current.leftChild);
preOrder(current.rightChild);
}
}
//后序遍历
public void postOrder(Node current){
if(current != null){
postOrder(current.leftChild);
postOrder(current.rightChild);
System.out.print(current.data+" ");
}
}
六、查找最大值和最小值
这没什么好说的，要找最小值，先找根的左节点，而后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。
//找到最大值
public Node findMax(){
Node current = root;
Node maxNode = current;
while(current != null){
maxNode = current;
current = current.rightChild;
}
return maxNode;
}
//找到最小值
public Node findMin(){
Node current = root;
Node minNode = current;
while(current != null){
minNode = current;
current = current.leftChild;
}
return minNode;
}
七、删除节点
删除节点是二叉搜索树中最复杂的操做，删除的节点有三种状况，前两种比较简单，可是第三种却很复杂。
一、该节点是叶节点（没有子节点）
二、该节点有一个子节点
三、该节点有两个子节点
下面咱们分别对这三种状况进行讲解。
①、删除没有子节点的节点
要删除叶节点，只须要改变该节点的父节点引用该节点的值，即将其引用改成 null 便可。要删除的节点依然存在，可是它已经不是树的一部分了，因为Java语言的垃圾回收机制，咱们不须要非得把节点自己删掉，一旦Java意识到程序不在与该节点有关联，就会自动把它清理出存储器。
@Override
public boolean delete(int key) {
Node current = root;
Node parent = root;
boolean isLeftChild = false;
//查找删除值，找不到直接返回false
while(current.data != key){
parent = current;
if(current.data > key){
isLeftChild = true;
current = current.leftChild;
}else{
isLeftChild = false;
current = current.rightChild;
}
if(current == null){
return false;
}
}
//若是当前节点没有子节点
if(current.leftChild == null && current.rightChild == null){
if(current == root){
root = null;
}else if(isLeftChild){
parent.leftChild = null;
}else{
parent.rightChild = null;
}
return true;
}
return false;
}
删除节点，咱们要先找到该节点，并记录该节点的父节点。在检查该节点是否有子节点。若是没有子节点，接着检查其是不是根节点，若是是根节点，只须要将其设置为null便可。若是不是根节点，是叶节点，那么断开父节点和其的关系便可。
②、删除有一个子节点的节点
删除有一个子节点的节点，咱们只须要将其父节点本来指向该节点的引用，改成指向该节点的子节点便可。
//当前节点有一个子节点
if(current.leftChild == null && current.rightChild != null){
if(current == root){
root = current.rightChild;
}else if(isLeftChild){
parent.leftChild = current.rightChild;
}else{
parent.rightChild = current.rightChild;
}
return true;
}else{
//current.leftChild != null && current.rightChild == null
if(current == root){
root = current.leftChild;
}else if(isLeftChild){
parent.leftChild = current.leftChild;
}else{
parent.rightChild = current.leftChild;
}
return true;
}
③、删除有两个子节点的节点
当删除的节点存在两个子节点，那么删除以后，两个子节点的位置咱们就没办法处理了。既然处理不了，咱们就想到一种办法，用另外一个节点来代替被删除的节点，那么用哪个节点来代替呢？
咱们知道二叉搜索树中的节点是按照关键字来进行排列的，某个节点的关键字次高节点是它的中序遍历后继节点。用后继节点来代替删除的节点，显然该二叉搜索树仍是有序的。（这里用后继节点代替，若是该后继节点本身也有子节点，咱们后面讨论。）
那么如何找到删除节点的中序后继节点呢？其实咱们稍微分析，这实际上就是要找比删除节点关键值大的节点集合中最小的一个节点，只有这样代替删除节点后才能知足二叉搜索树的特性。
后继节点也就是：比删除节点大的最小节点。
算法：程序找到删除节点的右节点，(注意这里前提是删除节点存在左右两个子节点，若是不存在则是删除状况的前面两种)，而后转到该右节点的左子节点，依次顺着左子节点找下去，最后一个左子节点便是后继节点；若是该右节点没有左子节点，那么该右节点即是后继节点。
须要肯定后继节点没有子节点，若是后继节点存在子节点，那么又要分状况讨论了。
①、后继节点是删除节点的右子节点
这种状况简单，只须要将后继节点表示的子树移到被删除节点的位置便可！
②、后继节点是删除节点的右子节点的左子节点
public Node getSuccessor(Node delNode){
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while(current != null){
successorParent = successor;
successor = current;
current = current.leftChild;
}
//将后继节点替换删除节点
if(successor != delNode.rightChild){
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
④、删除有必要吗？
经过上面的删除分类讨论，咱们发现删除实际上是挺复杂的，那么其实咱们能够不用真正的删除该节点，只须要在Node类中增长一个标识字段isDelete，当该字段为true时，表示该节点已经删除，反正没有删除。那么咱们在作好比find()等操做的时候，要先判断isDelete字段是否为true。这样删除的节点并不会改变树的结构。
public class Node {
int data; //节点数据
Node leftChild; //左子节点的引用
Node rightChild; //右子节点的引用
boolean isDelete;//表示节点是否被删除
}
八、二叉树的效率
从前面的大部分对树的操做来看，都须要从根节点到下一层一层的查找。
一颗满树，每层节点数大概为2n-1，那么最底层的节点个数比树的其它节点数多1，所以，查找、插入或删除节点的操做大约有一半都须要找到底层的节点，另外四分之一的节点在倒数第二层，依次类推。
总共N层共有2n-1个节点，那么时间复杂度为O(logn),底数为2。
在有1000000 个数据项的无序数组和链表中，查找数据项平均会比较500000 次，可是在有1000000个节点的二叉树中，只须要20次或更少的比较便可。
有序数组能够很快的找到数据项，可是插入数据项的平均须要移动 500000 次数据项，在 1000000 个节点的二叉树中插入数据项须要20次或更少比较，在加上很短的时间来链接数据项。
一样，从 1000000 个数据项的数组中删除一个数据项平均须要移动 500000 个数据项，而在 1000000 个节点的二叉树中删除节点只须要20次或更少的次数来找到他，而后在花一点时间来找到它的后继节点，一点时间来断开节点以及链接后继节点。
因此，树对全部经常使用数据结构的操做都有很高的效率。
遍历可能不如其余操做快，可是在大型数据库中，遍历是不多使用的操做，它更经常使用于程序中的辅助算法来解析算术或其它表达式。
九、用数组表示树
用数组表示树，那么节点是存在数组中的，节点在数组中的位置对应于它在树中的位置。下标为 0 的节点是根，下标为 1 的节点是根的左子节点，以此类推，按照从左到右的顺序存储树的每一层。
树中的每一个位置，不管是否存在节点，都对应于数组中的一个位置，树中没有节点的在数组中用0或者null表示。
假设节点的索引值为index，那么节点的左子节点是 2*index+1，节点的右子节点是 2*index+2，它的父节点是 （index-1）/2。
在大多数状况下，使用数组表示树效率是很低的，不满的节点和删除掉的节点都会在数组中留下洞，浪费存储空间。更坏的是，删除节点若是要移动子树的话，子树中的每一个节点都要移到数组中新的位置，这是很费时的。
不过若是不容许删除操做，数组表示可能会颇有用，尤为是由于某种缘由要动态的为每一个字节分配空间很是耗时。
十、完整的BinaryTree代码
Node.java
package com.ys.tree;
public class Node {
int data; //节点数据
Node leftChild; //左子节点的引用
Node rightChild; //右子节点的引用
boolean isDelete;//表示节点是否被删除
public Node(int data){
this.data = data;
}
//打印节点内容
public void display(){
System.out.println(data);
}
}
Tree.java
package com.ys.tree;
public interface Tree {
//查找节点
public Node find(int key);
//插入新节点
public boolean insert(int data);
//中序遍历
public void infixOrder(Node current);
//前序遍历
public void preOrder(Node current);
//后序遍历
public void postOrder(Node current);
//查找最大值
public Node findMax();
//查找最小值
public Node findMin();
//删除节点
public boolean delete(int key);
//Other Method......
}
BinaryTree.java
package com.ys.tree;
public class BinaryTree implements Tree {
//表示根节点
private Node root;
//查找节点
public Node find(int key) {
Node current = root;
while(current != null){
if(current.data > key){//当前值比查找值大，搜索左子树
current = current.leftChild;
}else if(current.data < key){//当前值比查找值小，搜索右子树
current = current.rightChild;
}else{
return current;
}
}
return null;//遍历完整个树没找到，返回null
}
//插入节点
public boolean insert(int data) {
Node newNode = new Node(data);
if(root == null){//当前树为空树，没有任何节点
root = newNode;
return true;
}else{
Node current = root;
Node parentNode = null;
while(current != null){
parentNode = current;
if(current.data > data){//当前值比插入值大，搜索左子节点
current = current.leftChild;
if(current == null){//左子节点为空，直接将新值插入到该节点
parentNode.leftChild = newNode;
return true;
}
}else{
current = current.rightChild;
if(current == null){//右子节点为空，直接将新值插入到该节点
parentNode.rightChild = newNode;
return true;
}
}
}
}
return false;
}
//中序遍历
public void infixOrder(Node current){
if(current != null){
infixOrder(current.leftChild);
System.out.print(current.data+" ");
infixOrder(current.rightChild);
}
}
//前序遍历
public void preOrder(Node current){
if(current != null){
System.out.print(current.data+" ");
infixOrder(current.leftChild);
infixOrder(current.rightChild);
}
}
//后序遍历
public void postOrder(Node current){
if(current != null){
infixOrder(current.leftChild);
infixOrder(current.rightChild);
System.out.print(current.data+" ");
}
}
//找到最大值
public Node findMax(){
Node current = root;
Node maxNode = current;
while(current != null){
maxNode = current;
current = current.rightChild;
}
return maxNode;
}
//找到最小值
public Node findMin(){
Node current = root;
Node minNode = current;
while(current != null){
minNode = current;
current = current.leftChild;
}
return minNode;
}
@Override
public boolean delete(int key) {
Node current = root;
Node parent = root;
boolean isLeftChild = false;
//查找删除值，找不到直接返回false
while(current.data != key){
parent = current;
if(current.data > key){
isLeftChild = true;
current = current.leftChild;
}else{
isLeftChild = false;
current = current.rightChild;
}
if(current == null){
return false;
}
}
//若是当前节点没有子节点
if(current.leftChild == null && current.rightChild == null){
if(current == root){
root = null;
}else if(isLeftChild){
parent.leftChild = null;
}else{
parent.rightChild = null;
}
return true;
//当前节点有一个子节点，右子节点
}else if(current.leftChild == null && current.rightChild != null){
if(current == root){
root = current.rightChild;
}else if(isLeftChild){
parent.leftChild = current.rightChild;
}else{
parent.rightChild = current.rightChild;
}
return true;
//当前节点有一个子节点，左子节点
}else if(current.leftChild != null && current.rightChild == null){
if(current == root){
root = current.leftChild;
}else if(isLeftChild){
parent.leftChild = current.leftChild;
}else{
parent.rightChild = current.leftChild;
}
return true;
}else{
//当前节点存在两个子节点
Node successor = getSuccessor(current);
if(current == root){
root= successor;
}else if(isLeftChild){
parent.leftChild = successor;
}else{
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
}
return false;
}
public Node getSuccessor(Node delNode){
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while(current != null){
successorParent = successor;
successor = current;
current = current.leftChild;
}
//后继节点不是删除节点的右子节点，将后继节点替换删除节点
if(successor != delNode.rightChild){
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.insert(50);
bt.insert(20);
bt.insert(80);
bt.insert(10);
bt.insert(30);
bt.insert(60);
bt.insert(90);
bt.insert(25);
bt.insert(85);
bt.insert(100);
bt.delete(10);//删除没有子节点的节点
bt.delete(30);//删除有一个子节点的节点
bt.delete(80);//删除有两个子节点的节点
System.out.println(bt.findMax().data);
System.out.println(bt.findMin().data);
System.out.println(bt.find(100));
System.out.println(bt.find(200));
}
}
十一、哈夫曼(Huffman)编码
咱们知道计算机里每一个字符在没有压缩的文本文件中由一个字节（好比ASCII码）或两个字节（好比Unicode,这个编码在各类语言中通用）表示，在这些方案中，每一个字符须要相同的位数。
有不少压缩数据的方法，就是减小表示最经常使用字符的位数量，好比英语中，E是最经常使用的字母，咱们能够只用两位01来表示，2位有四种组合：00、0一、十、11，那么咱们能够用这四种组合表示四种经常使用的字符吗？
答案是不能够的，由于在编码序列中是没有空格或其余特殊字符存在的，全都是有0和1构成的序列，好比E用01来表示，X用01011000表示，那么在解码的时候就弄不清楚01是表示E仍是表示X的起始部分，因此在编码的时候就定下了一个规则：每一个代码都不能是其它代码的前缀。
①、哈夫曼编码
二叉树中有一种特别的树——哈夫曼树（最优二叉树），其经过某种规则（权值）来构造出一哈夫曼二叉树，在这个二叉树中，只有叶子节点才是有效的数据节点（很重要），其余的非叶子节点是为了构造出哈夫曼而引入的！
哈夫曼编码是一个经过哈夫曼树进行的一种编码，通常状况下，以字符：‘0’与‘1’表示。编码的实现过程很简单，只要实现哈夫曼树，经过遍历哈夫曼树，规定向左子树遍历一个节点编码为“0”，向右遍历一个节点编码为“1”，结束条件就是遍历到叶子节点！由于上面说过：哈夫曼树叶子节点才是有效数据节点！
咱们用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
哈夫曼编码为：100111110110111100100101110100011001100011010001111010101110
②、哈夫曼解码
若是收到上面的一串哈夫曼编码，怎么解码呢？消息中出现的字符在哈夫曼树中是叶节点，也就是没有子节点，以下图：它们在消息中出现的频率越高，在树中的位置就越高，每一个圆圈外面的数字就是频率，非叶节点外面的数字是它子节点数字的和。
每一个字符都从根开始，若是遇到0，就向左走到下一个节点，若是遇到1，就向右。好比字符A是010，那么先向左，再向右，再向左，就找到了A，其它的依次类推。
十二、总结
树是由边和节点构成，根节点是树最顶端的节点，它没有父节点；二叉树中，最多有两个子节点；某个节点的左子树每一个节点都比该节点的关键字值小，右子树的每一个节点都比该节点的关键字值大，那么这种树称为二叉搜索树，其查找、插入、删除的时间复杂度都为logN；能够经过前序遍历、中序遍历、后序遍从来遍历树，前序是根节点-左子树-右子树，中序是左子树-根节点-右子树，后序是左子树-右子树-根节点；删除一个节点只须要断开指向它的引用便可；哈夫曼树是二叉树，用于数据压缩算法，最常常出现的字符编码位数最少，不多出现的字符编码位数多一些。