persontree.java

这里面包含有栈

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));
	}
}