BinarySearchTest.java

class BinarySearchTest
{
	public static void main(String[] args)
	{
		BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>(8);
		tree.add(3);
		tree.add(10);
		tree.add(6);
		tree.add(4);
		tree.add(7);
		tree.add(1);
		tree.add(10);
		tree.add(14);
		tree.add(13);
		tree.printTree();

		System.out.println(tree.find(3));
		System.out.println(tree.find(11));
	}
}

BinarySearchTree.java

import java.util.*;

public class BinarySearchTree<E extends Comparable<E>>
{
	BinarySearchTreeNode<E> root;

	//コンストラクタ
	BinarySearchTree(BinarySearchTreeNode<E> root)
	{
		this.root = root;
	}
	BinarySearchTree(E rootobj)
	{
		this.root = new BinarySearchTreeNode<E>(null, rootobj);
	}

	//挿入
	public void add(E obj)
	{
		BinarySearchTreeNode<E> node = root;
		while(node != null){
			int c = obj.compareTo(node.data);
			if(c < 0){
				//obj < node
				if(node.left != null)
					node = node.left;
				else{
					//挿入
					node.left = new BinarySearchTreeNode<E>(node, obj);
					return;
				}
			}
			else{
				//obj >= node
				if(node.right != null)
					node = node.right;
				else{
					//insert
					node.right = new BinarySearchTreeNode<E>(node, obj);
					return;
				}
			}
		}
		System.out.println("add root");
		root = new BinarySearchTreeNode<E>(null, obj);
	}

	//削除(未実装)
	/*
	public void remove(E obj)
	{
		BinarySearchTreeNode<E> node = root;
		while(node != null){
			int c = obj.compareTo(node);
			if(c < 0){
				node = node.left;
			}
			else if(c > 0)
				node = node.right;
			else
				//delete node
				if(node.right == null && node.left == null)
				node.parent.
		}
	}
	*/

	//探索
	public E find(E obj)
	{
		BinarySearchTreeNode<E> node = root;
		while(node != null){
			int c = obj.compareTo(node.data);
			if(c < 0)
				node = node.left;
			else if(c > 0)
				node = node.right;
			else
				return node.data;
		}
		return null;
	}

	public void printTree()
	{
		if(root != null){
			printTree(root);
			System.out.println();
		}
		else
			System.out.println("root is empty");
	}
	public void printTree(BinarySearchTreeNode<E> node)
	{
		if(node.left != null)
			printTree(node.left);

		System.out.printf("%s ", node.toString());

		if(node.right != null)
			printTree(node.right);
	}
}

class BinarySearchTreeNode<E>
{
	E data;

	public BinarySearchTreeNode<E> left, right, parent;

	BinarySearchTreeNode(BinarySearchTreeNode<E> parent, E obj)
	{
		this.parent = parent;
		this.data = obj;
	}

	@Override
	public String toString()
	{
		return data.toString();
	}
}

BinarySearchTree.md

#二分探索木

##2013-07-25 追加、探索が実装されている

削除は未実装

##todo 平衡二分探索木への進化が待たれる。