Как вернуть все дубликаты двоичного дерева поиска java

Question

Я написал метод, который ищет запись в двоичном дереве поиска. Он успешно выполняет поиск значения, но я не думаю, что он найдет все дубликаты. Причина, по которой я знаю, что это не работает, заключается в том, что я пытаюсь написать другой метод, который возвращает arraylist со всеми дубликатами значения поиска. Этот метод возвращает только первое найденное значение. вот мои два метода. для метода arraylist я думаю, что я должен написать рекурсивный метод для получения всех значений, но я не уверен, как это сделать.

public T getEntry(T entry) { 
    T result = null; 
    boolean found = false; 

    BinaryNodeInterface<T> currentNode = getRootNode(); 
    while (!found && (currentNode != null)) { 
     T currentEntry = currentNode.getData(); 

     if (entry.equals(currentEntry)) { 
      result = currentEntry; 
      found = true; 
     } else if (entry.compareTo(currentEntry) < 0) 
      currentNode = currentNode.getLeftChild(); 
     else 
      currentNode = currentNode.getRightChild(); 
    } 

    return result; 
} 

public ArrayList<T> getAllEntries(T searchVal) { 
    BinaryNodeInterface<T> currentNode = getRootNode(); 
    ArrayList<T> array = new ArrayList<T>(); 
    T value = getEntry(searchVal); 
    if (value == null) 
     return array; 
    else 
     array.add(getEntry(searchVal)); 
    return array; 
} 

Answer 1

позвольте мне попробовать еще раз здесь ... я думаю, что это работает

 import java.util.ArrayList; 
     import java.util.Queue; 


     public ArrayList<T> T getallenteries(T entry) { 
      ArrayList<T> result = new ArrayList<T>(); 
      Queue<T> q=(Queue<T>) new Queue<T>(); 
      boolean found = false; 

      BinaryNodeInterface<T> currentNode = getRootNode(); 

      while ((!found||!q.isEmpty())&&currentNode!=null) { 
       if(!found)T currentEntry = currentNode.getData(); 
       if(found)T currentEntry = q.poll(); 
       if (entry.equals(currentEntry)) { 
        result.add(currentEntry); 
        found=true; 

        if(currentNode.getLeftChild()!=null)q.add(currentNode.getLeftChild()); 
        if(currentNode.getRightChild()!=null)q.add(currentNode.getRightChild()); 
       } 
       else if (entry.compareTo(currentEntry) < 0) 
        if(!found) currentNode = currentNode.getLeftChild(); 
       else{ 
        if(!found) currentNode = currentNode.getRightChild(); 
       } 
      } 

      return result;} 

Answer 2

Это кажется забавной проблемой, поэтому я решил написать код является решением сам. Это должно выполнить ваш запрос.

//class variable with duplicates. 
ArrayList<T> duplicates = new ArrayList<T>(); 

public ArrayList<T> getDuplicates(T searchVal, BinaryNodeInterface<T> currentNode) { 
    if (currentNode == null) 
     return; 

    if (currentNode.getData().equals(searchVal)) 
     duplicates.add(currentNode.getData()); //not sure why you just want to store the data. You can change this to store the node, which would be more useful. 
    else if (currentNode.getData().compareTo(searchVal) < 0) 
     getDuplicates(searchVal, currentNode.getLeftChild()); 
    else 
     getDuplicates(searchVal, currentNode.getRightChild()); 

} 

public ArrayList<T> getAllEntries(T searchVal) { 
    BinaryNodeInterface<T> root = getRootNode(); 
    T value = getEntry(searchVal); 
    if (value == null) 
     return null; 
    else 
     getDuplicates(searchVal, root); 


    if (duplicates.size() > 1) 
     System.out.println("Tree has " + duplicates.size() + " duplicates."); 
    else 
     System.out.println("There are no duplicates in the tree"); 
} 

Answer 3

Вот что я понял. Я просто использовал что-то очень похожее на мой метод getEntry, но добавил код, который был вставлен в arraylist, если у него были дубликаты.

public T getEntry(T entry) { 
    T result = null; 
    boolean found = false; 

    BinaryNodeInterface<T> currentNode = getRootNode(); 
    while (!found && (currentNode != null)) { 
     T currentEntry = currentNode.getData(); 

     if (entry.equals(currentEntry)) { 
      result = currentEntry; 
     } 
     if (entry.compareTo(currentEntry) < 0) 
      currentNode = currentNode.getLeftChild(); 
     if(entry.compareTo(currentEntry) >= 0) 
      currentNode = currentNode.getRightChild(); 
    } 

    return result; 
} 

public ArrayList<T> getAllEntries(T searchVal) { 

    ArrayList<T> array = new ArrayList<T>(); 
    T result = null; 
    boolean found = false; 

    BinaryNodeInterface<T> currentNode = getRootNode(); 
    while (!found && (currentNode != null)) { 
     T currentEntry = currentNode.getData(); 

     if (searchVal.equals(currentEntry)) { 
      array.add(currentEntry); 
     } 
     if (searchVal.compareTo(currentEntry) < 0) 
      currentNode = currentNode.getLeftChild(); 
     if(searchVal.compareTo(currentEntry) >= 0) 
      currentNode = currentNode.getRightChild(); 
    } 
    return array; 
}