java 数据结构---树---持续补充

1. 数组的优点是，通过下标访问，速度快，有序数组，可以通过二分查找提高检索效率，但是如果要检索某个值，或者从中间插入一个值，需要移动整体，效率就很低了
2. 链式存储优点是，一定程度上优化数组存储方式，插入和删除效率提高，不用整体移动了，但是检索时效率却异常的低，比如检索特定的一个值，需要遍历整个链表
3. 树，就是提高数据存储和读取的效率，比如二叉排序树，既可以保证数据检索速度，又保证数据插入，删除，修改速度。
   

1. 下图中有一个错误，H、E、F、G没有子节点，称为叶子节点，图中将H写成了A
   

1. 二叉树就是每个节点最多有两个子节点，而形成的树形数据结构
2. 如果二叉树的所有叶子节点（没有子节点的节点称为叶子节点）都在最后一层，并且节点总数=2^n-1（n为层数），则称为满二叉树。
3. 如果二叉树的所有叶子节点都在倒数第一或倒数第二层，最后一层的叶子节点在左边连续，倒数第二层叶子节点在右边连续，称为完全二叉树
   
   

以这颗树为例

1. 前序遍历：先输出父节点，再遍历左子树和右子树
2. 中序遍历：先遍历左子树，再输出父节点，再遍历右子树
3. 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
4. 根据父节点的顺序即可判断是那种遍历，父节点最先遍历就是前序，父节点在左子树后面遍历就是中序，父节点最后遍历就是后序
5. 通过遍历，我们就可以写出查找，删除的代码
6. 运行效果
   
7. 代码

public class Test {

