难点：树的代码
ADT:
package tree;
public interface TTree<T> {
boolean isEmpty();//判断是否为空
int level(T key);//判断层次
int size();//节点数量
int height();//树的高度
void preorder();//先根次序
void postorder();//后根次序
void levelorder();//层次遍历
TreeNode<T> insertRoot(T x);//当根节点插入
TreeNode<T> insertChild(TreeNode<T> p,T x,int i);//插入x当作p节点的i个孩子
void remove(TreeNode<T> p,int i);//删除第i个子树
void clear();//清空
TreeNode<T> search(T x);//查找
T remove(T x);//删除
boolean contains(T key);//判断是否包含
}
TreeNode:
package tree;
public class TreeNode<T> {
public T data;//数据
public TreeNode<T> parent,child,sibling;//父母节点，孩子节点，兄弟节点，链表连接
public int level;//节点层次
public TreeNode(T data, int level,TreeNode<T> parent,TreeNode<T> child,TreeNode<T> 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());
}
}
运行结果：
