Занятие 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 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, описанные в тексте.

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

Задание 5.2

Преобразуйте написанный вами класс в класс, предназначенный для работы со строками. Получившийся класс должен выглядеть примерно так:

public class ModifiedBinarySearchTree{ private static class Node{ String data = null; Node parent = null; Node left = null; Node right = null; Node (String data){ this.data = data; } } private Node root; public void treeInsert(String data){ Node y = null; Node x = root; while(x != null){ y = x; if(data.compareTo(x.data) < 0) x = x.left; else x = x.right; } Node z = new Node(data); z.parent = y; if(y == null) root = z; else{ if(data.compareTo(y.data) < 0) y.left = z; else y.right = z; } } /* Остальные методы (модифицированные соответствующим образом) */ }

Дан текстовый файл, содержащий английские названия стран мира. С помощью класса ModifiedBinarySearchTree составьте алфавитный список названий стран и запишите его в файл alphabetical_list_of_countries.txt

Код для чтения из файла и записи в файл:

/* чтение из файла list_of_countries.txt и сохранение списка стран в виде ArrayList */ BufferedReader inputFile = null; try { inputFile = new BufferedReader(new FileReader("list_of_countries.txt")); } catch (FileNotFoundException e) { e.printStackTrace(); } String tmpString; ArrayList<String> arr = new ArrayList<String>(); try { while ((tmpString = inputFile.readLine()) != null) arr.add(tmpString); } catch (IOException e) { e.printStackTrace(); } /* запись списка стран в файл alphabetical_list_of_countries.txt */ BufferedWriter outputFile = null; try { outputFile = new BufferedWriter(new FileWriter("alphabetical_list_of_countries.txt")); } catch (IOException e) { e.printStackTrace(); } try { for (int i = 0; i < arr.size(); i++){ outputFile.write(arr.get(i)); outputFile.newLine(); } } catch (IOException e) { e.printStackTrace(); } finally{ try{ if(outputFile != null){ outputFile.flush(); outputFile.close(); } } catch(IOException e){ e.printStackTrace(); } }

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