реализация двоичного дерева с бесконечными циклами

Question

Я исправил проблему с помощью бесконечных циклов, но теперь, когда я пытаюсь использовать функцию find, она всегда возвращает значение null. Любые идеи о том, что происходит? Также по какой-то причине я получаю исключение NullPointerException в моей функции удаления. Пожалуйста, помогите мне здесь, ребята?

package ui; 

import java.time.LocalDate; 

import bp.BinaryTree; 

public class Main { 

    public static void main(String[] args) { 
     BinaryTree myTree = new BinaryTree(); 
     myTree.insert(LocalDate.of(2014,12,01)); 
     myTree.insert(LocalDate.of(2014,12,02)); 
     myTree.insert(LocalDate.of(2014,12,03)); 
     myTree.insert(LocalDate.of(2013,12,04)); 
     myTree.insert(LocalDate.of(2012,12,04)); 
     myTree.insert(LocalDate.of(2011,12,04)); 
     myTree.insert(LocalDate.of(2010,12,04)); 
     myTree.insert(LocalDate.of(2014,12,04)); 
     myTree.insert(LocalDate.of(2014,12,05)); 
     myTree.insert(LocalDate.of(2014,12,06)); 
     myTree.insert(LocalDate.of(2014,12,07)); 
     System.out.println(myTree); 

     System.out.println(myTree.getSize()); 
     System.out.println(myTree.showMaximumValue()); 
     System.out.println(myTree.showMinimumValue()); 
     System.out.println(myTree.find(LocalDate.of(2014,12,07))); 
} 


public class BinaryTree implements IBinaryTree { 

    public Node root = null; 
    private int sizeOfTree = 0; 


    @Override 
    public LocalDate showMinimumValue() { 
     Node current; 
     Node last=null; 
     current = root; 
     while (current != null) { 
      last = current; 
      current = current.getLeftChild(); 
     } 
     return last.getDate(); 
    } 

    @Override 
    public LocalDate showMaximumValue() { 
     Node current; 
     Node last=null; 
     current = root; 
     while (current != null) { 
      last = current; 
      current = current.getRightChild(); 
     } 
     return last.getDate(); 

    } 

    @Override 
    public boolean isEmpty() { 
     if (root == null) { 
      return true; 
     } else 
      return false; 

    } 


    public int getDepth(Node n) { 
     int currentDepth = 0; 
     int depth = 0; 
     if (n != null) { 
      currentDepth++; 

      if (currentDepth > depth) { 
       depth = currentDepth; 
      } 

      getDepth(n.getLeftChild()); 
      getDepth(n.getRightChild()); 

      currentDepth--; 
     } 
     return depth; 
    } 



    @Override 
    public int getSize() { 

     return sizeOfTree; 
    } 

    @Override 
    public void clear() { 
     root = null; 

    } 

    @Override 
    public void insert(LocalDate valueToInsert) { 
     if (isEmpty()) { 
      root = new Node(valueToInsert); 
      sizeOfTree++; 
     } else { 
      Node n = root; 
      Node oldParent = null; 
      boolean lastDirectWasLeft = false; 
      sizeOfTree++; 
      while (n != null) { 
       oldParent = n; 
       if (valueToInsert.isBefore(n.getDate())) { 
        n = n.getLeftChild(); 
        lastDirectWasLeft = true; 
       } else { 
        n = n.getRightChild(); 
        lastDirectWasLeft = false; 
       } 
      } 
      if (lastDirectWasLeft) { 
       oldParent.setLeftChild(new Node(valueToInsert)); 
      } else { 
       oldParent.setRightChild(new Node(valueToInsert)); 
      } 
     } 

    } 


    @Override 
    public void delete(LocalDate valueToDelete) { 
     Node current = root; 
     Node parent = root; 
     boolean isLeftChild = true; 

     while (current.getDate() != valueToDelete) { 
      parent = current; 
      if (valueToDelete.isBefore(current.getDate())) { 
       isLeftChild = true; 
       current = current.getLeftChild(); 
      } else { 
       isLeftChild= false; 
       current = current.getRightChild(); 
      } 
      if (current == null) { 
       break; 
      } 
     } 

     //When there is no children, cut the string 
     if(current.getLeftChild().equals(null) 
       && current.getRightChild().equals(null)) { 
      if (current == root) { 
       root = null; 
      } else if (isLeftChild) { 
       parent.setLeftChild(null); 
      } else { 
       parent.setRightChild(null); 
      } 
     } 

     //When there is no right child, replace with left child 
     else if (current.getRightChild().equals(null)) { 
      if (current == root) { 
       root = current.getLeftChild(); 
      } else if (isLeftChild) { 
       parent.setLeftChild(current.getLeftChild()); 
      } else 
       parent.setRightChild(current.getLeftChild()); 
     } 

     //When there is no left child, replace with right child 
     else if (current.getLeftChild() == null) { 
      if (current == root) { 
       root = current.getRightChild(); 
      } else if (isLeftChild) { 
       parent.setLeftChild(current.getRightChild()); 
      } else 
       parent.setRightChild(current.getRightChild()); 
     } 

     //has grandchildren, pass them to the grandpas 
     else { 
      //find the grandchildren 
      Node successor = getSuccessor(current); 
      if (current == root) { 
       root = successor; 
      } else if (isLeftChild) { 
       parent.setLeftChild(successor); 
      } else { 
       parent.setRightChild(successor); 
      } 
      //bring grandkids and granppas together 
      successor.setLeftChild(current.getLeftChild()); 
     } 

    } 



