0001 /* 0002 * 基于秩实现的完全二叉树节点 0003 */ 0004 0005 package dsa; 0006 0007 public class ComplBinTreeNode_Rank extends BinTreeNode implements BinTreePosition { 0008 private Vector T;//所属的树 0009 private int rank;//在所属树中的秩 0010 private Object element;//存放的对象 0011 0012 //构造函数 0013 public ComplBinTreeNode_Rank (Vector t, Object obj) { 0014 element = obj; 0015 T = t; 0016 rank = T.getSize(); 0017 T.insertAtRank(rank, this); 0018 } 0019 0020 //返回当前节点中存放的对象 0021 public Object getElem() 0022 { return element; } 0023 //将对象obj存入当前节点,并返回此前的内容 0024 public Object setElem(Object obj) 0025 { Object bak = element; element = obj; return bak; } 0026 0027 //判断是否有父亲(为使代码描述简洁) 0028 public boolean hasParent() 0029 { return (0 != rank) ? true : false; } 0030 //返回当前节点的父节点 0031 public BinTreePosition getParent() 0032 { return hasParent() ? (BinTreePosition) T.getAtRank((rank - 1) / 2) : null; } 0033 0034 //判断是否有左孩子(为使代码描述简洁) 0035 public boolean hasLChild() 0036 { return (1 + rank * 2 < T.getSize()) ? true : false; } 0037 //返回当前节点的左孩子 0038 public BinTreePosition getLChild() 0039 { return hasLChild() ? (BinTreePosition) (T.getAtRank(1 + rank * 2)) : null; } 0040 0041 //判断是否有右孩子(为使代码描述简洁) 0042 public boolean hasRChild() 0043 { return (2 + rank * 2 < T.getSize()) ? true : false; } 0044 //返回当前节点的右孩子 0045 public BinTreePosition getRChild() 0046 { return hasRChild() ? (BinTreePosition) (T.getAtRank(2 + rank * 2)) : null; } 0047 0048 //返回当前节点后代元素的数目 0049 public int getSize() { 0050 int size = 1; 0051 if (hasLChild()) size += getLChild().getSize(); 0052 if (hasRChild()) size += getRChild().getSize(); 0053 return size; 0054 } 0055 0056 //返回当前节点的高度 0057 public int getHeight() { 0058 int hL = hasLChild() ? getLChild().getHeight() : -1; 0059 int hR = hasRChild() ? getRChild().getHeight() : -1; 0060 return 1 + Math.max(hL, hR); 0061 } 0062 0063 //返回当前节点的深度 0064 public int getDepth() { 0065 return hasParent() ? 1 + getParent().getDepth() : 0; 0066 } 0067 }