学步园

package dankui.com;

//tree接口

public interface Tree {
 //返回当前结点中存放的对象
 public Object getElem();
 //将对象obj存入当前结点。并返回此前的内容
 public Object setElem(Object obj);
 //返回当前结点的父结点
 public TreeLinkedList getParent();
 //返回当前结点的长子
 public TreeLinkedList getFirstChild();
 //返回当前结点的最大弟弟
 public TreeLinkedList getNextSibling();
 //返回当前结点后代元素的数目，即以当前结点为根的子树的规模
 public int getSize();
 //返回当前结点的高度
 public int getHeight();
 //返回当前结点的深度
 public int getDepth();
}

package dankui.com;
/*基于链表的树实现*/
public class TreeLinkedList implements Tree{
 

 private Object element; //树根结点
    private TreeLinkedList parent,firstChild,nextSibling;
   
    public TreeLinkedList() {
  super();
 }

 public TreeLinkedList(Object element, TreeLinkedList parent,
   
   TreeLinkedList firstChild, TreeLinkedList nextSibling) {
  super();
  this.element = element;
  this.parent = parent;
  this.firstChild = firstChild;
  this.nextSibling = nextSibling;
 }
 
 @Override
 public Object getElem() {
  // TODO Auto-generated method stub
  return element;
 }

 @Override
 public Object setElem(Object obj) {
  // TODO Auto-generated method stub
  this.element = obj;
  return element;
 }

 @Override
 public TreeLinkedList getParent() {
  // TODO Auto-generated method stub
  return parent;
 }

 @Override
 public TreeLinkedList getFirstChild() {
  // TODO Auto-generated method stub
  return firstChild;
 }

 @Override
 public TreeLinkedList getNextSibling() {
  // TODO Auto-generated method stub
  return nextSibling;
 }

 @Override
 public int getSize() {
  // TODO Auto-generated method stub
  int size = 1;
  TreeLinkedList subtree = firstChild;
  while(null != subtree){
   size += subtree.getSize();
   subtree = subtree.getNextSibling();
  }
  return size;
 }

 @Override
 public int getHeight() {
  // TODO Auto-generated method stub
  int height = -1;
  TreeLinkedList subtree = firstChild;
  while(null != subtree){
   height = Math.max(height, subtree.getHeight());
   subtree = subtree.getNextSibling();
  }
  return height+1;
  
 }

 @Override
 public int getDepth() {
  // TODO Auto-generated method stub
  int depth = 0;
  TreeLinkedList p = parent;
  while(null != p){
   depth++;
      p = p.getParent();
  }
  return depth;
 }
 
}