Java实现二叉排序树

package h1;

import java.lang.Thread.State;
import java.util.Stack;

public class Tree {

	public static void main(String[] args) {

		Tree tree = new Tree();
		tree.insert(8);
		tree.insert(5);
		tree.insert(10);
		tree.insert(4);
		tree.insert(6);
		tree.insert(9);
		tree.insert(12);
		tree.postOrder(tree.root);
		System.out.println();
		tree.PostTraverse(tree.root);

	}

	private Node root;

	public boolean find(int key) {
		boolean flag = true;
		Node current = root;

		while (current.getiData() != key) {

			if (key < current.getiData()) {

				current = current.getLeftChild();
			} else {
				current = current.getRightChild();
			}

			if (current == null) {

				flag = false;
				break;
			}
		}

		return flag;

	}

	/**
	 * 为插入数的节点的操作
	 * 
	 * @param iData
	 */
	public void insert(int iData) {

		// make a new Node
		Node newNode = new Node();
		newNode.setiData(iData);

		if (root == null) {

			root = newNode;
		} else {

			Node current = root;
			Node parent;
			while (true) {
				parent = current;
				if (iData < current.getiData()) { // go left

					current = current.getLeftChild();
					if (current == null) {

						parent.setLeftChild(newNode);
						return;
					}

				} else { // go right

					current = current.getRightChild();

					if (current == null) {

						parent.setRightChild(newNode);
						return;
					}

				}

			}
		}

	}

	public void delete(int key) {

	}

	/**
	 * 用于遍历的时候访问的数据节点
	 * 
	 * @param node
	 */
	public void visit(Node node) {
		System.out.print(node.getiData() + " ");

	}

	/**
	 * 先序遍历，递归实现（根节点，左子树，右子树，）
	 * 
	 * @param node
	 */
	public void preOrder(Node node) {

		if (node == null) {
			return;
		}
		visit(node);
		if (node.getLeftChild() != null) {
			preOrder(node.getLeftChild());
		}
		if (node.getRightChild() != null) {
			preOrder(node.getRightChild());
		}

	}

	// 先序遍历非递归实现
	public void preTraverse(Node node) {

		Stack<Node> stack = new Stack<Node>();
		stack.push(node); // 首先将根节点入栈
		while (!stack.isEmpty()) {
			// 总结：栈中的pop和peek有什么区别呢？
			// pop:移除并返回栈顶的元素
			// peek：只返回栈顶的元素
			Node node2 = (Node) stack.pop();
			visit(node2);
			if (node2.getRightChild() != null) {
				stack.push(node2.getRightChild());
			}
			if (node2.getLeftChild() != null) {
				stack.push(node2.getLeftChild());
			}

		}

	}

	// 中序遍历非递归实现,首先一直找到最左的孩子，
	// 然后将右子树入栈
	public void InTraverse(Node node) {

		Stack<Node> stack = new Stack<>();
		Node p = root;
		while (p != null || !stack.isEmpty()) {

			if (p != null) {
				stack.push(p);
				p = p.getLeftChild();

			} else {

				p = stack.pop();
				visit(p);
				p = p.getRightChild();

			}

		}

	}

	// 后序遍历非递归实现
	public void PostTraverse(Node node) {

		Stack<Node> stack = new Stack<>();
		Node p = root;
		Node pre = p;
		while (p != null || !stack.isEmpty()) {

			// 首先也是找到树的最左孩子
			if (p != null) {

				stack.push(p);
				p = p.getLeftChild();

			} else {

				if (stack.isEmpty()) {
					return;
				}
				p = stack.peek(); // 取得栈顶的元素，但是peek是不会移除的！
				if (p.getRightChild() != null && p.getRightChild() != pre) {

					p = p.getRightChild();
				} else {

					p = stack.pop();
					visit(p);
					pre = p;
					p = null;
				}

			}

		}

	}

	/**
	 * 中序遍历(递归实现)：左子树，data，右子树
	 * 
	 * @param node
	 */
	public void inOrder(Node node) {
		if (node == null) {
			return;
		}

		if (node.getLeftChild() != null) {
			inOrder(node.getLeftChild());
		}
		visit(node);
		if (node.getRightChild() != null) {
			inOrder(node.getRightChild());
		}

	}

	/**
	 * 后序遍历，递归实现（左子树，右子树，根节点）
	 * 
	 * @param node
	 */
	public void postOrder(Node node) {
		if (node == null) {
			return;
		}

		if (node.getLeftChild() != null) {
			postOrder(node.getLeftChild());
		}
		if (node.getRightChild() != null) {
			postOrder(node.getRightChild());
		}
		visit(node);
	}

	public int getMinValue() {
		int min = 0;
		Node current = root;
		while (current.getLeftChild() != null) {

			current = current.getLeftChild();
		}

		return current.getiData();

	}

	public int getMaxValue() {
		int min = 0;
		Node current = root;
		while (current.getRightChild() != null) {

			current = current.getRightChild();
		}

		return current.getiData();

	}

	/**
	 * 删除一个节点的时候，要分类讨论： ①：当该节点是叶子节点的时候，是直接删除的； ②：当该节点有一个孩子的时候， ③：当该节点有3个孩子的时候
	 * 
	 * @param key
	 * @return
	 */
	public boolean remove(int key) {

		boolean flag = true;

		return flag;
	}
}