package I第12章__二叉搜索树;

//普通二叉树
public class BinaryTree<T> {
	// -----------------------数据结构---------------------------------
	private int height = 0;
	private Node<T> rootNode;

	class Node<T> {
		T t;
		int key;
		Node left;
		Node right;
		public Node(T t, int big) {
			this.t = t;
			this.key = big;
		}
	}

	// -----------------------数据处理------------------------------------
	// 插入
	public void add(T t, int big) {
		Node<T> node = new Node<T>(t, big);
		//根节点为空
		if (isEmpty()) {
			this.rootNode = node;
			return;
		}
		// 根节点不为空
		insert(this.rootNode, node);
	}
    //递归调用
	private void insert(Node rootNode, Node node) {
		//如果要插入的数据比根节点大，就将其插入右子树
		if (node.key >= rootNode.key) {
			// 右边元素为空
			   // 直接插入
			if (rootNode.right == null) {
				rootNode.right = node;
				return;
			}
			// 右边元素不为空
			   // 这时候要重进递归，但是这次递归的父节点发生了变化，所以在递归的参数中，要体现这个变化！
			if (rootNode.right != null) {
				insert(rootNode.right, node);
			}
		}
		//如果是插入的数据比根节点小，就将其插入左子树
		if (node.key < rootNode.key) {
			if (rootNode.left == null) {
				rootNode.left = node;
				return;
			}
			if (rootNode.left != null) {
				insert(rootNode.left, node);
			}
		}
	}
	// 获取信息
	public T get(int key) {
		return this.get_xianxu(this.rootNode, key);
	}

	private T get_xianxu(Node root, int key) {
        //递归算法中，如果需要返回一个值，那么，一般是在递归程序中定义一个，然后先在本层搜索，如果搜索不到，则另本层的参数等于下一层的搜索结果
		T t = null;
		if (root != null) {
			if (key == root.key) {
				t = (T) root.t;
			} else if (key < root.key) {
				t=get_xianxu(root.left, key);
			} else if (key > root.key) {
				t=get_xianxu(root.right, key);
			}
		}
		return t;
	}
	// 显示
	public void Show_All(int i) {
		if (i == -1) {
			show_xian(this.rootNode);
		} else if (i == 0) {
			show_zhong(this.rootNode);
		} else if (i == 1) {
			show_hou(this.rootNode);
		} else {
			System.out.println("大哥！你输入的数字有误");
		}

	}

	// 先根遍历
	public void show_xian(Node rootNode) {
		if (rootNode != null) {
			System.out.println(rootNode.t);
			show_xian(rootNode.left);
			show_xian(rootNode.right);
		}
	}

	// 中根遍历
	public void show_zhong(Node rootNode) {
		if (rootNode != null) {
			show_zhong(rootNode.left);
			System.out.println(rootNode.t);
			show_zhong(rootNode.right);
		}
	}

	// 后根遍历
	public void show_hou(Node rootNode) {
		if (rootNode != null) {
			show_hou(rootNode.left);
			show_hou(rootNode.right);
			System.out.println(rootNode.t);
		}
	}

	public void houxu(Node rootNode) {
		if (rootNode.left != null) {
			houxu(rootNode.left);
		}
		if (rootNode.right != null) {
			houxu(rootNode.right);
		}
		System.out.println(rootNode.t);
	}

	// 判断树是否为空
	public boolean isEmpty() {
		return this.rootNode == null;
	}
}