二分查找树（BST）源码

1.BST (Binary Search Tree)

package BinarySearchTree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

import BinarySearchTree.BST.TreeNode;

/**
 * Binary Search Tree
 * 二分查找树
 */
public class BST <E extends Comparable<E>> extends AbstractTree<E>{
	// 内部类，定义一个节点
	public static class TreeNode<E extends Comparable<E>>{
		protected E element;
		protected TreeNode<E> left;
		protected TreeNode<E> right;
		
		public TreeNode(E e){
			this.element=e;
		}
	}
	
	protected TreeNode<E> root;
	protected int size;
	
	public BST(){}
	
	public BST(E[] arr) {
		for (int i = 0; i < arr.length; i++) {
			insert(arr[i]);
		}
	}
	@Override
	public boolean search(E e) {
		TreeNode<E> current = root;
		while(current!=null){
			if (current.element.compareTo(e) > 0) {
				current=current.left;
			}
			else if(current.element.compareTo(e) < 0){
				current=current.right;
			}
			else {
				return true;
			}
		}
		
		return false;
	}

	@Override
	public boolean insert(E e) {
		if (root==null) {
			root = new TreeNode<>(e);
		}
		else
		{	
			TreeNode<E> parent = null;
			TreeNode<E> current = root;
			  while(current!=null){
				  if (e.compareTo(current.element) > 0) {
					parent = current;
					current = current.right;
				}
				  else if (e.compareTo(current.element) < 0) {
					  parent = current;
					  current = current.left;
				}
				  else {
					return false;
				}	
			  }
			  if (e.compareTo(parent.element) > 0) {
					parent.right =  new TreeNode<E>(e);
				}
				  else {
					parent.left =  new TreeNode<E>(e);
				}
		}
		size++;
		return true;
	}
	
	
	@Override//删除一个几点，需要找到该节点左子树中最大的节点 来代替。   或者用该节点右子树中最小的节点代替
	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.right;
			} else if (e.compareTo(current.element) < 0) {
				parent = current;
				current = current.left;
			} else
				break;
		}

		if (current == null) {
			return false;
		}

		if (current.left == null) {
			if (parent == null) {
				root = current.right;
				return true;
			}

			if (parent.left == current) {
				parent.left = current.right;
			} else {
				parent.right = current.right;
			}
			return true;
		} 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 == current) {
				parentOfRightMost.left = rightMost.left;
			} else {
				parentOfRightMost.right = rightMost.left;
			}
		}

		size--;
		return true;
	}

	@Override
	public int getSieze() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public Iterator<E> iterator() {
			
		return new InorderIterator();
	}
	
	private class InorderIterator implements Iterator<E>{
		private ArrayList<E> list = new ArrayList<>();
		private int current = 0;
		public  InorderIterator(){
			inorder();
		}
		private void inorder(){
			inorder(root);
		}
		private void inorder(TreeNode<E> t){
			inorder(t.left);
			list.add(t.element);
			inorder(t.right);
		}
		
		public boolean hasNext(){
			if (current<list.size()) {
				return true;
			}
			return false;
		}
		@Override
		public E next() {
			return list.get(current++);
		}
		public void remove(){
			delete(list.get(current));
			list.clear();
			inorder();
		}
		public void clear(){
			root=null;
			size=0;
		}
	}
	
	//中序遍历
 	public void inorder() {
		inorder(root);
	}
	
	public void inorder(TreeNode<E> rootNode) {
		if (rootNode==null) {
			return;
		}
		inorder(rootNode.left);
		System.out.print(rootNode.element+" ");
		inorder(rootNode.right);
	}
	
	//后序遍历
	public void postorder() {
		postorder(root);	
	}
	
	public void postorder(TreeNode<E> rootNode) {
		if (rootNode==null) {
			return;
		}
		postorder(rootNode.left);
		postorder(rootNode.right);				
		System.out.print(rootNode.element+" ");
	}
	
	//前序遍历，深度优先
	public void preorder() {
		preorder(root);
	}
	
	public void preorder(TreeNode<E> rootNode) {
		if (rootNode==null) {
			return;
		}
		System.out.print(rootNode.element+" ");
		preorder(rootNode.left);
		preorder(rootNode.right);
		
	}
	
	public void levelOrder(){
		levelOrder(root);
	}
	
	
	//层序遍历。广度优先遍历
	public void levelOrder(TreeNode<E> rootNode){
		Queue<TreeNode<E>> q = new LinkedList<TreeNode<E>>();
		q.offer(rootNode);
		while (!q.isEmpty()) {
			TreeNode<E> node  = q.peek();
			q.poll();
			System.out.print(node.element +" ");
			if(node.left!=null){
				q.offer(node.left);
			}
			if (node.right!=null) {
				q.offer(node.right);
			}
			
		}
	}
	
	public TreeNode<E> getRoot(){
		return root;	
	}
	
	public ArrayList<TreeNode<E>> path(E e){
		ArrayList<TreeNode<E>> list = new ArrayList<>();
		TreeNode<E> current = root;
		while(current!=null){
			list.add(current);
			if (e.compareTo(current.element)>0) {
				current=current.right;
			}
			else if (e.compareTo(current.element)<0) {
				current=current.left;
			}
			else {
				break;
			}
		}
		return list;
	}
}