    public static void main(String[] args) {
        BinaryTreeNode[] binaryTreeNodes = new BinaryTreeNode[7];
        for(int i = 0 ;i 
1. 顺序存储二叉树 
顺序存储二叉树

 
 
以数组存放树的节点，遍历数组时，依旧按照前序，中序和后序的顺序遍历
 
 
 
  
顺序二叉树通常只考虑完全二叉树
第n个元素的左子节点为2n+1，右子节点为2n+2，父节点为(n-1)/2. —n表示二叉树的第几个元素，从0开始
 
 
 
 
 
有啥用?
 
 
 
  
八大排序算法的堆排序，就会用到，包括类似的场景都可以用，很好用，后面会讲到
 
 
 
 
代码
 
 
public class ArrBinaryTreeDemo {

	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
		//创建一个 ArrBinaryTree
		ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
		arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
	}

}

//编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历

class ArrBinaryTree {
	private int[] arr;//存储数据结点的数组

	public ArrBinaryTree(int[] arr) {
		this.arr = arr;
	}
	
	//重载preOrder
	public void preOrder() {
		this.preOrder(0);
	}
	
	//编写一个方法，完成顺序存储二叉树的前序遍历
	
	public void preOrder(int index) {
		//如果数组为空，或者 arr.length = 0
		if(arr == null || arr.length == 0) {
			System.out.println("数组为空，不能按照二叉树的前序遍历");
		}
		//输出当前这个元素
		System.out.println(arr[index]); 
		//向左递归遍历
		if((index * 2 + 1) < arr.length) {
			preOrder(2 * index + 1 );
		}
		//向右递归遍历
		if((index * 2 + 2) < arr.length) {
			preOrder(2 * index + 2);
		}
	}
	
}
 
2. 线索化二叉树 
线索化二叉树

 
 
解决了指针浪费问题
让空闲的指针指向自己的前后节点
 
 
 
代码
 
 
 
  
首先我们再节点中添加两个属性，分别代表左、右指针的状态，看它是指向子树，还是前驱或后继
 
然后，我们再二叉树中，创建一个属性，代表当前节点的上一个节点
 
编写方法并测试(注意，线索化二叉树，需要使用新的遍历方式，线性遍历，效率更高，结果和非线索化二叉树遍历结果一样)
 
 
 
 
 
    //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
    //在递归进行线索化时，pre 总是保留前一个结点
    private BinaryTreeNode pre = null;

    

    //重载一把threadedNodes方法
    public void threadedNodes() {
        this.threadedNodes(root);
    }

    //编写对二叉树进行中序线索化的方法
    
    public void threadedNodes(BinaryTreeNode node) {

        //如果node==null, 不能线索化
        if(node == null) {
            return;
        }

        //(一)先线索化左子树
        threadedNodes(node.getLeftNode());
        //(二)线索化当前结点[有难度]

        //处理当前结点的前驱结点
        //以8结点来理解
        //8结点的.left = null , 8结点的.leftType = 1
        if(node.getLeftNode() == null) {
            //让当前结点的左指针指向前驱结点
            node.setLeftNode(pre);
            //修改当前结点的左指针的类型,指向前驱结点
            node.setLeftType(1);
        }

        //处理后继结点
        if (pre != null && pre.getRightNode() == null) {
            //让前驱结点的右指针指向当前结点
            pre.setRightNode(node);
            //修改前驱结点的右指针类型
            pre.setRightType(1);
        }
        //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = node;

        //(三)在线索化右子树
        threadedNodes(node.getRightNode());


    }

    //遍历线索化二叉树的方法
    public void threadedList() {
        //定义一个变量，存储当前遍历的结点，从root开始
        BinaryTreeNode node = root;
        while(node != null) {
            //循环的找到leftType == 1的结点，第一个找到就是8结点
            //后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化
            //处理后的有效结点
            while(node.getLeftType() == 0) {
                node = node.getLeftNode();
            }

            //打印当前这个结点
            System.out.println(node+"left指向"+node.getLeftNode());
            //如果当前结点的右指针指向的是后继结点,就一直输出
            while(node.getRightType() == 1) {
                //获取到当前结点的后继结点
                node = node.getRightNode();
                System.out.println(node+"right指向"+node.getRightNode());
            }
            //替换这个遍历的结点
            node = node.getRightNode();

        }
    }
 
3. 二叉排序树（BST） 
 
 
BST(Binary Sort(Search) Tree),二叉排序树就是任何一个非叶子结点，要求左子结点的值比当前结点的值小，右子结点的值比当前结点的值大。如果有相同的值，可以将该结点放在左或右子结点
 
 
 
二叉树的构建、添加和删除

 
 
构建
 
 
 
  
比如将{7,3,10,12,5,1,9}构建成排序二叉树，依次遍历数据，第一个直接就是根结点，剩下的按照规则，小的在左边，大的在右边，依次添加即可
 
 
 
 
添加
 
 
 
  
添加就是从根结点开始往下找，如果他比根结点大，就比较右边，如果右子结点没值，直接添加，如果有，就和右子结点比较，依次类推
 
 
 
 
删除
 
 
 
 
  
删除叶子结点，比如2,5,9,12，直接删除即可
删除有一颗子树的节点，比如1，直接让它的子树来到它的位置，然后删掉自己
删除有两颗子树的节点，比如7,3,10，让它的右子树来到它的位置，然后删掉自己,然后让左子树按排序树规则添加到右子树，比如删除7，让10和它的子树到它的位置，然后3和它的子树添加到9的左子树
删除结点时，如果当前结点的子结点，就是要删除的结点，那么开始执行逻辑
首先判断要删除的结点时1,2,3种情况的那种，然后进行相应操作
 
 
 
 
代码

 
 
运行效果
 
代码
 
 
import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9};
        System.out.println("将数组"+ Arrays.toString(arr)+"构建成二叉排序树=================");
        BinarySortTree binarySortTree = new BinarySortTree(arr);
        System.out.println("二叉排序树中序遍历结果为======================================");
        binarySortTree.midOrder();
        System.out.println("添加一个结点2");binarySortTree.add(2);binarySortTree.midOrder();
        System.out.println("删除结点2");binarySortTree.deleteNode(2);binarySortTree.midOrder();
        System.out.println("删除结点5");binarySortTree.deleteNode(5);binarySortTree.midOrder();
        System.out.println("删除结点9");binarySortTree.deleteNode(9);binarySortTree.midOrder();
        System.out.println("删除结点12");binarySortTree.deleteNode(12);binarySortTree.midOrder();
        System.out.println("删除结点7");binarySortTree.deleteNode(7);binarySortTree.midOrder();
        System.out.println("删除结点3");binarySortTree.deleteNode(3);binarySortTree.midOrder();
        System.out.println("删除结点10");binarySortTree.deleteNode(10);binarySortTree.midOrder();
        System.out.println("删除结点1");binarySortTree.deleteNode(1);binarySortTree.midOrder();
    }

}


