Иногда студентам поручают задания, которые на первый взгляд кажутся легкими, и только при их выполнении понимаешь их истинную сложность.
Одно из таких заданий — создание класса-коллекции «бинарное дерево». Подробнее можно почитать тут. Более опытный программист при желании напишет лучше, здесь же простая реализация.
Итак, было решено использовать такую схему:
class BinaryTree{
private static class BinaryTreeElement{
public Comparable object;
public BinaryTreeElement leftChild;
public BinaryTreeElement rightChild;
}
private BinaryTreeElement root;
public boolean isEmpty();
public boolean add(Comparable o);
public boolean delete(int number);
public Object[] output();
public Object[] toArray();
}
Interface Comparable{
public int CompareTo(Object o);
public int nextNumber();
public int getNumber();
}Обо всем по порядку. Класс BinaryTree содержит скрытый подкласс-узел дерева. Каждый узел бинарного дерева содержит левый и правый узел-потомок, а также хранимый объект. Объект реализует созданный интерфейс Comparable, который содержит методы, используемые для корректного размещения объектов в узлах дерева:
- Метод, получающий ответ на вопрос «как сравнивать объекты? Какой из них-текущий (this), или переданный методу, больше?»;
- Метод, определяющий алгоритм программы при попытке добавить элемент, номер которого совпадает с номером одного из ранее добавленных элементов;
- Метод, используемый для получения номера элемента для корректного добавления элемента в коллекцию.
Остальные два элемента класса BinaryTreeElement требуются для хранения узлов-потомков данного узла. Получается, что каждый узел является фракталом, что позволяет добавлять элементы в дерево пока не надоест или закончатся ресурсы компьютера.
Теперь перейдем непосредственно к классу BinaryTree. Этот класс содержит корневой узел root и методы для работы с ним и его потомками. Методы подробно описаны ниже.
- Чтобы не кидать в пользователя исключения при попытке получить элементы дерева, было бы неплохо создать метод, определяющий, есть ли в данном дереве элементы. К тому же, он совсем простой:
public boolean isEmpty(){ return root==null; } - Зачем нужна коллекция, в которую невозможно добавить элементы? Поэтому реализуем метод add().
Этот метод должен правильно определять место элемента в бинарном дереве, следовательно, нужно иметь возможность получения номера элемента. Чтобы не ограничивать возможности этой коллекции всего одним классом, с которым она сможет работать, и был создан интерфейс Comparable.
Каждый элемент дерева-это фрактал, значит, рекурсивная функция в данной ситуации подойдет идеально. Однако при реализации рекурсивного метода, этот метод должен иметь элемент, считающийся локально (только в этом методе) корнем. При его вызове он определяет, в какую сторону шагать (если добавляемый элемент больше корневого-вправо, меньше-влево) и передает соответствующего потомка себе же рекурсивно. При этом пользователь не имеет доступа непосредственно к узлам, => не может определить начальную точку-локальный корень для данного метода, поэтому здесь реализовано два метода — приватный и доступный пользователю, который просто вызывает приватный метод, передавая ему корень дерева.
Если добавляемый элемент имеет номер, который совпадает с номером ранее добавленного элемента, вызывается метод для смены номера нового элемента, затем генерируется исключение. Исключение используется для возврата в вызывающий (public) метод для того, чтобы сбросить рекурсию и искать место для элемента с начала списка.public boolean add(Comparable o){ while(true) { try { root = add(o, root); break; }catch(ArrayStoreException e){ continue; } } return true; } private BinaryTreeElement add(Comparable o,BinaryTreeElement element){ if(element==null){ element=new BinaryTreeElement(); element.object=o; return element; } else { //номер элементов не должен совпадать while(o.CompareTo(element.object) == 0) { o.nextNumber(); //исключение используется для сброса стека (рекурсия) и сортировки элемента по его новому номеру с начала дерева throw new ArrayStoreException(); } if (o.CompareTo(element.object) > 0) { //добавить справа element.rightChild = add(o, element.rightChild); return element; } else { //добавить слева element.leftChild = add(o, element.leftChild); return element; } } } - Затем следует добавить возможность удаления элементов из коллекции. Данная функция не представляет сложности, если у удаляемого элемента нет дочерних узлов, тогда можно не заботиться об их сохранности и уничтожить элемент. В противном случае я сохраняю ветку-потомка удаляемого элемента, удаляю требуемый элемент и рекурсивно добавляю элементы из сохраненной ветки в коллекцию методом add(BinaryTreeElement element,boolean b).
Так как объект-это ссылочный тип данных, нельзя просто изменить в null текущий объект, вместо этого родитель должен удалить ссылку на элемент, поэтому код кажется сложным.
Тактика удаления узла, имеющего потомков-поиск минимального элемента в его правом потомке (правом поддереве) и замена удаляемого элемента на найденный. Для поиска минимального элемента в определенном поддереве служит метод deleteMinChild()public Comparable delete(int number)throws NullPointerException { if (root == null) throw new NullPointerException(); //объект, данные которого будут предоставлены в отчете об удалении Comparable object; //рекурсивный метод работает с детьми заданной точки, следовательно будет лучше вынести раьоту с корнем а данный метод if (root.object.getNumber() == number) { object = root.object; if (root.leftChild == null) { if (root.rightChild == null) root = null; else root = root.rightChild; } else { if (root.rightChild == null) { if (root.leftChild == null) root = null; else root = root.leftChild; } else { if (root.leftChild != null && root.rightChild != null) { try { BinaryTreeElement element=deleteMinChild(root.rightChild); root.object = element.object; add(element,false); }catch(NullPointerException e){ //это значит, что левой ветки у правого узла нет, и он сам минимальный root.rightChild.leftChild=root.leftChild; root=root.rightChild; } } } } return object; } object=delete(number, root); return object; } private BinaryTreeElement deleteMinChild(BinaryTreeElement element){ if(element.leftChild.leftChild==null){ BinaryTreeElement find=element.leftChild; element.leftChild=null; return find; } return deleteMinChild(element.leftChild); } private Comparable delete(int number, BinaryTreeElement element) throws NullPointerException{ //это возвращаемый объект Comparable result=null; //необходимо идти вправо if(element.object.getNumber() < number) { //если правый потомок подходит if (element.rightChild.object.getNumber() == number) { //правый узел-искомый элемент result = element.rightChild.object; //если у узла-потомка нет дочерних узлов, его требуется удалить if (element.rightChild.leftChild == null && element.rightChild.rightChild == null) element.rightChild = null; else { if(element.rightChild.leftChild!=null && element.rightChild.rightChild!=null){ try { BinaryTreeElement newElement = deleteMinChild(element.rightChild.rightChild); element.rightChild.object=newElement.object; add(newElement,false); }catch(NullPointerException e){ //это значит, что в левой ветке правого узла элемента нет элементов и он сам минимальный element.rightChild.rightChild.leftChild=element.rightChild.leftChild; element.rightChild=element.rightChild.rightChild; } } else { if (element.rightChild.leftChild == null) element.rightChild = element.rightChild.rightChild; else { if (element.rightChild.rightChild == null) element.rightChild = element.rightChild.leftChild; } } } } else{ result=delete(number,element.rightChild); } } //необходимо идти влево else { if (element.leftChild.object.getNumber() == number) { //левый узел-искомый элемент result = element.leftChild.object; //если у узла-потомка нет дочерних узлов, его требуется удалить if (element.leftChild.leftChild == null && element.leftChild.rightChild == null) element.leftChild = null; else { if (element.leftChild.leftChild!=null && element.leftChild.rightChild!=null){ try{ BinaryTreeElement newElement = deleteMinChild(element.leftChild.rightChild); element.leftChild.object=newElement.object; add(newElement,false); }catch(NullPointerException e){ //это значит, что в левой ветке правого узла элемента нет элементов и он сам минимальный element.leftChild.rightChild.leftChild=element.leftChild.leftChild; element.leftChild=element.leftChild.rightChild; } } else{ if(element.leftChild.rightChild==null) element.leftChild=element.leftChild.leftChild; else{ if(element.leftChild.leftChild==null) element.leftChild=element.leftChild.rightChild; } } } } else{ result=delete(number,element.leftChild); } } return result; } - Для красивого вывода содержимого дерева реализуется метод output(). Данный метод просматривает бинарное дерево и выводит все его элементы, начиная с минимального, причем по отступа можно отследить вложенность узлов. Таких методов также два-видимый пользователю и приватный:
public Object[] output(){ if(root!=null) return output(root); return new String[]{"Бинарное дерево не содержит элементов"}; } private Object[] output(BinaryTreeElement element) { ArrayList<String> result = new ArrayList<>(); if (element.leftChild != null) { Object[] temp = output(element.leftChild); for (int i = 0; i < temp.length; i++) { result.add(" "+ temp[i]); } } result.add(element.object.toString()); if (element.rightChild != null) { Object[] temp = output(element.rightChild); for (int i = 0; i < temp.length; i++) { result.add(" " + temp[i]); } } return result.toArray(); } - Предусмотрена возможность получения содержимого бинарного дерева в виде массива, элементы которого отсортированы от меньших (с меньшим номером) к большим. Метод генерирует исключение NullPointerException, если в коллекции нет элементов, поэтому перед его вызовом рекомендуется использовать метод isEmpty(). Этот метод очень похож на метод output(), однако возвращает не строковое описание объектов, а сами объекты.
public Object[] toArray(){ if(root==null) throw new NullPointerException(); return toArray(root); } private Object[] toArray(BinaryTreeElement element){ ArrayList<Comparable> result=new ArrayList<>(); if (element.leftChild != null) { Object[] temp = toArray(element.leftChild); for (int i = 0; i < temp.length; i++) { Comparable object=(Comparable)temp[i]; result.add(object); } } result.add(element.object); if (element.rightChild != null) { Object[] temp = toArray(element.rightChild); for (int i = 0; i < temp.length; i++) { Comparable object=(Comparable)temp[i]; result.add(object); } } return result.toArray(); }
Полный код разработанного класса, класса, реализующего интерфейс Comparable и программа, добавляющая элементы этого класса в коллекцию, тут.
Понимаю, что реализация слабовата, предложения по улучшению разработанного класса приветствуются.
Автор: Nerd0_0
