package datastructure.tree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
/** 
   * 樹的定義和實(shí)現(xiàn) 
   * @author Administrator 
   * 
   */
public class Tree {
	private Object data;
	private List<Tree> childs;
	public Tree(){
		data = null;
		childs = new ArrayList();
		childs.clear();
	}
	public Tree(Object data) {
		this.data = data;
		childs = new ArrayList();
		childs.clear();
	}
	/** 
     * 添加子樹 
     * @param tree 子樹 
     */
	public void addNode(Tree tree) {
		childs.add(tree);
	}
	/** 
     * 置空樹 
     */
	public void clearTree() {
		data = null;
		childs.clear();
	}
	/** 
     * 求樹的深度 
     * 這方法還有點(diǎn)問(wèn)題，有待完善 
     * @return 樹的深度 
     */
	public int dept() {
		return dept(this);
	}
	/** 
     * 求樹的深度 
     * 這方法還有點(diǎn)問(wèn)題，有待完善 
     * @param tree 
     * @return 
     */
	private int dept(Tree tree) {
		if(tree.isEmpty()) {
			return 0;
		} else if(tree.isLeaf()) {
			return 1;
		} else {
			int n = childs.size();
			int[] a = new int[n];
			for (int i=0; i<n; i++) {
				if(childs.get(i).isEmpty()) {
					a[i] = 0+1;
				} else {
					a[i] = dept(childs.get(i)) + 1;
				}
			}
			Arrays.sort(a);
			return a[n-1];
		}
	}
	/** 
     * 返回遞i個(gè)子樹 
     * @param i 
     * @return 
     */
	public Tree getChild(int i) {
		return childs.get(i);
	}
	/** 
     * 求第一個(gè)孩子 結(jié)點(diǎn) 
     * @return 
     */
	public Tree getFirstChild() {
		return childs.get(0);
	}
	/** 
     * 求最后 一個(gè)孩子結(jié)點(diǎn) 
     * @return 
     */
	public Tree getLastChild() {
		return childs.get(childs.size()-1);
	}
	public List<Tree> getChilds() {
		return childs;
	}
	/** 
     * 獲得根結(jié)點(diǎn)的數(shù)據(jù) 
     * @return 
     */
	public Object getRootData() {
		return data;
	}
	/** 
     * 判斷是否為空樹 
     * @return 如果為空，返回true,否則返回false 
     */
	public Boolean isEmpty() {
		if(childs.isEmpty() && data == null) 
		        return true;
		return false;
	}
	/** 
     * 判斷是否為葉子結(jié)點(diǎn) 
     * @return 
     */
	public Boolean isLeaf() {
		if(childs.isEmpty()) 
		        return true;
		return false;
	}
	/** 
     * 獲得樹根 
     * @return 樹的根 
     */
	public Tree root() {
		return this;
	}
	/** 
     * 設(shè)置根結(jié)點(diǎn)的數(shù)據(jù) 
     */
	public void setRootData(Object data) {
		this.data = data;
	}
	/** 
     * 求結(jié)點(diǎn)數(shù) 
     * 這方法還有點(diǎn)問(wèn)題，有待完善 
     * @return 結(jié)點(diǎn)的個(gè)數(shù) 
     */
	public int size() {
		return size(this);
	}
	/** 
     * 求結(jié)點(diǎn)數(shù) 
     * 這方法還有點(diǎn)問(wèn)題，有待完善 
     * @param tree 
     * @return 
     */
	private int size(Tree tree) {
		if(tree.isEmpty()) {
			return 0;
		} else if(tree.isLeaf()) {
			return 1;
		} else {
			int count = 1;
			int n = childs.size();
			for (int i=0; i<n; i++) {
				if(!childs.get(i).isEmpty()) {
					count += size(childs.get(i));
				}
			}
			return count;
		}
	}
}

package datastructure.tree;
import datastructure.tree.btree.BTree;
/** 
   * 對(duì)結(jié)點(diǎn)進(jìn)行操作的接口,規(guī)定樹的遍歷的類必須實(shí)現(xiàn)這個(gè)接口 
   * @author Administrator 
   * 
   */
public interface Visit {
	/** 
     * 對(duì)結(jié)點(diǎn)進(jìn)行某種操作 
     * @param btree 樹的結(jié)點(diǎn) 
     */
	public void visit(BTree btree);
}

package datastructure.tree;
import java.util.List;
/** 
   * 樹的遍歷 
   * @author Administrator 
   * 
   */
public class Order {
	/** 
     * 先根遍歷 
     * @param root 要的根結(jié)點(diǎn) 
     */
	public void preOrder(Tree root) {
		if(!root.isEmpty()) {
			visit(root);
			for (Tree child : root.getChilds()) {
				if(child != null) {
					preOrder(child);
				}
			}
		}
	}
	/** 
     * 后根遍歷 
     * @param root 樹的根結(jié)點(diǎn) 
     */
	public void postOrder(Tree root) {
		if(!root.isEmpty()) {
			for (Tree child : root.getChilds()) {
				if(child != null) {
					preOrder(child);
				}
			}
			visit(root);
		}
	}
	public void visit(Tree tree) {
		System.out.print("\t" + tree.getRootData());
	}
}

package datastructure.tree;
import java.util.Iterator;
import java.util.Scanner;
public class TreeTest {
	/** 
     * @param args 
     */
	public static void main(String[] args) {
		Tree root = new Tree("A");
		root.addNode(new Tree("B"));
		root.addNode(new Tree("C"));
		root.addNode(new Tree("D"));
		Tree t = null;
		t = root.getChild(0);
		t.addNode(new Tree("L"));
		t.addNode(new Tree("E"));
		t = root.getChild(1);
		t.addNode(new Tree("F"));
		t = root.getChild(2);
		t.addNode(new Tree("I"));
		t.addNode(new Tree("H"));
		t = t.getFirstChild();
		t.addNode(new Tree("L"));
		System.out.println("first node:" + root.getRootData());
		//System.out.println("size:" + root.size()); 
		//System.out.println("dept:" + root.dept()); 
		System.out.println("is left:" + root.isLeaf());
		System.out.println("data:" + root.getRootData());
		Order order = new Order();
		System.out.println("前根遍歷：");
		order.preOrder(root);
		System.out.println("\n后根遍歷：");
		order.postOrder(root);
	}
}