2. AbstractTree

package BinarySearchTree;

public abstract class AbstractTree<E>  implements Tree<E>{

	@Override
	public void inorder() {
		
		
	}

	@Override
	public void postorder() {
		
		
	}

	@Override
	public void preorder() {
		
		
	}

	@Override
	public boolean isEmpty() {
		return getSieze()==0;
	}
	
}

3.Tree

package BinarySearchTree;
/**
 *2020/05/08
 */


public interface Tree<E> extends Iterable<E> {
	//查找一个元素
	public boolean search(E e);
	
	//插入一个元素
	public boolean insert(E e);
	
	//删除一个元素
	public boolean delete(E e);
	
	//中序遍历 1 + 2
	public void inorder();
	
	//后序遍历 1 2 +
	public void postorder();
	
	//前序遍历 + 1 2 (深度优先遍历)
	public void preorder();
	
	//返回树中节点数
	public int getSieze();
	
	//返回树是否为空
	public boolean isEmpty();
	
}

4.测试

package BinarySearchTree;

import java.util.ArrayList;

import BinarySearchTree.BST.TreeNode;

public class TestBST {
	public static void main(String[] args) {
		BST<String> tree = new BST<>();
		tree.insert("George"); //首字母ASCII -'A' = 6
		tree.insert("Michael");// 12
		tree.insert("Tom");// 19
		tree.insert("Adam");// 0
		tree.insert("Jones");// 9
		tree.insert("Peter");// 15
		tree.insert("Daniel");// 3
		
		//Traverse tree
		
		System.out.print("Inorder:   " );
		tree.inorder();
		System.out.println();
		System.out.print("Postorder:   ");
		tree.postorder();
		System.out.println();
		System.out.print("Preorder:   ");
		tree.preorder();
		System.out.println();
		System.out.print("Levelorder:   ");
		tree.levelOrder();
		System.out.println();
		System.out.println("treeSize:   "+tree.size);
		
		System.out.println(tree.search("Tom"));
		System.out.print("A path from the root to Peter is ：    ");
		ArrayList<TreeNode<String>> path = tree.path("Peter");
		for (TreeNode<String> treeNode : path) {
			System.out.print(treeNode.element+"-->");			
		}
		System.out.print("null");
		
		Integer[] numbers = {2,4,8,9,3,5,7,10,99,56,77,1};
		BST bst = new BST(numbers);
		System.out.println("\ninorder（Sorted）");
		bst.inorder();
	}
}