0001 /* 0002 * 基于链表实现树结构 0003 */ 0004 0005 package dsa; 0006 0007 public class TreeLinkedList implements Tree { 0008 private Object element;//树根节点 0009 private TreeLinkedList parent, firstChild, nextSibling;//父亲、长子及最大的弟弟 0010 0011 //(单节点树)构造方法 0012 public TreeLinkedList() 0013 { this(null, null, null, null); } 0014 0015 //构造方法 0016 public TreeLinkedList(Object e, TreeLinkedList p, TreeLinkedList c, TreeLinkedList s) { 0017 element = e; 0018 parent = p; 0019 firstChild = c; 0020 nextSibling = s; 0021 } 0022 0023 /*---------- Tree接口中各方法的实现 ----------*/ 0024 //返回当前节点中存放的对象 0025 public Object getElem() 0026 { return element; } 0027 0028 0029 //将对象obj存入当前节点,并返回此前的内容 0030 public Object setElem(Object obj) 0031 { Object bak = element; element = obj; return bak; } 0032 0033 //返回当前节点的父节点;对于根节点,返回null 0034 public TreeLinkedList getParent() 0035 { return parent; } 0036 0037 //返回当前节点的长子;若没有孩子,则返回null 0038 public TreeLinkedList getFirstChild() 0039 { return firstChild; } 0040 0041 //返回当前节点的最大弟弟;若没有弟弟,则返回null 0042 public TreeLinkedList getNextSibling() 0043 { return nextSibling; } 0044 0045 //返回当前节点后代元素的数目,即以当前节点为根的子树的规模 0046 public int getSize() { 0047 int size = 1;//当前节点也是自己的后代 0048 TreeLinkedList subtree = firstChild;//从长子开始 0049 while (null != subtree) {//依次 0050 size += subtree.getSize();//累加 0051 subtree = subtree.getNextSibling();//所有孩子的后代数目 0052 } 0053 return size;//即可得到当前节点的后代总数 0054 } 0055 0056 //返回当前节点的高度 0057 public int getHeight() { 0058 int height = -1; 0059 TreeLinkedList subtree = firstChild;//从长子开始 0060 while (null != subtree) {//依次 0061 height = Math.max(height, subtree.getHeight());//在所有孩子中取最大高度 0062 subtree = subtree.getNextSibling(); 0063 } 0064 return height + 1; //即可得到当前节点的高度 0065 } 0066 0067 //返回当前节点的深度 0068 public int getDepth() { 0069 int depth = 0; 0070 TreeLinkedList p = parent;//从父亲开始 0071 while (null != p) {//依次 0072 depth++; p = p.getParent();//访问各个真祖先 0073 } 0074 return depth;//真祖先的数目,即为当前节点的深度 0075 } 0076 }