难点：树的代码

ADT:

package tree;
 
public interface TTree<T> {
	boolean isEmpty();//判断是否为空
	int level(T key);//判断层次
	int size();//节点数量
	int height();//树的高度
	
	void preorder();//先根次序
	void postorder();//后根次序
	void levelorder();//层次遍历
	
	TreeNode insertRoot(T x);//当根节点插入
	TreeNode insertChild(TreeNode p,T x,int i);//插入x当作p节点的i个孩子
	void remove(TreeNode p,int i);//删除第i个子树
	void clear();//清空
	
	TreeNode search(T x);//查找
	T remove(T x);//删除
	boolean contains(T key);//判断是否包含
	
}

TreeNode:

package tree;
 
public class TreeNode<T> {
	public T data;//数据
	public TreeNode parent,child,sibling;//父母节点，孩子节点，兄弟节点，链表连接
	public int level;//节点层次
	
	public TreeNode(T data, int level,TreeNode parent,TreeNode child,TreeNode sibling) {
		this.data=data;
		this.level=level;
		this.parent=parent;
		this.child=child;
		this.sibling=sibling;//初始化成功
	}
	public TreeNode(T data,int level) {
		this(data,level,null,null,null);//初始化
	}//为的是初始化
	public String toString() {
		return this.data.toString();//节点信息
	}
	public boolean isLeaf() {
		return this.child==null;
	}//判断是不是叶子节点
}

Tree:

package tree;
 
public class Tree<T> {
	public TreeNode <T>root;//根节点
	public Tree() {
		this.root=null;//初始化
	}
	public boolean isEmpty() {
		return this.root==null;
	}//判空
	
	public String toString() {
		return "树的显示\n"+toString(root,"");
	}
	public String toString(TreeNode<T>  p,String tab) {
		if (p==null) {
			return "";
		}
		return tab+p.data.toString()+"\n"+toString(p.child,tab+"\t")+toString(p.sibling,tab);//递归调用
	}
	//先序
	public  void preorder() {
		preorder(this.root);
		System.out.println();
	}
	public  void preorder(TreeNode<T>  p) {
		if(p!=null) {
			System.out.print(p.data+" ");
			preorder(p.child);
			preorder(p.sibling);//循环调用
		}
	}
	//后序
	public  void postorder() {
		postorder(this.root);
		System.out.println();
	}
	public  void postorder(TreeNode<T>  p) {
		if(p!=null) {
	
			postorder(p.child);
			System.out.print(p.data+" ");
			postorder(p.sibling);//循环调用
		}
	}
	//递归提取节点数量
	public int size() {
		return size(this.root);
	}
	public int size(TreeNode<T>  p) {
		if(p==null) {
			return 0;
		}
		return 1+size(p.child)+size(p.sibling);
	}
	
	public Tree(Tree<T> tree) {
		this.root=copy(tree.root,null);//初始化
	}
	
	//深拷贝
	public TreeNode<T> copy(TreeNode<T> p,TreeNode<T> parent){
		if (p==null) {
			return null;
		}
		TreeNode<T> q=new TreeNode<T>(p.data,p.level,parent,null,null);
		q.child=copy(p.child,q);
		q.child=copy(p.sibling,q);
		return q;//返回节点
	}
	public void clear() {
		this.root=null;
	}
	public void setLevel(TreeNode<T> p,int level) {
		if(p!=null) {
			p.level=level;
			setLevel(p.child,level+1);
			setLevel(p.sibling,level);
		}
	}
	public  TreeNode<T> insertRoot(T x){
		this.root=new TreeNode<T>(x,1,null,this.root,null);
		if(this.root.child!=null) {
			this.root.child.parent=this.root;
			setLevel(this.root.child,this.root.level+1);//完成插入
		}
		return this.root;
	}
	//String prelist[]={"中国","\t北京","\t上海","\t江苏","\t\t南京","\t\t\t江宁","\t\t苏州",
    //"\t\t无锡","\t\t\t锡山","\t浙江","\t\t杭州","\t\t宁波","\t\t温州","\t广东","\t\t广州",
    //"韩国","\t首尔","法国","意大利","美国","\t华盛顿","\t纽约州","\t\t纽约"};
	public static  Tree<String> create(String[]prelist){
		Tree<String> tree =new Tree<String>();
		if (prelist.length==0) {
			return tree; //返回空树
		}
		tree.root=new TreeNode<String>(prelist[0],1);//层次1，
		TreeNode<String>p=tree.root;//备份根节点
		for(int i=1;i<prelist.length;i++) {
			int n=0;//多少个tab字符，为的是看层次
			while(n<prelist[i].length() && prelist[i].charAt(n)=='\t') {//"\t"的长度是一
				n++;
			}
			String str=prelist[i].substring(n);//去除\t
			if(n==p.level) {
				p.child=new TreeNode<String>(str,p.level+1,p,null,null);
				p=p.child;//循环下一个
			}else {
				while(n<p.level-1) {//向上寻找位置
					p=p.parent;
				}
				p.sibling=new TreeNode<String>(str,p.level,p.parent,null,null);
				p=p.sibling;
			}
		}
		return tree;
	}
}

运行代码：

package tree;
 
public class TreeRun {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String prelist[]={"中国","\t北京","\t上海","\t江苏","\t\t南京","\t\t\t江宁","\t\t苏州",
                "\t\t无锡","\t\t\t锡山","\t浙江","\t\t杭州","\t\t宁波","\t\t温州","\t广东","\t\t广州",
                "韩国","\t首尔","法国","意大利","美国","\t华盛顿","\t纽约州","\t\t纽约"};
 
	Tree<String>mytree=Tree.create(prelist);
		mytree.preorder();
		mytree.postorder();
		System.out.println(mytree.toString());
	}
 
}

运行结果：