    private Node getSuccessor (Node otroNode) { 
     Node successorParent = otroNode; 
     Node successor = otroNode; 
     Node current = otroNode.getRightChild(); 
     while (current != null) { 
      successorParent = successor; 
      successor = current; 
      current = current.getLeftChild(); 
     } 

     if (successor != otroNode.getRightChild()) { 
      successorParent.setLeftChild(successor.getRightChild()); 
      successor.setRightChild(otroNode.getRightChild()); 
     } 

     return successor; 

    } 

     @Override 
    public Node find(LocalDate valueToFind) { 
     Node current = root; 
     while (current.getDate() != valueToFind) { 
      if (valueToFind.isBefore(current.getDate())) { 
       current = current.getLeftChild(); 
      } else { 
       current = current.getRightChild(); 
      } 
      if (current == null) { 
       return null; 
      } 
     } 
     return current; 

    } 

     if (isEmpty()) { 
      return null; 
     } 
     if (root.getDate().isAfter(valueToFind)) { 
      find(root.getLeftChild().getDate()); 

     } else if (root.getDate().isBefore(valueToFind)) { 
      find(root.getRightChild().getDate()); 

     } else if (root.getDate().equals(valueToFind) ) { 
      return root; 
     } 
     return null; 
     **/ 


    private String toString(Node todoElArbol) { 
     if (todoElArbol == null){ 
      return ""; 
     } else { 
      return (toString(todoElArbol.getLeftChild()) + "," 
      + todoElArbol.getDate() + "," 
      + toString(todoElArbol.getRightChild())) 
      .replaceAll(",+", ",").replaceAll("^,", "").replaceAll(",$", ""); 

     } 
    } 


    @Override 
    public String toString() { 
     return toString(root); 
    } 
} 

Класс Node:

import java.time.LocalDate; 


public class Node implements IBinaryTreeNode { 

    private LocalDate date; 

    private Node leftChild; 

    private Node rightChild; 

    public Node (LocalDate valueToInsert) { 
     date = valueToInsert; 

    } 
    @Override 
    public LocalDate getDate() { 

     return date; 
    } 

    @Override 
    public void setDate(LocalDate pDate) { 

     date = pDate; 
    } 

    @Override 
    public Node getLeftChild() { 

     return leftChild; 
    } 

    @Override 
    public void setLeftChild(Node pLeftChild) { 

     leftChild = pLeftChild; 
    } 

    @Override 
    public Node getRightChild() { 

     return rightChild; 
    } 

    @Override 
    public void setRightChild(Node pRightChild) { 

     rightChild = pRightChild; 
    } 

} 

Answer 1

Ваш бинарный поиск .... сломан.

@Override 
public Node find(LocalDate valueToFind) { 
    if (isEmpty()) { 
     return null; 
    } 
    if (root.getDate().isAfter(valueToFind)) { 
     find(root.getLeftChild().getDate()); 

    } else if (root.getDate().isBefore(valueToFind)) { 
     find(root.getRightChild().getDate()); 

    } else if (root.getDate() == valueToFind) { 
     return root; 
    } 
    return null; 
} 

Этот метод должен рекурсивно найти значение в дереве (глубина-первых поиск).

Такие методы, как, что, как правило, реализуется в двух частях, публичной части, а реализация для рекурсии:

@Override 
public Node find(LocalDate valueToFind) { 
    if (isEmpty()) { 
     return null; 
    } 
    return findRecursive(root, valueToFind); 
} 

то частный/рекурсивный метод:

private Node findRecursive(Node node, LocalDate valueToFind) { 
    if (node == null) { 
     return null; 
    } 
    if (node.getDate().isAfter(valueToFind)) { 
     return findRecursive(node.getLeftChild(), valueToFind); 
    } 
    if (node.getDate().isBefore(valueToFind)) { 
     return findRecursive(root.getRightChild(), valueToFind); 
    } 
    if (node.getDate().equals(valueToFind)) { 
     return node; 
    } 
    return null; 
} 

Обратите внимание, нет ссылок до root в рекурсивном вызове, а также сменил == на .equals(...).

Answer 2

Я предлагаю, чтобы класс Node реализовал интерфейс Comparable, тогда вы можете избавиться от метода help isBefore и isAfter, что сделает ваш код более читаемым.