import java.util.Scanner;

/**
 * 二叉搜索树的操作集锦
 * 
 * @author Administrator
 *
 */
class BinSearchTreeTest02 {
	public Point1 root;

	// 访问结点
	public static void visitKey(Point1 p) {
		System.out.println(p.getKey() + "  ");
	}

	// 构造树
	public static Point1 Tree() {
		Point1 m = new Point1(4, null, null);
		Point1 a = new Point1(6, m, null);
		Point1 b = new Point1(5, null, a);
		Point1 c = new Point1(14, null, null);
		Point1 d = new Point1(10, b, c);
		Point1 e = new Point1(24, null, null);
		Point1 f = new Point1(25, e, null);
		Point1 g = new Point1(20, null, f);
		Point1 h = new Point1(15, d, g);
		return h;// root
	}

	// 构造空树
	public static Point1 EmptyTree(int t) {
		Point1 a = new Point1(t, null, null);
		return a;
	}

	// *********************************查找操作****************************
	/**
	 * 二叉搜索树查找操作方法1
	 * 
	 * @param t
	 * @param node
	 * @return
	 */
	public static boolean contains(int t, Point1 node) {
		if (node == null)
			return false;// 结点为空，查找失败
		String st = Integer.toString(t);// 把要查找的结点转化为String类型
		int result = compareTo(st, node);
		if (result == 1) {
			return true;
		} else {
			return false;
		}
	}

	public static int compareTo(String a, Point1 p) {
		// String b = Integer.toString(p.getKey());
		// if(a.equals(b))和下面这行是等价的
		if (a.equals(p.getKey() + ""))
			return 1;
		int i = 0, j = 0;
		if (p.getLeftChild() != null) {
			i = compareTo(a, p.getLeftChild());
		}
		if (p.getRightChild() != null) {
			j = compareTo(a, p.getRightChild());
		}
		if (i == 1) {
			return i;
		} else if (j == 1) {
			return j;
		} else {
			return -1;
		}
	}

	/**
	 * 二叉搜索树查找操作方法2(递归算法) 尾递归的方式
	 * 
	 * @param t
	 * @param node
	 * @return
	 */
	public static Point1 contains2(int t, Point1 node) {
		if (node == null)
			return null;// 结点为空，查找失败
		if (t > node.getKey())
			return contains2(t, node.getRightChild());// 查找右子树
		else if (t < node.getKey())
			return contains2(t, node.getLeftChild());// 查找左子树
		else
			return node;
	}

	/**
	 * 二叉搜索树查找的搜索方法2的变形，非递归算法的效率更高 将尾递归改为迭代函数
	 * 
	 * @param args
	 */
	public static Point1 contains3(int t, Point1 node) {
		while (node != null) {
			if (t > node.getKey())
				node = node.getRightChild();
			else if (t < node.getKey())
				node = node.getLeftChild();
			else
				return node;
		}
		return null;
	}

	/**
	 * 二叉搜索树的最大元素 根据其性质可以得出二叉搜索树的最大元一定位于右子树的最右端，最小元则相反
	 * 
	 * @param args
	 */
	public static int findMax(Point1 point) {
		if (point != null) {
			while (point.getRightChild() != null) {
				point = point.getRightChild();
			}
		}
		return point.getKey();
	}

	public static int findMin(Point1 point) {
		if (point == null)
			return 0;// 先判断树是否为空
		else if (point.getLeftChild() == null)
			return point.getKey();// 在判断左子树是否为空
		else
			return findMin(point.getLeftChild());
	}

	public static void main(String[] args, Point1 p) {
		System.out.println("此二叉树的最大结点为：" + findMax(Tree()));
		System.out.println("此二叉树的最小结点为：" + findMin(Tree()));
		@SuppressWarnings("resource")
		Scanner scanner = new Scanner(System.in);
		System.out.println("输入一个结点，将判断是否是此二叉树的结点");
		int a = scanner.nextInt();
		if (contains2(a, Tree()) != null) 
			System.out.println(a + " 是此二叉树的结点"); 
		else 
			System.out.println(a + " 不是此二叉树的结点");	 
	}
}

class Point1 {
	private int key;
	private Point1 LeftChild, RightChild;

	public Point1(int key, Point1 LeftChild, Point1 RightChild) {
		this.key = key;
		this.LeftChild = LeftChild;
		this.RightChild = RightChild;
	}

	public Point1(int key) {
		this(key, null, null);
	}

	public int getKey() {
		return key;
	}

	public void setKey(char key) {
		this.key = key;
	}

	public Point1 getLeftChild() {
		return LeftChild;
	}

	public void setLeftChild(Point1 leftChild) {
		LeftChild = leftChild;
	}

	public Point1 getRightChild() {
		return RightChild;
	}

	public void setRightChild(Point1 rightChild) {
		RightChild = rightChild;
	}
}