Бинарное дерево, быстрая реализация

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

Одно из таких заданий — создание класса-коллекции «бинарное дерево». Подробнее можно почитать тут ^[1]. Более опытный программист при желании напишет лучше, здесь же простая реализация.

Итак, было решено использовать такую схему:

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, который содержит методы, используемые для корректного размещения объектов в узлах дерева:

1. Метод, получающий ответ на вопрос «как сравнивать объекты? Какой из них-текущий (this), или переданный методу, больше?»;
2. Метод, определяющий алгоритм программы при попытке добавить элемент, номер которого совпадает с номером одного из ранее добавленных элементов;
3. Метод, используемый для получения номера элемента для корректного добавления элемента в коллекцию.

Остальные два элемента класса BinaryTreeElement требуются для хранения узлов-потомков данного узла. Получается, что каждый узел является фракталом, что позволяет добавлять элементы в дерево пока не надоест или закончатся ресурсы компьютера.

Теперь перейдем непосредственно к классу BinaryTree. Этот класс содержит корневой узел root и методы для работы с ним и его потомками. Методы подробно описаны ниже.

1. Чтобы не кидать в пользователя исключения при попытке получить элементы дерева, было бы неплохо создать метод, определяющий, есть ли в данном дереве элементы. К тому же, он совсем простой:

   public boolean isEmpty(){
           return root==null;
       }

2. Зачем нужна коллекция, в которую невозможно добавить элементы? Поэтому реализуем метод 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;
               }
           }
       }

3. Затем следует добавить возможность удаления элементов из коллекции. Данная функция не представляет сложности, если у удаляемого элемента нет дочерних узлов, тогда можно не заботиться об их сохранности и уничтожить элемент. В противном случае я сохраняю ветку-потомка удаляемого элемента, удаляю требуемый элемент и рекурсивно добавляю элементы из сохраненной ветки в коллекцию методом 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;
       }

4. Для красивого вывода содержимого дерева реализуется метод 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();
       }

5. Предусмотрена возможность получения содержимого бинарного дерева в виде массива, элементы которого отсортированы от меньших (с меньшим номером) к большим. Метод генерирует исключение 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 и программа, добавляющая элементы этого класса в коллекцию, тут ^[2].

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

Автор: Nerd0_0

Источник ^[3]