从零开始学数据结构和算法(七) huffman 树与 AVL 树

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