Java实现二进制排序树

在计算机科学中，树是非常重要的数据结构二叉排序树是，并且具有广泛的应用范围. 例如，Linux下的目录结构可以视为一棵树. 另外，树也是存储大量数据的解决方案. 方法中，二叉排序树是树的一种特殊情况二叉排序树是，它的每个节点只能有两个子节点，左子树的节点小于其父节点，右子树中的节点大于其父节点. 父节点二进制排序树在搜索中使用非常广泛，并且二进制排序树的一种变体（红色和黑色树）是Java中TreeMap和TreeSet的实现基础. 以下是二进制排序树的定义. 使用了两个类. 一个是Node类，它表示树中的节点，另一个是Name类，它表示节点的数据. Name类实现Comparable接口，以便可以比较节点. 大小.

public class BinarySearchTree{
	private Node root;
	private int size;
	
	public BinarySearchTree(Node root){
		this.root=root;
		size++;
	}
	
	public int getSize(){
		return this.size;
	}
	
	public boolean contains(Name name){
		return contains(name,this.root);
		//return false;
	}
	
	private boolean contains(Name n,Node root){
		if(root==null){
			return false;
		}
		int compare=n.compareTo(root.element);
		if(compare>0){
			if(root.right!=null){
				return contains(n,root.right);
			}else{
				return false;
			}
		}else if(compare<0){
			if(root.left!=null){
				return contains(n,root.left);
			}else{
				return false;
			}
		}else{
			return true;
		}
	}
	
	public boolean insert(Name n){
		boolean flag = insert(n,this.root);
		if(flag) size++;
		return flag;
	}
	
	private boolean insert(Name n,Node root){
		if(root==null){
			this.root=new Node(n);
			return true;
		}else if(root.element.compareTo(n)>0){
			if(root.left!=null){
				return insert(n,root.left);
			}else{
				root.left=new Node(n);
				return true;
			}
		}else if(root.element.compareTo(n)<0){
			if(root.right!=null){
				return insert(n,root.right);
			}else{
				root.right=new Node(n);
				return true;
			}
		}else{
			root.frequency++;
			return true;
		}
	}
	public boolean remove(Name name){
		root = remove(name,this.root);
		if(root != null){
			size--;
			return true;
		}
		return false;
	}
	
	private Node remove(Name name,Node root){
		int compare = root.element.compareTo(name);
		if(compare == 0){
			if(root.frequency>1){
				root.frequency--;
			}else{
				/**根据删除节点的类型，分成以下几种情况
				**①如果被删除的节点是叶子节点，直接删除
				**②如果被删除的节点含有一个子节点，让指向该节点的指针指向他的儿子节点
				**③如果被删除的节点含有两个子节点，找到左字数的最大节点，并替换该节点
				**/
				if(root.left == null && root.right == null){
					root = null;
				}else if(root.left !=null && root.right == null){
					root = root.left;
				}else if(root.left == null && root.right != null){
					root = root.right;
				}else{
					//被删除的节点含有两个子节点
					Node newRoot = root.left;
					while (newRoot.left != null){
						newRoot = newRoot.left;//找到左子树的最大节点
					}
					root.element = newRoot.element;
					root.left = remove(root.element,root.left);
				}
			}
		}else if(compare > 0){
			if(root.left != null){
				root.left = remove(name,root.left);
			}else{
				return null;
			}
		}else{
			if(root.right != null){
				root.right = remove(name,root.right);
			}else{
				return null;
			}
		}
		return root;
	}
	public String toString(){
		//中序遍历就可以输出树中节点的顺序
		return toString(root);
	}
	
	private String toString(Node n){
		String result = "";
		if(n != null){
			if(n.left != null){
				result += toString(n.left);
			}
			result += n.element + " ";
			if(n.right != null){
				result += toString(n.right);
			}
		}
		return result;
	}
	
}

在二进制排序树的操作中，删除节点最难处理，因此必须将其分为许多情况分别处理. 下面是Node类和Name类的定义:

class Node{
	public Name element;
	public Node left;
	public Node right; 
	public int frequency = 1;
	
	public Node(Name n){
		this.element=n;
	}
}
class Name implements Comparable<Name>{
	private String firstName;
	private String lastName;
	
	public Name(String firstName,String lastName){
		this.firstName=firstName;
		this.lastName=lastName;
	}
	
	public int compareTo(Name n) {
		int result = this.firstName.compareTo(n.firstName);
		return result==0?this.lastName.compareTo(n.lastName):result;
	}
	
	public String toString(){
		return firstName + "-" +lastName;
	}
}

最后，对二进制排序树进行测试:

public static void main(String[] args){
		//System.out.println("sunzhenxing");
		Node root = new Node(new Name("sun","zhenxing5"));
		BinarySearchTree bst =new BinarySearchTree(root);
		bst.insert(new Name("sun","zhenxing3"));
		bst.insert(new Name("sun","zhenxing7"));
		bst.insert(new Name("sun","zhenxing2"));
		bst.insert(new Name("sun","zhenxing4"));
		bst.insert(new Name("sun","zhenxing6"));
		bst.insert(new Name("sun","zhenxing8"));
		System.out.println(bst);
		bst.remove(new Name("sun","zhenxing2"));
		System.out.println(bst);
		bst.remove(new Name("sun","zhenxing7"));
		System.out.println(bst);
}

测试输出为:

sun-zhenxing2 sun-zhenxing3 sun-zhenxing4 sun-zhenxing5 sun-zhenxing6 sun-zhenxing7 sun-zhenxing8

sun-zhenxing3 sun-zhenxing4 sun-zhenxing5 sun-zhenxing6 sun-zhenxing7 sun-zhenxing8

sun-zhenxing3 sun-zhenxing4 sun-zhenxing5 sun-zhenxing6 sun-zhenxing8

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-208174-1.html