Binary tree, fast implementation

Sometimes students are assigned tasks that at first glance seem to be easy, and only when they are done you understand their true complexity.

One of these tasks is the creation of a binary tree collection class. You can read more here . A more experienced programmer will write better if desired, here is a simple implementation.

So, it was decided to use this scheme:

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(); } 

First things first. The BinaryTree class contains a hidden tree subclass. Each node of a binary tree contains a left and right child node, as well as a stored object. The object implements the created Comparable interface, which contains the methods used to correctly place objects in the tree nodes:
')

1. The method that receives the answer to the question “how to compare objects? Which one is the current (this), or passed to the method, anymore? ”;
2. The method that determines the program's algorithm when trying to add an element whose number matches the number of one of the previously added elements;
3. The method used to get the item number to correctly add an item to the collection.

The remaining two elements of the BinaryTreeElement class are required to store the descendant nodes of this node. It turns out that each node is a fractal, which allows you to add elements to the tree until you get bored or computer resources run out.

Now let's go directly to the BinaryTree class. This class contains the root root node and methods for working with it and its descendants. The methods are described in detail below.

1. In order not to throw exceptions at the user when trying to get the elements of the tree, it would be nice to create a method that determines whether there are elements in this tree. Besides, it is quite simple:
   
   

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

2. Why do you need a collection to which elements cannot be added? Therefore, we implement the add () method.
   
   This method must correctly determine the location of an element in a binary tree; therefore, it is necessary to be able to obtain an element number. In order not to limit the possibilities of this collection to just one class with which it can work, the Comparable interface was created.
   
   Each element of the tree is a fractal, which means that the recursive function in this situation fits perfectly. However, when implementing a recursive method, this method must have an element that is considered locally (only in this method) as a root. When it is called, it determines in which direction to step (if the added element is more root-to the right, less-to the left) and passes the corresponding descendant to itself as recursively. In this case, the user does not have access directly to the nodes, => cannot determine the starting point — the local root for this method; therefore, two methods are implemented here — private and accessible to the user, which simply calls the private method, passing it the root of the tree.
   If the added item has a number that matches the number of the previously added item, the method to change the number of the new item is called, then an exception is generated. The exception is used to return to the calling (public) method in order to reset the recursion and look for a place for an item from the top of the list.
   
   

    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. Then add the ability to remove items from the collection. This function is not difficult, if the deleted element does not have child nodes, then you can not care about their safety and destroy the element. Otherwise, I save the descendant branch of the element to be deleted, delete the required element and recursively add elements from the saved branch to the collection using the add (BinaryTreeElement element, boolean b) method.
   
   Since the object is a reference data type, you cannot simply change the current object to null; instead, the parent must remove the element reference, so the code seems complicated.
   The tactics of removing a node that has descendants is to find the minimum element in its right descendant (the right subtree) and replace the deleted element with the found one. To find the minimum element in a particular subtree, use the deleteMinChild () method.
   
   

    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. For a beautiful output of the contents of the tree, the output () method is implemented. This method scans the binary tree and displays all its elements, starting with the minimum, and the nesting of nodes can be traced by indentation. Such methods are also two-user and private:
   
   

    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. It is possible to obtain the contents of a binary tree in the form of an array, the elements of which are sorted from smaller (with a smaller number) to a larger one. The method throws a NullPointerException if there are no elements in the collection, so it is recommended to use the isEmpty () method before calling it. This method is very similar to the output () method, but it returns not the string description of the objects, but the objects themselves.
   
   

    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(); } 

The full code of the developed class, the class that implements the Comparable interface and the program that adds elements of this class to the collection is here .

I understand that the implementation is weak, suggestions for improving the developed class are welcome.