class BinarySortTreeNode{
    private int data;
    private BinarySortTreeNode left;
    private BinarySortTreeNode right;

    public BinarySortTreeNode(int data) {
        this.data = data;
    }

    
    public void add(BinarySortTreeNode node){
        if(node == null) return;//如果结点为null，不进行添加
        //如果要添加结点比当前结点小，那么添加到左子结点
        if(node.getData()this.data){//如果要添加结点比当前结点大，那么添加到右子结点
            if(this.right==null){//如果右子结点为空，将结点添加
                this.right = node;
            }else {//不为空
                this.right.add(node);//递归到右子树添加
            }
        }else{//如果要添加结点等于当前结点，添加到左右都可以
            if(this.left==null){
                this.left = node;
            }else if(this.right == null){
                this.left = node;
            }
            //如果左右子节点都有了，那么放在右子树
            else{
                this.right.add(node);
            }
        }
    }

    
    public void midOrder(){
        //1. 如果左子树存在，遍历左子树
        if(this.left!=null){
            this.left.midOrder();
        }
        //2. 然后输出当前节点
        System.out.print(this+" ");

        //3. 如果右子树存在，遍历右子树
        if(this.right!=null){
            this.right.midOrder();
        }
    }

    
    public BinarySortTreeNode midFindParent(Integer id){

        BinarySortTreeNode node = null;//用来保存结果

        //1. 如果左子树存在，判断左子结点是否是要找的值，不是继续遍历左子树
        if(this.left!=null&&this.left.getData()!=id){
            node =  this.left.midFindParent(id);
        }
        if(node != null){//如果node不为null，那么表示在左子树找到了，直接返回，无需执行下面找右子树的代码
            return node;
        }

        //2. 没有左子树了，判断是否和自己一致
        if(this.left!=null){
            if(id==this.left.data) return this;
        }
        if(this.right!=null){
            if(id==this.right.data) return this;
        }


        //3. 如果右子树存在，遍历右子树
        if(this.right!=null&&this.right.getData()!=id){
            node = this.right.midFindParent(id);
        }
        return node;
    }

    public int getData() { return data; }


    public void setData(int data) { this.data = data; }

    public BinarySortTreeNode getLeft() { return left; }

    public void setLeft(BinarySortTreeNode left) { this.left = left; }

    public BinarySortTreeNode getRight() { return right; }

    public void setRight(BinarySortTreeNode right) { this.right = right; }

    @Override
    public String toString() { return "Node{" + "data=" + data + '}'; }
}

class BinarySortTree{
    private BinarySortTreeNode root;

    public BinarySortTreeNode getRoot() { return root; }

    public BinarySortTree(){}

    //构造方法，通过数组直接构造排序二叉树
    public BinarySortTree(int[] arr){ this.addArrayToBinarySortTree(arr); }
    
    public void add(BinarySortTreeNode node){
        if(node == null) throw new RuntimeException("要添加结点为空！！！");
        if(root == null) root = node;
        else root.add(node);
    }

    
    public void add(int data){
        add(new BinarySortTreeNode(data));
    }

    
    public BinarySortTreeNode findParentByData(int data){
        if(root.getData() == data) return null;
        return root.midFindParent(data);
    }

    
    private void deleteRoot(){
        if(root.getLeft()==null&&root.getRight()==null){
            root=null;
        }else if(root.getLeft()!=null&&root.getRight()!=null){
            BinarySortTreeNode left = root.getLeft();
            root = root.getRight();
            add(left);
        }else if(root.getLeft()==null&&root.getRight()!=null){
            root=root.getRight();
        }else if(root.getLeft()!=null&&root.getRight()==null){
            root=root.getLeft();
        }
    }
    
