從零開始學資料結構和演算法(七) huffman 樹與 AVL 樹

摘要： 樹的構造 Huffman 原始碼 AVL 樹(平衡二叉樹) 概念 平衡因子 二叉樹上節點...

樹的構造

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 0right 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;
  }
  }
  }
  複製程式碼