树小结

1.树的概述
树代表一种非线性的，复杂的二维结构。

2.树的组成
1.根节点
2.叶子节点
3.路径（分支）；

3.树中的一些概念：
1.树的深度：
从根节点开始到叶子节点的路径数最多的那一个就是树的深度（树中节点的最大层次值）
2.度：
表示一个父节点有多少个叶子节点。
3.高度：
树的深度加一。

4.二叉树
二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

注：二叉树不是树的的特殊情况

5.树与二叉树的区别
二叉树每个父节点最多只能有两个子节点，树可以有无限个子节点
二叉树的左子结点和右子节点是有是有顺序的，但顺序是自己定义的

6.如何实现一个二叉树
1.将数据存储起来，然后对数据排列
2.创建节点：左右节点的数据域+引用（指针域）
3.构建二叉树：
每次取三个节点，根据大小判读谁为父节点谁为左右子节点（按自己想要的顺序）。再把父节点加到剩余数据中重复上述步骤。

7.树的遍历方式：
1前序遍历：先根，再左，最后右
2后序遍历：先左，再右，最后根
3中序遍历：先左，再根，最后右
中序遍历：

//遍历树 
	public void print1(Point root){
		if(root==null){
			return;
		}
		 //递归调用
		print1(root.getChildLift());
		System.out.print(root.getObj());
		print1(root.getChildRight());

	}

哈弗曼树

1.哈夫曼树又称最优树，是一类带权路径最短的树。
其中的一些概念
1.节点之间的路径长度：从一个节点到另一个节点的分支数目
2.树的路径长度：从树的根到每一个节点的的路径长度
3.节点的带权路径长度：从该节点到树根之间的路径长度与节点上权值的乘积。
4.树的带权路径长度：树中所有节点的带权路径长度,记作WPL
注：WPL最小的二叉树称为最优二叉树或哈弗曼树。（完全二叉树不一定是最优二叉树）

2.如何构造一棵哈夫曼树
1.用数组将数据保存起来，并从小到大排序（可用优先队列）；
2.取出前两个最小的数创建节点，并使之形成一个性的节点为其父节点，再将其父节点添加到队列中去。
3.重复1,2步。最后便可形成一棵哈夫曼树。

3.哈弗曼压缩
哈弗曼压缩是一种无损压缩，压缩比例为3分之2.对应用程序，重要资料等绝不允许丢失的压缩场合，是最好的选择。


哈弗曼压缩的实现：
（1）读入文件，将文件中同一字符出现的频率用数组存储起来，并排序（可用优先队列，取出即移除）。
（2）根据优先队列创建哈弗曼树（哈树中存的是节点，节点中要存取字符的ascii码值和字符出现的频率）:取出队列中的两个最小值，形成一个新的节点，再将新的节点添加
到队列中去，重复上述步骤，便可构建一棵哈弗曼树。
（3）遍历哈弗曼树，获取哈树中每个叶子节点的哈弗曼编码。
（4）写入文件
1.文件信息头
码表长度，码表对应的字符,码表
码表：编码用byte写入，不足8的整数倍的补零。
文件信息不足8的整数倍的也补零。
2.文件内容的写入。

解压就是压缩的逆过程。
简单来说，1.读取文件信息头按自己定义的读取，获取码表。
2.读取文件内容，将其转换为字符串与码表匹配，获取其对应的字符写入解压文件,需注意最后一个字节，如有补零，舍零后再写入
我觉得压缩想的过程不太难，但写的时候好麻烦。
1.读文件内容

/**
	 * 读取文件内容并将文件中字符出现的次数存储在数组中
	 * 
	 * @throws FileNotFoundException
	 */
	public void Read(String path) throws Exception {

		// 实例化一个输入流对象
		InputStream is = new FileInputStream(path);
		while (is.available() > 0) {
			int t = is.read();
			array[t]++;
			System.out.println(t + "<><><><><><>" + array[t]);
		}
	}

创建哈夫曼树

/**
	 * 利用数组构哈弗曼树
	 */
	public void createTree() {
		// 优先队列
		PriorityQueue<hfmNode> nodeQueue = new PriorityQueue<hfmNode>();
		// 将所有节点都添加到队列中去
		for (int i = 0; i < array.length; i++) {
			if (array[i] != 0) {
				// 创建节点
				hfmNode hfm = new hfmNode(i, array[i]);
				// 加入节点
				nodeQueue.add(hfm);
			}

		}
		// 构建哈弗曼树
		while (nodeQueue.size() > 1) {
			// 获取队列头
			hfmNode min1 = nodeQueue.poll();
			hfmNode min2 = nodeQueue.poll();
			System.out.println(min1.getObj() + "<><>><" + min2.getObj());
			// 构建一个新的节点，使其成为上两个的父节点
			hfmNode result = new hfmNode(0, min1.getObj() + min2.getObj());
			result.setLChild(min1);
			result.setRChild(min2);
			// 加入合并的节点
			nodeQueue.add(result);

		}
		root = nodeQueue.peek();
	}

获取哈弗曼编码
[code="java"]/**
* 取得叶子节点的哈弗曼编码
*
*/
public void getMB(hfmNode root, String s) {

// 判断
if (root.getLChild() == null && root.getRChild() == null) {
Code hc = new Code();
hc.node = s;
hc.lenght = s.length();

System.out.println("节点" + root.getCount() + "编码" + hc.node + "<>,."
+ hc.lenght);
saveCode = hc;

}
// 判断递归
if (root.getLChild() != null) {// 如果含有左子树

getMB(root.getLChild(), s + '0');

}
if (root.getRChild() != null) {// 如果含有右子树
getMB(root.getRChild(), s + '1');
}

}
[/code]
在接下来就是压缩文件文件写入时以int型写入需将01字符串转换为int型

/**
	 * 将写入的内容变成Int型
	 */
	public int changeString(String s) {
		return ((int) s.charAt(0) - 48) * 128 + ((int) s.charAt(1) - 48) * 64
				+ ((int) s.charAt(2) - 48) * 32 + ((int) s.charAt(3) - 48) * 16
				+ ((int) s.charAt(4) - 48) * 8 + ((int) s.charAt(5) - 48) * 4
				+ ((int) s.charAt(6) - 48) * 2 + ((int) s.charAt(7) - 48);
	}