    private void deleteNode(BinarySortTreeNode node,BinarySortTreeNode nodeParent,Boolean flag){
        if (node.getLeft()==null&&node.getRight()==null){//如果要删除结点是叶子结点，直接删除
            if(flag) nodeParent.setLeft(null);//如果它是父结点的左子结点，直接让父结点的left置为null
            else nodeParent.setRight(null);//如果是右子结点，让right置为null
        }else if(node.getLeft()!=null && node.getRight()==null){//如果要删除结点是只有右子树的结点
            //让右子树到它的位置
            if(flag) nodeParent.setLeft(node.getLeft());
            else nodeParent.setRight(node.getRight());
        }else if(node.getRight()!=null&&node.getLeft()==null){//如果要删除结点是只有左子树的结点
            //让左子树到它的位置
            if(flag)nodeParent.setLeft(node.getRight());
            else nodeParent.setRight(node.getRight());
        }else{//如果要删除结点拥有左右两个子树
            //让右子树到它的位置，然后左子树按规则添加到右子树中
            BinarySortTreeNode left = node.getLeft();//先记录左子树
            if(flag){
                nodeParent.setLeft(node.getRight());//然后让它的右子树到它原来的位置
                node.getRight().add(left);//然后将左子树按规则添加到右子树
            }else{
                nodeParent.setRight(node.getRight());
                node.getRight().add(left);
            }
        }
    }
    
    public void deleteNode(int data){
        if(root == null) throw new RuntimeException("二叉排序树为空");

        BinarySortTreeNode nodeParent = null;//要删除节点的父节点
        BinarySortTreeNode node = null;//要删除的节点
        boolean flag = true;//要删除节点是父节点左子结点True，还是右子结点False

        if(root.getData()==data){//如果是根结点
            deleteRoot();//删除根结点
            return;
        }
        //获取要删除结点的父结点
        nodeParent = findParentByData(data);
        //获取要删除结点，并用flag记录结点时父结点的左子结点还是右子结点
        if(nodeParent.getLeft()!=null&&nodeParent.getLeft().getData()==data){
           node = nodeParent.getLeft();
           flag = true;
        }else{
            node = nodeParent.getRight();
            flag = false;
        }
        if(node==null){
            System.out.println("没有找到要删除的节点");
            return;
        }else{
            deleteNode(node,nodeParent,flag);
        }

    }

    
    public void midOrder(){
        if(root == null) System.out.println("二叉排序树为空！！！");
        else {
            root.midOrder();
            System.out.println();
        }
    }

    
    public void addArrayToBinarySortTree(int[] arr){
        for(int i : arr){
            BinarySortTreeNode binarySortTreeNode = new BinarySortTreeNode(i);
            add(binarySortTreeNode);
        }
    }
}
 
4. 平衡二叉树（AVT） 
平衡二叉树，就是更完善的二叉排序树，代码也是在二叉排序基础上添加了一些逻辑

 
 
平衡二叉树(AVL)，又名平衡二叉搜索树，保证查询效率较高
它是一课空树或它的左右两个子树的高度差的绝对值小于等于1，并且左右两个子树都是一课平衡二叉树。满足这些特点就是平衡二叉树。(下图就是一课树，右子树高度比左子树高2，不满足，所以进行左旋转操作，后面会讲)
 
常用实现算法有红黑树、AVL算法、替罪羊树、Treap、伸展树等
 
 
为什么要有平衡二叉树

 
 
 
 
 
  
当我们要将一个递增的序列转换成二叉排序树时，那么会变成一个效率很低的单链表，因为需要判断左右子树
而平衡二叉树可以解决此类问题
 
 
 
 
左旋转（以右子树比左子树高度，高1以上，比如2，就需要左旋转，反之右旋转）

 
 
 
 
