0001 /* 0002 * 基于链表式BST实现的词典结构 0003 * 基于BinTree进行扩充 0004 */ 0005 0006 package dsa; 0007 0008 public class BSTree extends BinTree_LinkedList implements Dictionary { 0009 /**************************** 实例变量 ****************************/ 0010 protected Comparator C;//比较器 0011 protected BinTreePosition lastV;//最后操作的节点,以便AVL树、伸展树重平衡 0012 0013 /**************************** 构造方法 ****************************/ 0014 public BSTree() 0015 { this(null, new ComparatorDefault()); } 0016 0017 public BSTree(BinTreePosition r) 0018 { this(r, new ComparatorDefault()); } 0019 0020 public BSTree(BinTreePosition r, Comparator c) 0021 { root = r; C = c; } 0022 0023 /**************************** 词典方法 ****************************/ 0024 //若词典中存在以key为关键码的条目,则返回其中的一个条目;否则,返回null 0025 public Entry find(Object key) { 0026 if (isEmpty()) return null; 0027 BSTreeNode u = binSearch((BSTreeNode)root, key, C); 0028 return (0 == C.compare(key, u.getKey())) ? (Entry)u.getElem() : null; 0029 } 0030 0031 //返回由关键码为key的条目组成的迭代器 0032 public Iterator findAll(Object key) { 0033 List s = new List_DLNode(); 0034 finAllNodes((BSTreeNode)root, key, s, C); 0035 return s.elements(); 0036 } 0037 0038 //插入条目(key, value),并返回该条目 0039 //lastV指示被插入的节点 0040 public Entry insert(Object key, Object value) { 0041 Entry e = new EntryDefault(key, value);//创建新的元素 0042 if (isEmpty()) {//插入根节点的情况 0043 lastV = root = new BSTreeNode(e, null, true, null, null);//插入新节点 0044 } else {//插入一般节点的情况 0045 BSTreeNode p = (BSTreeNode)root;//从根节点开始,查找可插入位置 0046 boolean asLeftChild;//表示新节点是否作为p的左孩子插入 0047 while(true) {//不断地 0048 p = binSearch(p, key, C);//查找关键码为key的节点,直至 0049 if (C.compare(key, p.getKey()) < 0)//查找失败于无左孩子节点,或 0050 { asLeftChild = true; break; } 0051 else if (C.compare(key, p.getKey()) > 0)//查找失败无右孩子节点,或 0052 { asLeftChild = false; break; } 0053 else if (!p.hasLChild())//查找成功,且可作为左孩子插入,或 0054 { asLeftChild = true; break; } 0055 else if (!p.hasRChild())//查找成功,且可作为右孩子插入,或 0056 { asLeftChild = false; break; } 0057 else//否则 0058 p = (BSTreeNode)p.getLChild();//在左子树中继续查找(当然,在右子树中查找亦可) 0059 }//至此,新节点可以作为p的孩子插入,插入的方向由childType确定 0060 lastV = new BSTreeNode(e, p, asLeftChild, null, null);//插入新节点 0061 }//else 0062 return e; 0063 } 0064 0065 //若词典中存在以key为关键码的条目,则摘除这样的一个节点,并返回其中存放的条目;否则,返回null 0066 //lastV指示被删除节点的父亲 0067 public Entry remove(Object key) { 0068 if (isEmpty()) return null;//空树 0069 BinTreePosition v = binSearch((BSTreeNode)root, key, C);//查找 0070 if (0 != C.compare(key, ((BSTreeNode)v).getKey())) return null;//若查找失败,则返回null 0071 //至此查找必成功,v为待删除节点 0072 if (v.hasLChild()) {//若v的左子树非空,则 0073 BinTreePosition w = v.getPrev();//在v的左子树中找出其直接前驱w 0074 w.setElem(v.setElem(w.getElem()));//交换v和u的数据对象 0075 v = w;//这样,相当于删除w 0076 } 0077 //至此,v至多只有一个孩子 0078 //下面,删除v,代之以其孩子 0079 lastV = v.getParent();//取待删除节点v的父亲 0080 BinTreePosition u = v.hasLChild() ? v.getLChild() : v.getRChild();//取v的孩子u 0081 if (null == lastV)//若v恰为树根 0082 { if (null != u) u.secede(); root = u; }//将u作为树根 0083 else {//否则 0084 if (v.isLChild())//若v是p的左孩子,则 0085 { v.secede(); lastV.attachL(u); }//摘出v,将u作为p的左孩子 0086 else//否则 0087 { v.secede(); lastV.attachR(u); }//摘出v,将u作为p的右孩子 0088 } 0089 return (Entry) v.getElem();//返回被删除节点中存放的的元素 0090 } 0091 0092 //返回词典中所有条目的一个迭代器 0093 public Iterator entries() { 0094 List list = new List_DLNode(); 0095 concatenate(list, (BSTreeNode)root); 0096 return list.elements(); 0097 } 0098 0099 /**************************** 辅助方法 ****************************/ 0100 //在以v为根的子树中查找关键码为key的节点(假设该子树不为空) 0101 // 若找到,则返回该节点 0102 // 否则,返回被访问的最后一个节点 0103 //为了确定是否成功,上层方法需要再检查一次返回节点的关键码 0104 protected static BSTreeNode binSearch(BSTreeNode v, Object key, Comparator c) { 0105 BSTreeNode u = v;//当前节点 0106 while (true) {//不断地 0107 int comp = c.compare(key, u.getKey());//将当前节点与目标关键码做比较 0108 if (comp < 0)//若目标关键码更小,则 0109 if (u.hasLChild())//若u有左孩子 0110 u = (BSTreeNode)u.getLChild();//递归查找左子树,或 0111 else 0112 return u;//终止于无左孩子节点 0113 else if (comp > 0)//若目标关键码更大,则 0114 if (u.hasRChild())//u有右孩子 0115 u = (BSTreeNode)u.getRChild();//递归查找右子树,或 0116 else 0117 return u;//终止于无右孩子节点 0118 else 0119 return u;//查找命中 0120 } 0121 } 0122 0123 //在以v为根节点的(子)树中,递归地找出关键码为key的所有节点 0124 //这些节点被组织为一个列表(借此可以生成一个迭代器) 0125 protected static void finAllNodes(BSTreeNode v, Object k, List s, Comparator c) { 0126 if (null == v) return;//递归基:空树 0127 int comp = c.compare(k, v.getKey()); 0128 if (0 >= comp) finAllNodes((BSTreeNode)v.getLChild(), k, s, c);//查找左子树 0129 if (0 == comp) s.insertLast(v);//命中 0130 if (0 <= comp) finAllNodes((BSTreeNode)v.getRChild(), k, s, c);//查找右子树 0131 } 0132 0133 //将v的所有后代节点(中存放的条目)组织为一个列表(借此可以生成一个迭代器) 0134 protected static void concatenate(List list, BSTreeNode v) { 0135 if (null == v) return; 0136 concatenate(list, (BSTreeNode) v.getLChild()); 0137 list.insertLast(v.getElem()); 0138 concatenate(list, (BSTreeNode) v.getRChild()); 0139 } 0140 }