Как эта рекурсия работает и как я могу ее распечатать?

Question

Так что я сделал реализацию BST

private String toStringHelper(Node node) { 


      if (node == null) { 
       return ""; 
      } 
      if (node.left != null) { 
       System.out.println(node.left.value); 
       toStringHelper(node.left); 

      } 

      if (node.right != null) { 
       System.out.println(node.right.value); 
       toStringHelper(node.right); 

      } 


      return ""; 
     } 

Я хочу использовать рекурсию. Проблема в том, что он не будет печатать элемент, который является моим корнем, в противном случае он работает (начало редактирования). при вставке следующих значений 100, -12, -13, -1, 0, 12, 10, 123, 122, 124. Он возвращает их в следующем порядке: -12 -13 -1 124 Который явно не заказан вообще. (Конец редактирования)

Дело в том, что я не совсем уверен в том, как работает рекурсивная часть, и я хотел бы, чтобы это объяснялось, чтобы я также мог получить способ распечатать корень в соответствующем месте ,

Answer 1

Похоже, вы передаете ему начальный узел, а затем распечатаете левые и правые поддеревья. Вам нужно распечатать значение в узле передаются как пары к методу, а затем вызвать метод на левых и правых детях узла

private String toStringHelper(Node node) { 

     if (node == null) { 
      return ""; 
     } 
     //print the value of the current node 
     System.out.println(node.value); 
     if (node.left != null) { 
      //System.out.println(node.left.value); 
      toStringHelper(node.left); 

     } 

     if (node.right != null) { 
      //System.out.println(node.right.value); 
      toStringHelper(node.right); 

     } 


     return ""; 
    } 

EDIT: Переехал заявление печатающего после нулевой проверка на корректировку OLE VV

Answer 2

Хотя ответ на оригинальный вопрос очень прост и уже отмечен другими плакатами, я хотел бы дать более подробный ответ об рекурсивном обходе дерева, может быть, это будет полезно для будущих посетителей этого поста. Существует много разных способов обхода дерева, некоторые из них «естественно» рекурсивные, некоторые из них не являются. (См. wikipedia для получения более подробной информации.) Нижеприведенный код иллюстрирует предварительный и вводный порядок глубины - первый и поиск по ширине на основе кода в OP. Из-за практических ограничений рекурсии (переполнения стека), сначала как по глубине, так и по ширине должны быть реализованы с помощью циклов с использованием стека или очереди в качестве базовой структуры данных, если только реализация не является хвостовой рекурсивной, и платформа может оптимизировать ее до цикл, но компилятор Java этого не поддерживает. В приведенном ниже коде я привожу рекурсивные примеры, потому что исходный вопрос о рекурсии, а не обход дерева.

// depth first pre-order 
// root 
// left child 
// left child of left child 
// right child of left child 
// right child 
// left child of right child 
// right child of right child 
private String toStringHelperDepthFirst(Node node) { 
    if (node == null) { 
     return ""; 
    } 
    System.out.println(node.value); 
    toStringHelper(node.left); 
    toStringHelper(node.right); 
} 

// depth first in-order 
// left child of left child 
// left child 
// right child of left child 
// root 
// left child of right child 
// right child 
// right child of right child 
private String toStringHelperDepthFirst(Node node) { 
    if (node == null) { 
     return ""; 
    } 
    toStringHelper(node.left); 
    System.out.println(node.value); 
    toStringHelper(node.right); 
} 

// depth first post-order 
// left child of left child 
// right child of left child 
// left child 
// left child of right child 
// right child of right child 
// right child 
// root 
private String toStringHelperDepthFirst(Node node) { 
    if (node == null) { 
     return ""; 
    } 
    toStringHelper(node.left); 
    System.out.println(node.value); 
    toStringHelper(node.right); 
} 

// breadth-first 
// root 
// left child 
// right child 
// left child of left child 
// right child of left child 
// left child of right child 
// right child of right child 
private void toStringHelperBreadthFirst(Node node) { 
    if(node != null) { 
     Queue<Node> queue = new LinkedList<>(); 
     queue.add(node); 
     breadhFirst(queue); 
    } 
} 

private <E> void breadthFirst(Queue<E> queue) { 
    if(queue.isEmpty()) { 
     return; 
    } 
    Node node = queue.pop(); 
    System.err.println(node.value); 
    if(node.left != null) { 
     queue.add(node.left); 
    } 
    if(node.right != null) { 
     queue.add(node.right) 
    } 
    breadhFirst(queue); 
}