Код реализация Бинарного дерева на Java для задания из Word of Week. Саму идею дерева и теоретический алгоритм можно почитать в Википедии. Отличается от реализации на C++ тем, что в Java мы не обращаемся к адресам узлам явно, сравнение происходит через компаратор и сам класс при создании имеет свои особенности от C++. Для работы самого класса, в нем присутствуют приватные методы, которые работают рекурсивно, и geter’ы, позволяющие получать значение от работы приватных методов.
В тестовом выводе можно пронаблюдать(если вы запустите данный код) как выглядит дерево после добавления данных, потом как оно выглядит после удаления одного из узлов и далее убедиться в правильности дополнительных функций.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 |
import jdk.internal.org.objectweb.asm.tree.analysis.Value; import java.security.Key; /** * Created by green on 26.11.15. */ class BST <Key extends Comparable<Key>, Value> { private class Node { Key key; Value value; Node left, right, father; public Node (Key key, Value value) { this.key = key; this.value = value; this.left = this.right = null; this.father = null; } public Node (Key key, Value value, Node father) { this.key = key; this.value = value; this.left = this.right = null; this.father = father; } } private Node root; private Node add (Node node,Key key, Value value, Node father){ if (node == null){ Node newnode = new Node(key,value, father); return newnode; } int compareResult = key.compareTo(node.key); if (compareResult > 0) node.right = add(node.right, key, value, node); else if(compareResult < 0) node.left = add(node.left, key, value, node); else{ node.value = value; } return node; } public void add(Key key, Value value) { root = add(root, key, value, root); } private Node delete(Node node, Key key){ if(node == null) return null; int compareResult = key.compareTo(node.key); if(compareResult > 0){ node.right = delete(node.right, key); }else if(compareResult < 0){ node.left = delete(node.left, key); }else{ if(node.right == null && node.left == null){ return node = null; }else if(node.right == null){ return node = node.left; }else if(node.left == null){ return node = node.right; }else{ if(node.right.left == null){ node.right.left = node.left; node.right.father = node.father; return node = node.right; }else{ Node res = min(node.right); node.key = res.key; node.value = res.value; delete(node.right, node.key); return node; } } } return node; } public void delete(Key key) { root = delete(root, key); } public Key minKey(){ return min(root).key; } public Key maxKey(){ return max(root).key; } private Node min(Node node){ if(node.left == null) return node; return min(node.left); } private Node max(Node node){ if(node.right == null) return node; return min(node.right); } private Value get(Node node, Key key){ if(node == null) return null; int compareResult = key.compareTo(node.key); if(compareResult == 0){ return node.value; }else if(compareResult > 0){ return get(node.right, key); }else{ return get(node.left, key); } } public Value get(Key key) { return get(root, key); } private void print(Node node, int level) { if (node != null) { print(node.right,level+1); for (int i=0;i<level;i++) { System.out.print("\t"); } System.out.println(node.key + "->" + node.value); print(node.left,level+1); } } public void print() { print(root,0); } } public class Hello_World { public static void main(String[] args) { BST<Integer, String> tree = new BST<>(); tree.add(10, "Test1"); tree.add(12, "Test2"); tree.add(1, "Test3"); tree.add(5, "Test4"); tree.add(6, "Test5"); tree.add(3, "Test5"); tree.print(); tree.delete(5); tree.print(); System.out.println(tree.get(1)); System.out.println(tree.minKey()); System.out.println(tree.maxKey()); System.out.println(tree.get(3)); } } |
В соответствии со спецификацией Comparable compareTo возвращает «a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.» — т.е. не обязательно -1, 0 и 1.
Ваш minKey никакой не minKey, а, фактически, minValue — значение сопоставленное минимальному ключу, то же и с maxKey. Конечно, метод minValue тоже имеет право на жизнь, но сейчас у Вас путаница. Кроме того, что этот метод вернет для пустого дерева?
В Вашем случае тестового ввода нет — но тестовый вывод (т.е. результат) то есть. И его нужно кратко пояснить. Так же нет ссылки на ideone или другое online IDE.
Исправил все.