Метод рекурсивного шифрования дерева с использованием dfs

Question

Эта проблема не для задания, хотя это несколько типичная проблема с назначением, которую я пытаюсь решить по-другому.

Я хочу написать метод, который будет рекурсивно проходить через двоичное дерево, используя алгоритм поиска глубины, чтобы найти совпадение для символа. Когда он найдет соответствующий символ, я хочу, чтобы он возвращал строку, которая отображает позицию символа в дереве с помощью 0 и 1. Например, «001» указывает, что символ найден, перейдя в левый узел корневого узла, левый узел этого узла, а затем в правый узел этого узла.

Вот код, который я до сих пор:

private static String encryptSearch(char c, BinaryNode curNode, String result) 
{ 
    char data = (char) curNode.getData(); 

    if (data != c) 
    { 
     if (curNode.hasLeftChild()) 
     { 
      result = result + "0"; 
      encryptSearch(c, curNode.getLeftChild(), result); 
     } 
     if (curNode.hasRightChild()) 
     { 
      result = result + "1"; 
      encryptSearch(c, curNode.getRightChild(), result); 
     } 

     result = result.substring(0, result.length()-1); 
    } 

    return result; 
} 

Метод изначально отправлен символ, который будет искать, корневой узел, а нуль результата. Этот метод не возвращает ничего, кроме 0. Я думаю, что есть несколько проблем с моим кодом, но самый большой из них заключается в том, что когда поиск достигает листового узла, он возвращается. Я не мог придумать способ решения этой проблемы, все еще вернув строку. Я мог бы легко написать метод void, который действует на результирующую строку как внешнюю переменную, но я не хочу этого делать с целью упражнения. Любая помощь приветствуется!

Answer 1

Используйте изменяемый StringBuilder вместо String. Также должен быть способ узнать, что вы получили результат с левой (если есть), прежде чем искать правильный. Поэтому я предлагаю следующие изменения.

private static boolean encryptSearch(char c, BinaryNode curNode, StringBuilder result) { 
    char data = curNode.getData(); 
    if (data != c) { 
     boolean found = false; 
     if (curNode.hasLeftChild()) { 
      found = encryptSearch(c, curNode.getLeftChild(), result); 
      if (found) { 
       result.insert(0, "0"); 
       return true; 
      } 
     } 
     if (curNode.hasRightChild()) { 
      found = encryptSearch(c, curNode.getRightChild(), result); 
      if (found) { 
       result.insert(0, "1"); 
       return true; 
      } 
     } 
     return false; //no result 
    } 
    return true; 
}