二叉树的排序（转摘）

import java.util.NoSuchElementException;


public class BST {
	public Integer data;
	public BST left;
	public BST right;
	
	public BST(Integer data){
		this.data = data;
	}
	
	//add
	public void add(Integer number){
		if(number < data){
			add(number, this, this.left, 0);
		}else{
			add(number, this, this.right, 1);
		}
	}
	
	private void add(Integer number, BST father, BST child, int tag){
		if(child == null){
			child = new BST(number);
			if(tag == 0){
				father.setLeft(child);
			}else{
				father.setRight(child);
			}
		}else{
			if(number < child.data){
				// add to left
				add(number, child, child.left, 0);
			}else{
				// add to right
				add(number, child, child.right, 1);
			}
		}
	}

	//find
	public BST find(Integer number){
		return find(number, this);
	}
	
	private BST find(Integer number, BST tree){
		if(tree == null){
			throw new NoSuchElementException("no such element in the binary search tree");
		}
		if(number < tree.data){
			return find(number, tree.left);
		}else if(number > tree.data){
			return find(number, tree.right);
		}else
			return tree;
	}
	
	//find minimum
	public BST findMin(BST tree){
		if(tree == null){
			throw new NoSuchElementException("no such element in the binary search tree");
		}else if(tree.left == null){
			return tree;
		}else
			return findMin(tree.left);
	}
	
	//find maximal
	public BST findMax(BST tree){
		if(tree == null){
			throw new NoSuchElementException("no such element in the binary search tree");
		}else if(tree.right == null){
			return tree;
		}else
			return findMax(tree.right);
	} 
	
	//remove
	public BST remove(Integer number, BST tree){
		BST delete = null;
		if (tree == null){
			throw new IndexOutOfBoundsException("tree size is 0");
		} else if(number < tree.data){
			// go left
			tree.left = remove(number, tree.left);
		} else if (number > tree.data) {
			// go right
			tree.right = remove(number, tree.right);
			// found element to be remove(recursion)
		} else if(tree.left != null && tree.right != null) {
			delete = findMin(tree.right);
			tree.setData(delete.data);
			tree.setRight(remove(tree.data,tree.right));
			delete = null;
			// one or zero child
		} else {
			delete = tree;
			if(tree.left == null){
				tree = tree.right;
			}else if(tree.right == null){
				tree = tree.left;
			}
			delete = null;
		}
		return tree;
	}
	
	//get depth
	public int getDepth(BST root){
		if( root == null){
			return 0;
		}else{
			return 1 + Math.max(getDepth(root.left), getDepth(root.right));
		}
	}
	
	//print previous order 先序遍历 中->左->右
	public void printPreOrder(){
		System.out.print(data + " ");
		if(left != null)
			left.printPreOrder();
		if(right != null)
			right.printPreOrder();
	}
	//print middle order 中序遍历 左->中->右
	public void printMidOrder(){
		if(left != null)
			left.printMidOrder();
		System.out.print(data + " ");
		if(right != null)
			right.printMidOrder();
	}
	//print post order 后序遍历 左->右->中
	public void printPostOrder(){
		if(left != null)
			left.printPostOrder();
		if(right != null)
			right.printPostOrder();
		System.out.print(data + " ");
	}
	//print level
	public void printLevelOrder(int flag){
		if(flag == 0)
			System.out.print(data + " ");
		if(left != null)
			System.out.print(left.data + " ");
		if(right != null)
			System.out.print(right.data + " ");
		
		if(left != null)
			left.printLevelOrder(1);
		if(right != null)
			right.printLevelOrder(1);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BST tree = new BST(37);
		tree.add(24);
		tree.add(42);
		tree.add(32);
		tree.add(7);
		tree.add(40);
		tree.add(2);
		tree.add(42);
		tree.add(120);
		System.out.println("Depth is: "+tree.getDepth(tree));
		System.out.print("Privious: ");
		tree.printPreOrder();
		System.out.println();
		
		System.out.print("Middle  : ");
		tree.printMidOrder();
		System.out.println();
		
		System.out.print("Post    : ");
		tree.printPostOrder();
		System.out.println();
		
		System.out.print("Level   : ");
		tree.printLevelOrder(0);
		System.out.println();
		
	}

	public Integer getData() {
		return data;
	}
	public void setData(Integer data) {
		this.data = data;
	}
	public BST getLeft() {
		return left;
	}
	public void setLeft(BST left) {
		this.left = left;
	}
	public BST getRight() {
		return right;
	}
	public void setRight(BST right) {
		this.right = right;
	}
}

转载于:https://my.oschina.net/huichen/blog/415153