右旋转

 
 
 
 
双旋转

 
 
某些序列，无法通过左旋转，或右旋转，转变为平衡二叉树，此时需要双旋转
 
 
 
代码，只贴出和二叉排序树不同的代码块

 
 
运行效果
 
代码(以下指出添加的代码，和修改的代码)
 
 
 
 
    
    public int leftHeight(){
        if(left == null){
            return 0;
        }
        return left.height();
    }
    
    public int rightHeight(){
        if(right == null){
            return 0;
        }
        return right.height();
    }
    
    public int height(){
        return Math.max(left == null?0:left.height(),right == null?0:right.height())+1;
    }

    
    public void leftRotate(){
        //1.创建新结点，保存当前根结点
        BinarySortTreeNode binarySortTreeNode = new BinarySortTreeNode(data);
        //2.左子树变为新结点左子树
        binarySortTreeNode.setLeft(left);
        //3.右子树的左子树变为新结点的右子树
        binarySortTreeNode.setRight(right.getLeft());
        //4.让右子树上移成为根结点
        data = right.getData();
        right = right.getRight();
        //5.新结点作为左子树
        left = binarySortTreeNode;
    }

    
    public void rightRotate(){
        //1.创建新结点，保存当前根结点
        BinarySortTreeNode binarySortTreeNode = new BinarySortTreeNode(data);
        //2.右子树变为新结点右子树
        binarySortTreeNode.setRight(right);
        //3.左子树的右子树变为新结点的左子树
        binarySortTreeNode.setLeft(left.getRight());
        //4.让左子树上移成为根结点
        data = left.getData();
        left = left.getLeft();
        //5.新结点作为右子树
        right = binarySortTreeNode;
    }

    
    public void add(BinarySortTreeNode node){
        if(node == null) return;//如果结点为null，不进行添加
        //如果要添加结点比当前结点小，那么添加到左子结点
        if(node.getData()this.data){//如果要添加结点比当前结点大，那么添加到右子结点
            if(this.right==null){//如果右子结点为空，将结点添加
                this.right = node;
            }else {//不为空
                this.right.add(node);//递归到右子树添加
            }
        }else{//如果要添加结点等于当前结点，添加到左右都可以
            if(this.left==null){
                this.left = node;
            }else if(this.right == null){
                this.left = node;
            }
            //如果左右子节点都有了，那么放在右子树
            else{
                this.right.add(node);
            }
        }

        
        //如果右子树高度比左子树高度大，并且比1大,那么需要左旋转
        if(rightHeight() - leftHeight()>1){
            //如果右子树的左子树高度，大于右子树的右子树的高度，那么进行双旋转(先对右子树，右旋转)
            if(right!=null && right.leftHeight() > right.rightHeight()){
                right.rightRotate();
                //然后再左旋转
                leftRotate();
            }else{
                //然后再左旋转
                leftRotate();
            }
            return;//旋转完成后，不要继续下面的判断了
        }
        //如果左子树高度比右子树高度大，并且比1大,那么需要右旋转
        if(leftHeight() - rightHeight()>1){
            //如果左子树的右子树高度，大于左子树的左子树的高度，那么进行双旋转(先对左子树，左旋转)
            if(left!=null && left.rightHeight() > left.leftHeight()){
                left.leftRotate();
                //然后再右旋转
                rightRotate();
            }else{
                //然后再右旋转
                rightRotate();
            }
            return;
        }
    }

 
二、赫夫曼树 
 
 
给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小，称为最优二叉树，又称哈夫曼树（Huffman Tree），或霍夫曼树或赫夫曼树
赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
 
 
 
 
  
13这个结点，权值是13，根结点层数为1的情况下，此结点的路径长度是2
这并不是一课赫夫曼树，请继续往下看
 
 
 
 
路径和路径长度

 
 
一棵树中，一个结点往下可以到达的孩子或孙子结点之间的通路，称为路径。
通路中分支的数目称为路径长度，若根节点层数为1，则根节点到第L层结点的路径长度为L-1
 
 
 
 
  
