二叉树详解-Java实现二叉树数据结构

树的由来

我们知道对于有序数组，查找很快，并介绍可以通过二分法查找，但是 想要在有序数组中插入一个数据项，就必须先找到插入数据项的位置，然后将所有插入位置后面的数据 项全部向后移动一位，来给新数据腾出空间，平均来讲要移动N/2次，这是很费时的。同理，删除数据 也是。
然后我们介绍了另外一种数据结构——链表，链表的插入和删除很快，我们只需要改变一些引用值 就行了，但是查找数据却很慢了，因为不管我们查找什么数据，都需要从链表的第一个数据项开始，遍 历到找到所需数据项为止，这个查找也是平均需要比较N/2次。
那么我们就希望一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点，于是 树 诞生了

二叉树

二叉树:树的每个节点最多只能有两个子节点
上图的第一幅图B节点有DEF三个子节点，就不是二叉树，称为多路树;而第二幅图每个节点最多只 有两个节点，是二叉树，并且二叉树的子节点称为“左子节点”和“右子节点”。上图的D,E分别是B的左子 节点和右子节点。
如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊 二叉树。
二叉搜索树要求:若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值; 若它的右 子树不空，则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

二叉搜索树作为一种数据结构，那么它是如何工作的呢?它查找一个节点，插入一个新节点，以及 删除一个节点，遍历树等工作效率如何，下面我们来一一介绍

二叉树的节点类:

public class Node {
private Object data; //节点数据 private Node leftChild; //左子节点的引用 			   private Node rightChild; //右子节点的引用 //打印节点内容
public void display(){
System.out.println(data); }
}

二叉树的具体方法:

public interface Tree { //查找节点
	public Node find(Object key); //插入新节点
	public boolean insert(Object key); //删除节点
    public boolean delete(Object key);
//Other Method......
}

查找节点

查找某个节点，我们必须从根节点开始遍历。
1、查找值比当前节点值大，则搜索右子树;
2、查找值等于当前节点值，停止搜索(终止条件);
3、查找值小于当前节点值，则搜索左子树;

//查找节点
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;
}

遍历树

遍历树是根据一种特定的顺序访问树的每一个节点。比较常用的有前序遍历，中序遍历和后序遍
历。而二叉搜索树最常用的是中序遍历。
1、前序遍历:根节点——>左子树——>右子树
2、中序遍历:左子树——>根节点——>右子树
3、后序遍历:左子树——>右子树——>根节点

前序：GDAFEMHZ
中序：ADEFGHMZ
后序：AEFDHZMG

//中序遍历
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;
}

删除节点

删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。
1、该节点是叶节点(没有子节点)
2、该节点有一个子节点
3、该节点有两个子节点
下面我们分别对这三种情况进行讲解。

删除没有子节点的节点

要删除叶节点，只需要改变该节点的父节点引用该节点的值，即将其引用改为 null 即可。要删除的 节点依然存在，但是它已经不是树的一部分了，由于Java语言的垃圾回收机制，我们不需要非得把节点 本身删掉，一旦Java意识到程序不在与该节点有关联，就会自动把它清理出存储器

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;
	}

删除有一个子节点的节点

删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节 点即可

//当前节点有一个子节点
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。
在大多数情况下，使用数组表示树效率是很低的，不满的节点和删除掉的节点都会在数组中留下 洞，浪费存储空间。更坏的是，删除节点如果要移动子树的话，子树中的每个节点都要移到数组中新的 位置，这是很费时的。
不过如果不允许删除操作，数组表示可能会很有用，尤其是因为某种原因要动态的为每个字节分配 空间非常耗时。

哈夫曼(Huffman)编码

我们知道计算机里每个字符在没有压缩的文本文件中由一个字节(比如ASCII码)或两个字节(比如Unicode,这个编码在各种语言中通用)表示，在这些方案中，每个字符需要相同的位数。
有很多压缩数据的方法，就是减少表示最常用字符的位数量，比如英语中，E是最常用的字母，我 们可以只用两位01来表示，2位有四种组合:00、01、10、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;可以通过前序遍历、中序遍 历、后序遍历来遍历树，前序是根节点-左子树-右子树，中序是左子树-根节点-右子树，后序是左子树- 右子树-根节点;删除一个节点只需要断开指向它的引用即可;哈夫曼树是二叉树，用于数据压缩算 法，最经常出现的字符编码位数最少，很少出现的字符编码位数多一些。