二叉排序树的实现
最适合用STree排序的是不可变类，不可变类的主要特征是它的对象的属性不能被修改．public class Customerimplements Comparable<Object>{private final String name;private final int age;...}
二叉排序树操作的复杂度
最好情况: 完全树
最坏情况: 在二叉排序树为退化树时，add()和remove()处于最坏情况,相当于一个链表,可以通过红黑树消除最坏情况．
Iterator接口
package BinarySearchTree;public interface Iterator<T> {public boolean hasNext();public T next();public void remove();}
package BinarySearchTree;import java.util.ConcurrentModificationException;import java.util.NoSuchElementException;public class STree<T> implements Cloneable {/**结点内部类*/private static class STNode<T> {T nodeValue;STNode<T> left, right, parent;/**结点类构造函数*/public STNode(T item, STNode<T> parentNode) {nodeValue = item;left = null;right = null;parent = parentNode;}}/**二叉搜索树类成员变量*/private STNode<T> root;private int treeSize;private int modCount;/**二叉搜索树类构造函数*/public STree() {root = null;treeSize = 0;modCount = 0;}/**插入方法*/public boolean add(T item) {STNode<T> t = root, parent = null, newNode;int orderValue = 0;// 循环终止条件在一个空的子树上while(t != null) {// 更新父结点的引用parent = t;// 比较item与当前结点的值orderValue = ((Comparable<T>)item).compareTo(t.nodeValue);// 比较item与当前结点的值,小于零往左走,否则向右走，等于零将不能插入新值if(orderValue == 0)return false;else if(orderValue < 0)t = t.left;elset = t.right;}// 创建新结点newNode = new STNode<T>(item, parent);// 下面几句是父结点与子结点的连接操作if(parent == null)// 这是第一个被添加的结点，使它成为根结点root = newNode;else if(orderValue < 0)// 连接新结点作为父结点的左孩子parent.left = newNode;else// 连接新结点作为父结点的右孩子parent.right = newNode;// 增加tree size and modCounttreeSize++;modCount++;return true;}/**定位结点*/public T find(T item) {STNode<T> t = findNode(item);T value = null;if (t != null)value = t.nodeValue;return value;}private STNode<T> findNode(Object item) {STNode<T> t = root;int orderValue;while(t != null) {orderValue = ((Comparable<T>)item).compareTo(t.nodeValue);if(orderValue == 0)return t;else if(orderValue < 0)t = t.left;elset = t.right;}return null;}/**删除结点*/public boolean remove(Object item) {STNode<T> dNode = this.findNode(item);if(dNode == null)return false;removeNode(dNode);treeSize--;modCount++;return true;}private void removeNode(STNode<T> dNode) {if(dNode == null)return;// dNode: 待删除结点// pNode: 待删除结点的父结点// rNode: 待删除结点的替换结点STNode<T> pNode, rNode;pNode = dNode.parent;// 待删除的结点至少具有一棵空子树if(dNode.left == null || dNode.right == null) {// 找替换结点if(dNode.right == null)rNode = dNode.left;elserNode = dNode.right;if(rNode != null)rNode.parent = pNode;// 连接操作if(pNode == null)root = rNode;else if(((Comparable<T>)dNode.nodeValue).compareTo(pNode.nodeValue) < 0)pNode.left = rNode;elsepNode.right = rNode;// 待删除的结点具有两个非空子树}else {// pOfRNode: 替换结点的父结点STNode<T> pOfRNode = dNode;rNode = dNode.right;pOfRNode = dNode;while(rNode.left != null) {pOfRNode = rNode;rNode = rNode.left;}dNode.nodeValue = rNode.nodeValue;if(pOfRNode == dNode)dNode.right = rNode.right;elsepOfRNode.left = rNode.right;if(rNode.right != null)rNode.right.parent = pOfRNode;dNode = rNode;}dNode = null;}// end removeNode~/** 返回最小值*/public T first() {STNode<T> nextNode = root;if(nextNode == null)return null;while(nextNode.left != null)nextNode = nextNode.left;return nextNode.nodeValue;}/** 返回最大值*/public T last() {STNode<T> nextNode = root;if(nextNode == null)return null;while(nextNode.right != null)nextNode = nextNode.right;return nextNode.nodeValue;}/**清除树*/public void clear() {this.deleteTree(root);root = null;treeSize = 0;}private void deleteTree(STNode<T> t) {if(t != null) {deleteTree(t.left);deleteTree(t.right);t = null;}}public Object clone() {STree<T> copy = null;try {copy = (STree<T>)super.clone();}catch (CloneNotSupportedException cnse){throw new InternalError(); }copy.root = copyTree(root);// return the cloned objectreturn copy;}/**后根遍历由底向上复制一棵树*/private static<T> STNode<T> copyTree(STNode<T> t) {STNode<T> newLeft, newRight, newNode;if(t == null)return null;newLeft = copyTree(t.left);newRight = copyTree(t.right);newNode = new STNode<T>(t.nodeValue, null);newNode.left = newLeft;newNode.right = newRight;if(newLeft != null)newLeft.parent = newNode;if(newRight != null)newRight.parent = newNode;return newNode;}public boolean contains(Object item) {STNode<T> t = findNode(item);return (t == null) ? false : true;}public int size() {return treeSize;}public boolean isEmpty() {return treeSize == 0;}public Object[] toArray() {Iterator<T> iter = this.iterator();Object[] arr = new Object;int i = 0;while(iter.hasNext()) {arr = iter.next();i++;}return arr;}public String toString() {int i;String str = "[";Iterator<T> iter = this.iterator();for (i = 0; i < treeSize; i++) {str += iter.next();if(i < treeSize - 1)str += ", ";}str += "]";return str;}/**二叉搜索树跌代器的公共方法*/public Iterator<T> iterator() {return new MyIterator();}/**MyIterator内部类*/private class MyIterator implements Iterator<T> {private int expectedModCount = modCount;private STNode<T> tmp = null;private STNode<T> nextNode = null;MyIterator() {nextNode = root;if(nextNode != null) {while(nextNode.left != null)nextNode = nextNode.left;}}public boolean hasNext() {return nextNode != null;}public T next() {checkIteratorState();if(nextNode == null)throw new NoSuchElementException("Iteration has no more elements");tmp = nextNode;STNode<T> p;if(nextNode.right != null) {nextNode = nextNode.right;while(nextNode.left != null)nextNode = nextNode.left;}else {p = nextNode.parent;while(p != null && nextNode == p.right) {nextNode = p;p = p.parent;}nextNode = p;}return tmp.nodeValue;}public void remove() { // check for a missing call to next() or previous() if (tmp == null) throw new IllegalStateException( "Iterator call to next() " + "required before calling remove()"); // make sure our state is good checkIteratorState();// if lastReturned has two children, the replacement node// during deletion is nextNode. the value in nextNode// is copied to lastReturned. nextNode must be// lastReturnedif (tmp.left != null && tmp.right != null) nextNode = tmp; removeNode(tmp); // list has been modified modCount++; expectedModCount = modCount; // we did a deletion. indicate this by setting lastReturned // to null and decrementing treeSize tmp = null; treeSize--; } private void checkIteratorState() { if (expectedModCount != modCount) throw new ConcurrentModificationException( "Inconsistent iterator"); } }//end MyIterator~}//end STree~
测试类
package BinarySearchTree;// 要实现Comparable接口,然后重写compareTo方法public class Customerimplements Comparable<Object>{private String name;private int age;public Customer(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public int getAge() {return age;}public void setName(String name) {this.name = name;}public void setAge(int age) {this.age = age;}public int compareTo(Object o) {Customer other = (Customer)o;if(this.name.compareTo(other.name) > 0)return 1;if(this.name.compareTo(other.name) < 0)return -1;if(this.age > other.age)return 1;if(this.age < other.age)return -1;return 0;}public static void main(String[] args) {STree<Customer> sT = new STree<Customer>();Customer c1 = new Customer("Tom", 32);Customer c2 = new Customer("Jack", 12);Customer c3 = new Customer("Lucy", 22);sT.add(c1); sT.add(c1);sT.add(c2);sT.add(c3);Iterator<Customer> it = sT.iterator();while(it.hasNext()) {Customer c = it.next();System.out.println(c.getName() + " " + c.getAge());}Customer minAge = sT.first();System.out.println("minAge: " + minAge.getName() + " " + minAge.getAge());Customer f = sT.find(c2);f.setAge(42);System.out.println("find: " + f.getName() + " " + f.getAge());System.out.println(sT.contains(c3));sT.clear();System.out.println(sT.size());}}
页:
[1]