根结点层数为1,13这个结点层数为3,3-1=2，那么13这个结点路径长度为2
 
 
 
 
结点的权和带权路径长度

 
 
权：树中结点赋予一个具有某种含义的数值，称为该结点的权
结点带权路径长度：根节点到该结点之间的路径长度与该结点的权的乘积
 
 
 
  
依然以上面的图片为例，13这个结点的带权路径长度就是路径长度 *权=2 *13=26
 
 
 
 
树的带权路径长度

 
 
所有叶子结点的带权路径长度之和，即为WPL(weighted path length)，权值越大的结点离根结点越近的二叉树才是最优二叉树。
WPL最小的就是赫夫曼树
 
 
 
 
  
树的带权路径长度wpl是评价一课二叉树是否为赫夫曼树的指标，wpl最小的就是最赫夫曼树
树的wpl就是所有叶子节点的带权路径长度相加后的结果
上图可以看出，中间的树，满足权值越大的叶子结点离根节点越近（层数越靠近根结点层数）的条件，那么它就是最优二叉树
 
 
 
 
1. 创建赫夫曼树 
如何创建赫夫曼树

 
 
假定数列{13,7,8,3,29,6,1}要转换成一棵赫夫曼树
先从小到大排序，将每一个数据（就是一个结点），看成是一颗最简单的二叉树
取出根结点权值最小的两颗二叉树（第一次取，就是1和3这两颗）
组成一棵新的二叉树，此时新二叉树的根结点权值是前面两颗二叉树根结点的权值之和（第一次就是1和3合并，根结点权值为1+3=4,那么此时就有了一颗{1,4,3}的二叉树）
最后再将新二叉树，以根结点的权值大小再次排序（第一次就是{1,4,3}这颗和{6}这颗），然后不断重复3-4-5的步骤，直到数列中，所有数据都被处理，就得到了赫夫曼树
 
 
 
代码

 
 
运行效果
 
代码
 
 
import java.util.ArrayList;
import java.util.Collections;

public class Test {

    public static void main(String[] args) {
        int arr[] = {13,7,8,3,29,6,1};
        HuffmanTreeNode huffmanTree = createHuffmanTree(arr);
        System.out.println("====前序遍历结果====");
        preOrder(huffmanTree);
    }

    
    public static HuffmanTreeNode createHuffmanTree(int[] arr){
        //1.将arr中每个元素构建成结点，放入一个集合中
        ArrayList huffmanTreeNodes = new ArrayList<>();
        for(int value:arr){
            huffmanTreeNodes.add(new HuffmanTreeNode(value));
        }
        //不断重复 取结点---构成新二叉树----重新排序，直到集合中只剩下一个结点
        while(huffmanTreeNodes.size()>1){
            //2.排序，使用Collections接口的sort方法，对集合排序，要求集合中元素，必须实现Comparable接口，并从写compareTo方法，至于从小到大排，还是从大到小排，取决于compareTo方法的实现
            Collections.sort(huffmanTreeNodes);
            //3. 取出根结点最小的两颗二叉树，构建成新二叉树，然后删除最小两颗二叉树，将新二叉树放集合中，然后排序
            HuffmanTreeNode leftNode = huffmanTreeNodes.get(0);//取出集合第一个，也就是最小的
            HuffmanTreeNode rightNode = huffmanTreeNodes.get(1);//取出第二个，也就是第二小的
            HuffmanTreeNode parent = new HuffmanTreeNode(leftNode, rightNode);//然后构建一个新二叉树
            huffmanTreeNodes.remove(leftNode);//删除
            huffmanTreeNodes.remove(rightNode);//删除
            huffmanTreeNodes.add(parent);//将新二叉树放进集合
            Collections.sort(huffmanTreeNodes);//排序
        }

        return huffmanTreeNodes.get(0);
    }
    
    public static void preOrder(HuffmanTreeNode node){
        if(node == null){
            System.out.println("赫夫曼树为空树");
            return;
        }
        node.preOrder();
    }
}


