树基础知识

1.树的定义（递归方式定义）

一棵树是一些节点的集合。这个集合可以是空集；若不是空集，则树由称作根（root）的节点r以及0个或多个非空的（子）树T1，T2，...Tk组成，这些子树中每一棵的跟都被来自跟r的一条又向边所连结。每一颗子树的跟叫做跟r的儿子，而r是每一棵子树根的父亲。

2.树的实现

将每一个节点的所有儿子都放在树节点的链表中。一个节点内部出了节点本身数据外还有两个引用，分别指向firstChild（第一个儿子）、和nextsibling（下一个兄弟）

3.树的遍历及应用

树的应用有很多，比较流行和常见的就是文件目录结构。如下根目录/usr，/usr又有三个儿子mark、alex、bill，他们自己也是目录。

遍历一个目录我们需要通过递归的方式进行，在遍历时我们通过tab符将目录层级分开

	public static void main(String[] args) {
		File file = new File("E:\\test");
		listAll(file, 0);//为了根目录不进行缩进，深度设为0开始
	}

	//输出文件file目录结构
	public static void listAll(File file, int depth) {
		//输出tab缩进
		for (int i = 0; i < depth; i++) {
			System.out.print("\t");
		}
		//输出文件名并换行
		System.out.println(file.getName());
		//判断是否文件夹，如果是进入下一级目录
		if (file.isDirectory()) {
			depth = depth + 1;
			for (File f : file.listFiles()) {
				listAll(f, depth);
			}
		}
	}

输出结果：

test
	name
		code
			coding.txt
	user
		clear
		sean
			sean文件.txt
	测试文件.txt

算法逻辑很简单，获取到的文件如果是一个目录，那么以递归的方式一个一个地处理它所有的儿子。这些儿子均处在下一层的深度上。这种先处理节点，再处理它所有儿子的遍历方式叫做先序遍历。

后序遍历一个节点的处理工作是在它所有儿子节点计算后进行的。如下代码示例同样以上面目录结构为例，计算根文件夹大小，根文件夹大小等于他所有子文件或文件夹大小相加，以此类推。

	public static void main(String[] args) {
		File file = new File("E:\\test");
		listAllSize(file, 0);
	}

	public static long listAllSize(File file, int depth) {
		long totalSize = 0L;
		if (file.isDirectory()) {
			int d = depth + 1;
			for (File f : file.listFiles()) {
				totalSize += listAllSize(f, d);
			}
		} else {
			totalSize = file.length();
		}
		// 输出tab缩进
		for (int i = 0; i < depth; i++) {
			System.out.print("\t");
		}
		// 输出文件名并换行
		System.out.println(file.getName() + "(" + totalSize + ")");
		return totalSize;
	}

输出结果：先计算子文件大小，再由所有子文件大小相加得到父文件大小。

			coding.txt(19720)
		code(19720)
	name(19720)
		clear(0)
			sean文件.txt(108460)
		sean(108460)
	user(108460)
	测试文件.txt(37)
test(128217)

4.二叉树