二叉搜索树描述

/*
 *  二叉查找树
 */
public class BinarySearchTree {
	//根节点
	private TreeNode root = null;
	
	public static void main(String[] args) {
		BinarySearchTree bst = new BinarySearchTree();
		bst.insertTreeNode(new TreeNode(12));
		bst.insertTreeNode(new TreeNode(5));
		bst.insertTreeNode(new TreeNode(2));
		bst.insertTreeNode(new TreeNode(9));
		bst.insertTreeNode(new TreeNode(18));
		bst.insertTreeNode(new TreeNode(15));
		bst.insertTreeNode(new TreeNode(17));
		bst.insertTreeNode(new TreeNode(19));
		//打印生成的树
		bst.printTree();
		//打印最大值和最小值
		System.out.println(bst.searchMaximum(bst.root).key);
		System.out.println(bst.searchMinimum(bst.root).key);
		//插入数据
		bst.insertTreeNode(new TreeNode(13));
		bst.printTree();
		//删除数据
		bst.deleteTreeNode(bst.searchTreeNode(bst.root, 12));
		bst.printTree();		
	}
	
	//构造函数
	public BinarySearchTree() {
		this.root = null;
	}
	
	//遍历二叉树
	private void traverseTree(TreeNode x) {
		if(x != null) {
			traverseTree(x.left);
			System.out.print(x.key + " ");
			traverseTree(x.right);
		}
	}
	private void printTree() {
		traverseTree(root);
		System.out.println();
	}
	
	//查找键值为key的树节点
	private TreeNode searchTreeNode(TreeNode x,int key) {
		while(x != null && x.key != key) {
			if(key < x.key) {
				x = x.left;
			} else {
				x = x.right;
			}
		}
		return x;
	}
	
	//获取最小键值
	private TreeNode searchMinimum(TreeNode x) {
		while(x.left != null) {
			x = x.left;
		}
		return x;
	}
	
	//获取最大键值
	private TreeNode searchMaximum(TreeNode x) {
		while(x.right != null) {
			x = x.right;
		}
		return x;
	}
	
	//插入一个键值为key的树节点
	private void insertTreeNode(TreeNode z) {
		
		TreeNode y = null;
		TreeNode x = root;
		while(x != null) {
			y = x;
			if(z.key < x.key) {
				x = x.left;
			} else {
				x = x.right;
			}		
		}
		z.parent = y;
		if(y == null) {
			root = z;
		} else if(z.key < y.key) {
			y.left = z;
		} else {
			y.right = z;
		}
	}
	
	private void deleteTreeNode(TreeNode z) {
		if(z.left == null) {
			transplant(z,z.right);
		} else if(z.right == null) {
			transplant(z,z.left);
		} else {
			TreeNode y = searchMinimum(z.right);
			if(y.parent != z) {
				transplant(y,y.right);
				y.right = z.right;
				z.right.parent = y;
			}
			transplant(z,y);
			y.left = z.left;
			z.left.parent = y;
		}
	}
	
	private void transplant(TreeNode u,TreeNode v) {
		if(u.parent == null) {
			root = v;
		} else if(u == u.parent.left) {
			u.parent.left = v;
		} else {
			u.parent.right = v;
		}
		if(v != null) {
			v.parent = u.parent;
		}
	}
	
	//树节点
	private static class TreeNode {	
		TreeNode left = null;
		TreeNode right = null;
		TreeNode parent = null;
		int key = 0;
		
		public TreeNode(int key) {
			this.key = key;
		}	
	}
}

二叉搜索树描述

原文：http://blog.csdn.net/q389281541/article/details/44835189