二叉树

二叉树 - 所有节点的度都不大于2的树。

存储结构 - 顺序和链式
对于顺序存储结构， 当二叉树为完全二叉树的时候才能够不浪费存储空间， 否则对空间的浪费是很大滴。

而对于链式存储结构， 分三域节点和四域节点
三域 - Data + lChild + rChild
四域 - Data + lChild + parent + rChild

----------------------------- 我是分割线 ----------------------------

二叉树的基本操作：
先序， 中序 和 后序遍历

先定义node

public class Node {
	private String value;
	private Node parent;
	private Node leftChild;
	private Node rightChild;

	public Node(String value, Node parent, Node leftChild, Node rightChild) {
		this.value = value;
		this.parent = parent;
		this.leftChild = leftChild;
		this.rightChild = rightChild;
	}

	public String getValue() {
		return value;
	}

	public Node getParent() {
		return this.parent;
	}

	public Node getLeftChild() {
		return this.leftChild;
	}

	public Node getRightChild() {
		return this.rightChild;
	}
}

再来看遍历

public class Tree {
	
	//       a
	//      / \
	//     b   c
	//    / \   \
	//   d   e   g
	
	public static void main(String[] args) {
		Node d = new Node("d", null, null, null);
		Node e = new Node("e", null, null, null);
		Node g = new Node("g", null, null, null);

		Node b = new Node("b", null, d, e);
		Node c = new Node("c", null, null, g);

		Node a = new Node("a", null, b, c);
		
		printDataLR(a);
		System.out.println();
		printLeftDR(a);
		System.out.println();
		printLRightD(a);
	}
	
	// 先序遍历 a-b-d-e-c-g
	private static void printDataLR(Node root) {
		if (root == null)
			return;
		System.out.print(root.getValue());
		printDataLR(root.getLeftChild());
		printDataLR(root.getRightChild());
	}

	// 中序遍历 d-e-b-g-c-a
	private static void printLeftDR(Node root){
		if (root == null)
			return;
		printLeftDR(root.getLeftChild());
		System.out.print(root.getValue());
		printLeftDR(root.getRightChild());
	}

	// 后序遍历 d-e-b-g-c-a
	private static void printLRightD(Node root){
		if (root == null)
			return;
		printLRightD(root.getLeftChild());
		printLRightD(root.getRightChild());
		System.out.print(root.getValue());
	}
}

----------------------------- 我是分割线 ----------------------------

Huffman树

先看个例子：

//               X
//            0/   \1
//            X      X
//          0/ \1 0/  \1
//          a   b c    d

//      a = 00; b = 01; c = 10; d = 11.

所以假如给定一个字串： aabdca, 则其对应的二进制编码为： 000001111000
而对其解码就是从根结点出发， 扫描二进制编码， 0往左， 1往右， 碰到叶子节点直接输出， 然后重新回到跟结点。所输出来的就是原始字串了。

再来看看Huffman树的定义：
由n个带权叶子结点构成的所有二叉树中带权路径长度最小的二叉树， 又叫最优二叉树。
什么生权？ 权就是赋予结点某种特殊意义的正数。
带权路径则是: Sum(结点的权 × 结点到根的路径长度)

一个Huffman树的构造过程如下：

// 权值 {5, 9, 11, 32, 10, 21, 6}

// 第一步
       11    9   11   32   10   21
      / \
     5   6

// 第二步
       11    19   11   32    21
      / \    / \
     5   6  9  10 

// 第三步
       22    19   32    21
      / \    / \
     11  11 9  10
    / \ 
   5  6 

// 第四步
      22      40     32
     / \     / \ 
   11  11   19  21 
   / \     / \
  5  6    9  10

// 第五步
        54            40
       / \            / \
      22  32        19  21
	   / \            / \
   11  11          9  10 
   / \     
  5  6     

// 第六步
            94
          /   \ 
       54      40
      / \      / \
     22 (32) (19)(21)
    / \      / \
   11 (11) (9) (10) 
   / \     
 (5) (6)