工学1号馆

home

« | 返回首页 | »

二叉排序树

By Wu Yudong on October 19, 2015

使用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

No comments yet.
To verify that you are human, please fill in "七"(required)