使用java泛型实现二叉排序树（Binary Sort Tree）
定义
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。
实现二叉排序树
定义一个接口(tree):
public interface Tree<E extends Comparable<E>> {
public boolean search(E e);
public boolean insert(E e);
public boolean delete(E e);
public void inorder();
public void postorder();
public void preorder();
public int getSize();
public boolean isEmpty();
public java.util.Iterator iterator();
}
定义一个抽象类(AbstractTree)继承tree接口:
public abstract class AbstractTree<E extends Comparable<E>> implements Tree<E>{
public void inorder() {
}
public void postorder() {
}
public void preorder() {
}
public boolean isEmpty() {
return getSize() == 0;
}
public java.util.Iterator iterator() {
return null;
}
}
定义一个BinaryTree类继承抽象类：
import java.util.*;
public class BinaryTree<E extends Comparable<E>> extends AbstractTree<E>{
protected TreeNode<E> root;
protected int size = 0;
public BinaryTree() {
}
public BinaryTree (E[] objects) {
for(int i = 0; i < objects.length; i++) {
insert(objects[i]);
}
}
public boolean search(E e) {
TreeNode<E> current = root;
while(current != null) {
if(e.compareTo(current.element) < 0) {
current = current.left;
} else if(e.compareTo(current.element) > 0) {
current = current.right;
} else
return true;
}
return false;
}
public boolean insert(E e) {
if(root == null)
root = creaNewNode(e);
else {
TreeNode<E> parent = null;
TreeNode<E> current = root;
while(current != null) {
if(e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
return false;
}
}
if(e.compareTo(parent.element) < 0)
parent.left = creaNewNode(e);
else
parent.right = creaNewNode(e);
}
size++;
return true;
}
protected TreeNode<E> creaNewNode(E e) {
return new TreeNode<E>(e);
}
public void inorder() {
inorder(root);
}
public void postorder() {
postorder(root);
}
public void preorder() {
preorder(root);
}
public boolean isEmpty() {
return getSize() == 0;
}
protected void inorder(TreeNode<E> root) {
if(root == null)
return;
else {
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
}
protected void postorder(TreeNode<E> root) {
if(root == null) return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
protected void preorder(TreeNode<E> root) {
if(root == null) return;
System.out.print(root.element + " ");
preorder(root.left);
preorder(root.right);
}
public static class TreeNode<E extends Comparable<E>> {
//内部类
E element;
TreeNode<E> left;
TreeNode<E> right;
public TreeNode(E e) {
element = e;
}
}
public int getSize() {
return size;
}
public TreeNode getRoot() {
return root;
}
//返回从根节点到指定节点的路径
public ArrayList<TreeNode<E>> path(E e) {
ArrayList<TreeNode<E>> list = new ArrayList<TreeNode<E>>();
TreeNode<E> current = root;
while(current != null) {
list.add(current);
if(e.compareTo(current.element) < 0) {
current = current.left;
} else if(e.compareTo(current.element) > 0){
current = current.right;
} else {
break;
}
}
return list;
}
public boolean delete(E e) {
TreeNode<E> parent = null;
TreeNode<E> current = root;
while(current != null) {
if(e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if(e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
break;
}
}
if(current == null) {
return false;
}
if(current.left == null) {
if(parent == null) {
root = current.right;
} else {
if(e.compareTo(parent.element) < 0)
parent.left = current.right;
else
parent.right = current.right;
}
} else {
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
while(rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}
current.element = rightMost.element;
if(parentOfRightMost.right == rightMost)
parentOfRightMost.right = rightMost.left;
else
parentOfRightMost.left = rightMost.left;
}
size--;
return true;
}
public Iterator iterator() {
return InorderIterator();
}
public Iterator InorderIterator() {
return new InorderIterator();
}
class InorderIterator implements Iterator {
ArrayList<E> list = new ArrayList<E>();
private int current = 0;
public InorderIterator() {
inorder();
}
public void inorder() {
inorder(root);
}
public void inorder(TreeNode<E> root) {
if(root == null) return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
public boolean hasNext() {
if(current < list.size())
return true;
return false;
}
public Object next() {
return list.get(current++);
}
public void remove() {
delete(list.get(current));
list.clear();
inorder();
}
}
public void clear() {
root = null;
size = 0;
}
}
实例运行主程序：
import java.util.ArrayList;
public class TestBinaryTree {
public static void main(String[] args) {
BinaryTree<String> tree = new BinaryTree<String>();
tree.insert("wu");
tree.insert("wang");
tree.insert("li");
tree.insert("zhang");
tree.insert("zhou");
tree.insert("he");
System.out.print("InOrder (sorted): ");
tree.inorder();
System.out.print("\nPostOrder (sorted): ");
tree.postorder();
System.out.print("\nPreOrder (sorted): ");
tree.preorder();
System.out.println("\nThe number of nodes is " + tree.getSize());
System.out.println("\nIs wu in the tree? " + tree.search("zhou"));
System.out.print("\nA path from the root to wu is: ");
ArrayList<BinaryTree.TreeNode<String>> path = tree.path("zhou");
for(int i = 0; path != null && i < path.size(); i++) {
System.out.print(path.get(i).element + " ");
}
}
}
运行结果如下：
InOrder (sorted): he li wang wu zhang zhou
PostOrder (sorted): he li wang zhou zhang wu
PreOrder (sorted): wu wang li he zhang zhou
The number of nodes is 6
Is wu in the tree? true
A path from the root to wu is: wu zhang zhou
Comments