package org.huhuiyu.datastructures;

import java.util.Random;
import java.util.Scanner;

/**
 * 二叉樹實現
 */
public class PersonTree {
	private PersonNode root;

	public PersonTree() {
	}

	/**
	 * 添加節點
	 * 
	 * @param person
	 */
	public void add(Person person) {
		if (!isEmpty()) {
			add(root, person);
		}
		else {
			root = new PersonNode(person);
		}
	}

	/**
	 * 添加節點的實現
	 * 
	 * @param node
	 *            目標節點
	 * @param person
	 *            添加的數據
	 */
	private void add(PersonNode node, Person person) {
		if (person.getId() <= node.getData().getId()) {
			// 如果添加的id比較小就添加到左子節點
			if (node.getLeft() == null) {
				node.setLeft(new PersonNode(person));
			}
			else {
				add(node.getLeft(), person); // 如果有左子節點就遞歸調用
			}
		}
		else if (person.getId() > node.getData().getId()) {
			// 如果添加的id比較大就添加到右子節點
			if (node.getRight() == null) {
				node.setRight(new PersonNode(person));
			}
			else {
				add(node.getRight(), person); // 如果有右子節點就遞歸調用
			}
		}
	}

	/**
	 * 查找指定編號的數據
	 * 
	 * @param id
	 *            編號
	 * @return 指定編號的數據
	 */
	public Person find(int id) {
		if (!isEmpty()) {
			return find(id, root);
		}
		else {
			return null;
		}
	}

	/**
	 * 查找指定編號的數據實現
	 * 
	 * @param id
	 *            編號
	 * @param node
	 *            查找的根節點
	 * @return 指定編號的數據
	 */
	private Person find(int id, PersonNode node) {
		Person data = null;
		if (node.getData().getId() == id) {
			return node.getData();
		}
		if (node.getLeft() != null) {
			data = find(id, node.getLeft());
		}
		if (data == null && node.getRight() != null) {
			data = find(id, node.getRight());
		}
		return data;
	}

	/**
	 * 顯示整個樹
	 */
	public void display() {
		if (!isEmpty()) {
			display(root);
		}
	}

	/**
	 * 顯示樹的實現
	 * 
	 * @param node
	 *            顯示的根節點
	 */
	private void display(PersonNode node) {
		if (node == null) { // 遞歸停止條件
			return;
		}
		// 中序遍歷，將會按照id排序顯示
		display(node.getLeft());
		System.out.println(node.getData());
		display(node.getRight());
	}

	public boolean isEmpty() {
		return root == null;
	}

	public void clear() {
		root = null;
	}

	public static void main(String[] args) {
		Random random = new Random();
		PersonTree tree = new PersonTree();
		for (int i = 1; i < 200; i++) {
			Person p = new Person(random.nextInt(100) + 1, "姓名" + i);
			tree.add(p);
		}
		tree.display();
		Scanner scanner = new Scanner(System.in);
		System.out.print("請輸入要查找的人員編號:");
		int id = scanner.nextInt();
		System.out.println(tree.find(id));
	}
}