Поиск строки в несортированном двоичном дереве

Question

Я не уверен, что мне нужно сделать для поиска строки, хранящейся в двоичном дереве. У меня есть метод поиска, но я не совсем понимаю, что ему передать. Мне нужно найти строку перед добавлением ее в дерево. Если он найден, мне просто нужно увеличить счетчик в узловом объекте, а не добавлять новый. Кстати, дерево не сортировано.

Мой вопрос: как его найти, прежде чем добавлять его?

System.out.println("Enter string to be stored"); 
stringValue = k.nextLine(); 
if (theString.isEmpty() == true) { 
    node.add(stringValue, count); 
} else { 
    // I am not sure what to do here 
    // How do I send the string to my search method? 
    stringValue.treeSearch(); 
} 

---

public Node treeSearch(String s, TreeNode root){ 

    if(root.toString().equals(s)){ 

     return root; 
    } 
    if(left != null){ 

     left.treeSearch(s, root.left); 
     if(root.toString().equals(s)){ 
      return root; 
     } 
    } 
    if(right != null){ 

     right.treeSearch(s, root.right); 
     if(root.toString().equals(s)){ 
      return root; 
     } 
    }else{ 
      return null; 
      } 
} 

---

Я обновляю метод поиска для этого.

Answer 1

Ошибка поиска в левом и правом поддеревьях. Например:

if (left != null) { 
    left.treeSearch(s, root.left); 
    if (root.toString().equals(s)) { 
     return root; 
    } 
} 

Итак ... вы будете искать в левое поддерево, но игнорировать результат поиска и сравнения s против root ... снова.

Такая же картина повторяется для правого поддерева.

(Так как это пахнет «учебного упражнения», я оставлю вас, чтобы выяснить, исправление.)

---

Сказав, что, если вы не заказать элементы двоичного дерева , он практически бесполезен в качестве структуры данных. Вам будет лучше хранить элементы в списке или массиве. (Сложность вашего treeSearch равна O(N) ... так же, как поиск в списке или массиве.)