- 左旋
- 右旋
代码
Huffman 树
public class HuffmanTree {
TreeNode root;
public TreeNode createHuffManTree(ArrayList 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 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 list = new ArrayList<>();
TreeNode node = new TreeNode(“good”, 50);
list.add(node);
list.add(new TreeNode(“morning”, 10));
TreeNode 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 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.po
p());
}
}
/**
-
结点
-
@param
*/
public static class TreeNode implements Comparable<TreeNode> {
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 o) {
if (this.weight > o.weight) {
return -1;
} else if (this.weight < o.weight) {
return 1;
}
return 0;
}
}
}
平衡二叉树
ld = null;
parent = null;
}
@Override
public int compareTo(@NonNull TreeNode o) {
if (this.weight > o.weight) {
return -1;
} else if (this.weight < o.weight) {
return 1;
}
return 0;
}
}
}