class HuffmanTreeNode implements Comparable {
    private int value;//结点权值
    private HuffmanTreeNode left;//左子结点
    private HuffmanTreeNode right;//右子结点

    
    public HuffmanTreeNode(int value) {
        this.value = value;
    }

    
    public HuffmanTreeNode(HuffmanTreeNode left,HuffmanTreeNode right){
        this.left = left;
        this.right = right;
        this.value = left.getValue() + right.getValue();
    }

    @Override
    public int compareTo(HuffmanTreeNode o) {
        //从小到大排序，至于为什么，百度一下Comparable接口
        return this.value - o.value;
        //从大到小排
        //return -(this.value - o.value);
    }

    
    public void preOrder(){
        //1. 先输出当前节点
        System.out.println(this+" ");
        //2. 如果左子树存在，遍历左子树
        if(this.left!=null){
            this.left.preOrder();
        }
        //3. 如果右子树存在，遍历右子树
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "HuffmanTreeNode{" +
                "value=" + value +
                '}';
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public HuffmanTreeNode getLeft() {
        return left;
    }

    public void setLeft(HuffmanTreeNode left) {
        this.left = left;
    }

    public HuffmanTreeNode getRight() {
        return right;
    }

    public void setRight(HuffmanTreeNode right) {
        this.right = right;
    }


}
 
2. 赫夫曼编码 
 
 
又称哈夫曼编码（Huffman Coding），又称霍夫曼编码，是一种编码方式，一种程序算法
是赫夫曼树在电讯通讯中的经典应用之一
广泛应用于数据文件压缩，压缩率在20%~90%之间
是可变字长编码（VLC的一种），Huffman于1952年提出一种编码方法，称为最佳编码
 
 
首先看一下定长编码方式，就是将字符转换成Ascii码，然后取到对应2进制编码，传输

 
 
 
 
变长编码，就是统计每个字符出现的次数，次数越多，编码越小，然后按照编码，将其组成一串2进制编码，但是因为编码的前缀重复性，比如编码1和编码10，计算机不知道什么时候按1解析，什么时候按10解析，也就是说，不能匹配到重复编码

 
 
 
 
赫夫曼编码，将字符出现次数，作为权值，出现的越多，权值越大，根据权值构建赫夫曼树

 
 
 
 
根据权值创建赫夫曼树，向左的路径为0，向右的路径为1
 
然后根据创建好的赫夫曼树，给各字符规定编码，可以发现，每个字符的编码，都不是其它字符编码的前缀，比如o的编码是1000，u的编码10010，如果o的编码是100，那么确实是10010的前缀，但是此编码，不会出现这种情况，那么赫夫曼编码，满足前缀编码的特性，不会造成匹配多义性
 
额外的，如果出现权值相同的情况，比如有4个权值为4的二叉树，那么它们的位置并不固定，这样生成的赫夫曼树不一样，编码也完全不一样，但是wpl是一样的，所以如果出现这种情况也无伤大雅，压缩最后的结果长度，还是一样的
 
 
实现思路和代码

 
 
实现思路
 
 
 
  
赫夫曼树的结点，除了存放权值、左右子树，还要存放数据
得到"i like like like java do you like a java"对应的byte数组
生成结点，将结点放到List
创建赫夫曼树
获取赫夫曼编码，
获取字符串对应二进制编码，也就是压缩操作（压缩对应的byte数组，返回的也是byte数组）
解码，就是解压操作
 
 
 
 
运行效果
 
 
 
 
 
代码
 
 
import java.util.*;

public class Test {

    public static void main(String[] args) {
        String str = "i like like like java do you like a java";
        //> > 2. 得到"i like like like java do you like a java"对应的byte数组
        byte[] strBytes = str.getBytes();

        System.out.println("源字符串和源字节数组==========================");
        System.out.println(str);
        System.out.println("压缩前字节数组"+Arrays.toString(strBytes));

        //获取压缩后字节数组和赫夫曼树编码表
        List