java实现二叉搜索树

       开门见山,首先来理解一下什么是二叉搜索树:也叫二叉排序树，是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。空树也是二叉搜索树。
       简单的说，二叉搜索树就是一课二叉树，每个父节点都一定大于等于其左孩子且小于等于它的右孩子。

       首先，创建一个节点类，Node，这个类需要有它左右孩子节点的引用，同时还应该有节点要存储的数据，为了简单起见，这里我只是用了一个index的整形数作为要保存的内容。

public class Node {
	private int index;
	private Node leftChild;
	private Node rightChild;

	public Node() {
	}

	public Node(int index) {
		super();
		this.index = index;
	}

	public int getIndex() {
		return index;
	}

	public void setIndex(int index) {
		this.index = index;
	}

	public Node getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(Node leftChild) {
		this.leftChild = leftChild;
	}

	public Node getRightChild() {
		return rightChild;
	}

	public void setRightChild(Node rightChild) {
		this.rightChild = rightChild;
	}

}

       接着，我们创建一个二叉树的类，BinaryTree，它只有一个根节点。里面主要有插入节点，查找节点的方法，删除节点的方法。
       查找的过程：从根节点开始，根节点为当前节点，判断要查找的内容与当前节点的内容的大小关系，若查找值小于等于当前节点的内容值，往左子树方向查找，反之往右子树查找。改变当前节点的指向对象(指向要查找的那个方向的当前节点的孩子节点)，重复上诉操作，直至找到节点或者到树的底部。
       插入节点跟查找节点类似，用同样的方式找到要插入的节点的恰当的插入位置，把节点插入(即使上一级的节点的左/右孩子节点指向该要插入的节点)
       删除节点的操作:分为三种情况，第一:该节点是叶子节点，找出来直接删除即刻；第二：该节点有一个孩子节点，找出节点，删除节点并让其父节点的左/右孩子节点引用指向删除的节点的孩子节点。第三:该节点有两个孩子节点，找出节点，然后找到该节点的直接后继节点（即中序遍历时，紧跟在这个节点后面的那个节点），并用这个节点代替删除的节点

public class BinaryTree {
	private Node root;

	public BinaryTree() {
	}

	public BinaryTree(Node root) {
		this.root = root;
	}

	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	/**
	 * 寻找节点
	 * 
	 * @param node
	 */
	public Node find(int index) {
		if (this.root.getIndex() == index) {
			return this.root;
		}
		Node current = this.root;
		while (current != null) {
			int temp_index = current.getIndex();
			// 判断查询方向
			if (temp_index >= index) {// 左子树
				current = current.getLeftChild();
			} else {
				current = current.getRightChild();
			}
			// 判断是否匹配当前节点
			if (current != null && current.getIndex() == index) {// 匹配则返回
				return current;
			}
		}
		return null;
	}

	/**
	 * 找到要找的节点的父节点
	 * 
	 * @param index
	 * @return
	 */
	private Node findParent(int index) {
		if (this.root.getIndex() == index) {
			return this.root;
		}
		Node current = this.root;
		Node parent = null;
		while (current != null) {
			parent = current;
			int temp_index = current.getIndex();
			// 判断查询方向
			if (temp_index >= index) {// 左子树
				current = current.getLeftChild();
			} else {
				current = current.getRightChild();
			}
			// 判断是否匹配当前节点
			if (current != null && current.getIndex() == index) {// 匹配则返回
				return parent;
			}
		}
		return null;
	}

	/**
	 * 删除节点
	 * 
	 * @param node
	 */
	public void delete(Node node) {
		int index = node.getIndex();
		Node target = find(index);
		if (target == null) {
			System.out.println("节点不存在");
			return;
		}
		// 取得目标节点的父节点
		Node parent = this.findParent(index);
		// 目标节点左孩子
		Node left_temp = target.getLeftChild();
		// 目标节点右孩子
		Node right_temp = target.getRightChild();

		if (target.getLeftChild() != null && target.getRightChild() != null) {// 有两个孩子节点
			// 目标节点直接左孩子
			Node direct_leftChild = left_temp;
			// 目标节点直接左孩子的父节点
			Node direct_leftChild_p = target;
			// 找到目标节点的直接左孩子节点以及记录该孩子节点的父节点
			while (direct_leftChild.getLeftChild() != null) {
				direct_leftChild_p = direct_leftChild;
				direct_leftChild = direct_leftChild.getLeftChild();
			}
			// 执行删除操作
			target = null;
			if (parent.getLeftChild().getIndex() == index) {
				parent.setLeftChild(direct_leftChild);
			}
			if (parent.getRightChild().getIndex() == index) {
				parent.setRightChild(direct_leftChild);
			}
			if (direct_leftChild_p.getRightChild() != null) {
				direct_leftChild.setRightChild(direct_leftChild_p
						.getRightChild());
			}
		} else {// 节点是叶子节点或者只有一个子节点的情况
			target = null;
			// 判断被删除的节点是其父节点的哪个孩子
			if (parent.getLeftChild().getIndex() == index) {// 左孩子
				// 从新给左孩子设值(为了满足有单个孩子的情况,做了左右孩子值是否为空的判断)
				parent.setLeftChild(left_temp == null ? right_temp : left_temp);
			}
			if (parent.getRightChild().getIndex() == index) {// 右孩子
				// 同上
				parent.setRightChild(right_temp == null ? left_temp
						: right_temp);
			}
		}
	}

	/**
	 * 添加节点
	 * 
	 * @param node
	 */
	public void insert(Node node) {
		if (this.root == null) {// 根节点不存在
			this.root = node;
		} else {
			Node current = this.root;
			while (true) {
				Node temp = null;
				if (current.getIndex() > node.getIndex()) {// 左子树
					temp = current.getLeftChild();
					if (temp == null) {
						current.setLeftChild(node);
						return;
					}
				} else {
					temp = current.getRightChild();
					if (temp == null) {
						current.setRightChild(node);
						return;
					}
				}
				current = temp;
			}
		}
	}

	public void print() {
		inorder_traversal(this.root, 1);// 中序遍历的结果是一个有序的序列
	}

	/**
	 * 先序遍历
	 * 
	 * @param node
	 * @param level
	 */
	private void preorder_traversal(Node node, int level) {// 先序遍历
		for (int i = 0; i < level; i++) {
			System.out.print("-");
		}
		System.out.println(node.getIndex());
		int lev = level + 1;
		if (node.getLeftChild() != null) {
			preorder_traversal(node.getLeftChild(), lev);
		}
		if (node.getRightChild() != null) {
			inorder_traversal(node.getRightChild(), lev);
		}
	}

	/**
	 * 中序遍历
	 * 
	 * @param node
	 * @param level
	 */
	private void inorder_traversal(Node node, int level) {// 中序遍历
		int lev = level + 1;
		if (node.getLeftChild() != null) {
			inorder_traversal(node.getLeftChild(), lev);
		}
		for (int i = 0; i < level; i++) {
			System.out.print("-");
		}
		System.out.println(node.getIndex());
		if (node.getRightChild() != null) {
			inorder_traversal(node.getRightChild(), lev);
		}
	}

	/**
	 * 后序遍历
	 * 
	 * @param node
	 * @param level
	 */
	private void postorder_traversal(Node node, int level) {// 后序遍历
		int lev = level + 1;
		if (node.getLeftChild() != null) {
			postorder_traversal(node.getLeftChild(), lev);
		}
		if (node.getRightChild() != null) {
			postorder_traversal(node.getRightChild(), lev);
		}
		for (int i = 0; i < level; i++) {
			System.out.print("-");
		}
		System.out.println(node.getIndex());
	}

}