мета-данные страницы
Это старая версия документа!
Семинар 5
Информацию о двоичных деревьях поиска можно прочитать здесь.
Задание 5.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
, описанные в тексте.