# 工学1号馆

home

## 二叉排序树

Wu Yudong    October 19, 2015     Algorithm   605

### 定义

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

### 实现二叉排序树

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();
}

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;
}
}


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) {
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);
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