Huffman 树

概念

树的构造

Huffman 源码

AVL 树(平衡二叉树)

概念

平衡因子二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）
最小不平衡树

构建 AVL 树

左旋

右旋

代码

Huffman 树

public class HuffmanTree {
    TreeNode root;
public TreeNode createHuffManTree(ArrayList<TreeNode> list) {
    while (list.size() > 1) {
        Collections.sort(list);
        TreeNode left = list.get(list.size() - 1);
        TreeNode right = list.get(list.size() - 2);
        TreeNode parent = new TreeNode("p", left.weight + right.weight);
        parent.leftChild = left;
        left.parent = parent;
        parent.rightChild = right;
        right.parent = parent;
        list.remove(left);
        list.remove(right);
        list.add(parent);
    }
    root = list.get(0);
    return list.get(0);
}

public void showHuffman(TreeNode root) {
    LinkedList<TreeNode> list = new LinkedList<>();
    list.offer(root);//入队
    while (!list.isEmpty()) {
        TreeNode node = list.pop();
        System.out.println(node.data);
        if (node.leftChild != null) {
            list.offer(node.leftChild);
        }
        if (node.rightChild != null) {
            list.offer(node.rightChild);
        }
    }
}

@Test
public void test() {
    ArrayList<TreeNode> list = new ArrayList<>();
    TreeNode<String> node = new TreeNode("good", 50);
    list.add(node);
    list.add(new TreeNode("morning", 10));
    TreeNode<String> node2 =new TreeNode("afternoon", 20);
    list.add(node2);
    list.add(new TreeNode("hell", 110));
    list.add(new TreeNode("hi", 200));
    HuffmanTree tree = new HuffmanTree();
    tree.createHuffManTree(list);
    tree.showHuffman(tree.root);
    getCode(node2);
}

/**
 * 编码
 */
public void getCode(TreeNode node) {
    TreeNode tNode = node;
    Stack<String> stack = new Stack<>();
    while (tNode != null && tNode.parent != null) {
        //left 0  right 1
        if (tNode.parent.leftChild == tNode) {
            stack.push("0");
        } else if (tNode.parent.rightChild == tNode) {
            stack.push("1");
        }
        tNode = tNode.parent;
    }
    System.out.println();
    while (!stack.isEmpty()) {
        System.out.print(stack.pop());
    }
}

/**
 * 结点
 *
 * @param <T>
 */
public static class TreeNode<T> implements Comparable<TreeNode<T>> {
    T data;
    int weight;
    TreeNode leftChild;
    TreeNode rightChild;
    TreeNode parent;

    public TreeNode(T data, int weight) {
        this.data = data;
        this.weight = weight;
        leftChild = null;
        rightChild = null;
        parent = null;
    }

    @Override
    public int compareTo(@NonNull TreeNode<T> o) {
        if (this.weight > o.weight) {
            return -1;
        } else if (this.weight < o.weight) {
            return 1;
        }
        return 0;
    }
}
}

平衡二叉树

左旋转

public class AVLBTree<E extends Comparable<E>> {
    Node<E> root;
    int size;
    public class Node<E extends Comparable<E>>{
        E element;
        int balance=0;//平衡因子
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element,Node<E> parent){
            this.element=element;
            this.parent=parent;
        }
    }
    public void left_rotate(Node<E> x){
        if(x!=null){
            Node<E> y=x.right;//先取到Y
            //1.把贝塔作为X的右孩子
            x.right=y.left;
            if(y.left!=null){
                y.left.parent=x;
            }
            //2。把Y移到原来X的位置上
            y.parent=x.parent;
            if(x.parent==null){
                root=y;
            }else{
                if(x.parent.left==x){
                    x.parent.left=y;
                }else if(x.parent.right==x){
                    x.parent.right=y;
                }
            }
            //3.X作为Y的左孩子
            y.left=x;
            x.parent=y;
        }
    }
}

作者：DevYK
链接：https://juejin.im/post/5c9464515188252d7e34df85