java二叉树查找、遍历、添加与删除

java二叉树查找、遍历、添加与删除

package com.structures.tree;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Stack;
/*
 * Binary Search Tree 
 */
public class Searchtree {
	public Integer data;
	public Searchtree left;
	public Searchtree right;
	public void setData(Integer data) {
		this.data = data;
	}
	public Searchtree(Integer number) {
		this.data = number;
	}
	public void setLeft(Searchtree left) {
		this.left = left;
	}
	public void setRight(Searchtree right) {
		this.right = right;
	}
	// add
	public void add(int number) {
		if (number <= this.data)
			add(number, this, this.left, 0);
		else
			add(number, this, this.right, 1);
	}
	private void add(int number, Searchtree father, Searchtree child, int tag) {
		if (child == null) {
			child = new Searchtree(number);
			if (tag == 0)
				father.setLeft(child);
			else
				father.setRight(child);
		} else {
			// attention: here must be child
			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 Searchtree find(int number) {
		if (number < data) {
			return find(number, this);
		} else if (number > data) {
			return find(number, this);
		} else {
			return find(number, this);
		}
	}
	private Searchtree find(int number, Searchtree tree) {
		if (tree == null)
			throw new NoSuchElementException(
					"no such element in the binary search tree");
		if (number < tree.data) {
			return find(number, tree.left.left);
		} else if (number > tree.data) {
			return find(number, tree.right);
		} else
			return tree;
	}
	// findPrevious
	private ArrayList<Searchtree> trees = new ArrayList<Searchtree>();
	private Searchtree findPrevious(int number, Searchtree tree) {
		if (tree == null)
			throw new NoSuchElementException(
					"no such element in the binary search tree");
		trees.add(tree);
		if (number < tree.data) {
			return findPrevious(number, tree.left);
		} else if (number > tree.data) {
			return findPrevious(number, tree.right);
		} else {
			Searchtree pre = trees.get(trees.size() - 2);
			trees = null;
			return pre;
		}
	}
	// min
	public Searchtree findMin(Searchtree 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);
	}
	// max
	public Searchtree findMax(Searchtree 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);
	}
	
	public Searchtree remove(int number) {
		return remove(number, this);
	}
	/*remove
	 *  是最困难的，请大家参考一下，递归有点晕。大家阅读书理解吧。
	 *  参考代码：《数据结构与算法分析》-C语言描述 英文版
	 *  第102-103页 
	 * ISBN: 9787115139849 
	 * detail：http://book.douban.com/subject/1444648/
	 */
	public Searchtree remove(int number, Searchtree tree) {
		Searchtree 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
		} else if (tree.left != null && tree.right != null) {
			// two children
			// replace with the smallest in right tree
			delete = findMin(tree.right);
			tree.setData(delete.data);
			tree.setRight(remove(tree.data, tree.right));
			delete = null;
		} else {
			// one or zero child
			delete = tree;
			if (delete.left == null) {
				tree = tree.right;
			} else if (delete.right == null) {
				tree = tree.left;
			}
			delete = null;
		}
		return tree;
	}
	// 先序遍历 preorder traversal
	public void preorder() {
		System.out.print(data + " ");
		if (left != null)
			left.preorder();
		if (right != null)
			right.preorder();
	}
	// 中序遍历 inorder traversal
	public void inorder() {
		if (left != null)
			left.inorder();
		System.out.print(data + " ");
		if (right != null)
			right.inorder();
	}
	// 后序遍历 postorder traversal
	public void postorder() {
		if (left != null)
			left.postorder();
		if (right != null)
			right.postorder();
		System.out.print(data + " ");
	}
	public int getDepth(Searchtree root) {
		int depth;
		if (root == null)
			return 0;
		else {
			depth = 1 + Math.max(getDepth(root.left), getDepth(root.right));
			return depth;
		}
	}
	public static void main(String[] args) {
		Searchtree tree = new Searchtree(5);
		tree.add(3);
		tree.add(7);
		tree.add(2);
		tree.add(4);
		tree.add(6);
		tree.add(8);
		tree.add(1);
		tree.add(1);
		tree.remove(1);
		// tree.remove(2, tree);
		//tree.remove(tree.data);
		tree.preorder();
		System.out.println();
		tree.inorder();
		System.out.println();
		System.out.println(tree.getDepth(tree));
		System.out.println(tree.find(7).data);
		System.out.println(tree.findPrevious(8, tree).data);
		
	}
}