Занятие II (весна 2014 г.)

Перед выполнением задания прочитайте информацию о двоичных деревьях поиска.

Приведем одну из возможных реализаций двоичного дерева поиска:

public class MyBinarySearchTree{
	private static class Node{
		Integer data = null;
		Node parent = null;
		Node left = null;
		Node right = null;
 
		Node (int data){
			this.data = new Integer(data);
		}
	}
 
	private Node root;
 
	public void treeInsert(int data){
		Node y = null;
		Node x = root;
 
		while(x != null){
			y = x;
			if(data < x.data.intValue())
				x = x.left;
			else
				x = x.right;
		}
 
		Node z = new Node(data);
		z.parent = y;
 
		if(y == null)
			root = z;
		else{
			if(data < y.data.intValue())
				y.left = z;
			else
				y.right = z;
		}
	}
 
	private Node treeSearch(Node x, int data){
		if(x == null || data == x.data.intValue())
			return x;
		else if (data < x.data.intValue())
			return treeSearch(x.left, data);
		else
			return treeSearch(x.right, data);
	}
 
	public boolean treeSearch(int data){
		if (treeSearch(root, data) == null)
			return false;
		return true;
	}
}

Протестируем работу метода treeSearch:

int tmpInt;
Random random = new Random();
 
ArrayList<Integer> list = new ArrayList<Integer>();
MyBinarySearchTree tree = new MyBinarySearchTree();
 
for (int i = 0; i < 10; i++) {
	tmpInt = random.nextInt(20);
	tree.treeInsert(tmpInt);
	list.add(new Integer(tmpInt));
}
 
System.out.println(list.toString());
for (int i = 0; i < 20; i++) {
	System.out.println(i + ": " + (list.indexOf(i) >= 0) + " "
				+ tree.treeSearch(i));
}

Допишите методы inOrderTreeWalk, treeMinimum, treeMaximum, treeSuccessor, treePredecessor, treeDelete, описанные в тексте.

Список занятий