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

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

Задание. Часть 1

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

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 MyBinarySearchTree(int data){ root = new Node(data); } 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); } private Node treeSearch(int data){ return treeSearch(root, data); } }

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