Нуждаюсь в помощи в возврате из рекурсивного метода
Я пытаюсь проследить путь узла в двоичном дереве (не дерево двоичного поиска). Учитывая узел, я пытаюсь распечатать значения пути от корня.
Я записал следующую программу.
package dsa.tree;
import java.util.Stack;
public class TracePath {
private Node n1;
public static void main(String args[]){
TracePath nodeFinder = new TracePath();
nodeFinder.find();
}
public void find(){
Tree t = getSampleTree();
tracePath(t,n1);
}
private Tree getSampleTree() {
Tree bsTree = new BinarySearchTree();
int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
for(int i=0;i<randomData.length;i++){
bsTree.add(randomData[i]);
}
n1 = bsTree.search(76);
return bsTree;
}
public void tracePath(Tree t, Node node){
trace(t,node);
}
Stack<Node> mainStack = new Stack<Node>();
public void trace(Tree t, Node node){
trace(t.getRoot(),node);
}
private void trace(Node parent, Node node){
mainStack.push(parent);
if(node.data == parent.data){
for(Node iNode:mainStack){
System.out.println(iNode.data);
}
return;
}
if(parent.left != null){
trace(parent.left, node);
}
if(parent.right!=null){
trace(parent.right, node);
}
mainStack.pop();
}
}
Я получаю вывод правильно. Но его довольно грязное. Если Вы видите трассировку метода (Узел, Узел), я печатаю значения, которые я не должен делать. Я хочу, чтобы метод трассировки правильно завершился. По крайней мере, я должен уничтожить рекурсивную структуру на этапе, с которым я встречаюсь если условие.
Советуйте.
5 ответов
Возвращает логическое значение из трассировки и определяет необходимость продолжения поиска на основе значения, возвращаемого рекурсивным вызовом.
-121--4780066- Пробовали ли вы использовать < C _ x > < C-] > ?
Хорошо, вам нужно убить рекурсию, как только вы найдете свой узел. Достаточно просто. Измените метод трассировки, чтобы вернуть логическое значение, сообщающее, найден ли узел. Таким образом, мы возвращаемся к дереву сразу после нахождения узла.
private boolean trace(Node parent, Node node){
mainStack.push(parent);
if(node.data == parent.data){
for(Node iNode:mainStack){
System.out.println(iNode.data);
}
return true;
}
if(parent.left != null){
if (trace(parent.left, node)) return true;
}
if(parent.right!=null){
if (trace(parent.right, node)) return true;
}
mainStack.pop();
return false;
}
Я предполагаю, что это домашнее задание, поэтому я дам несколько указателей вместо кода.
- ваш метод трассировки выполняет рекурсивный спуск, поэтому стек не нужен - вы можете построить структуру пути при возврате из найденного узла
- , если ваш метод использует возвращаемое значение типа boolean или List, вы можете распечатать путь, пока или создайте список с узлами для печати после того, как метод поиска вернет
Изменить : Если требуется путь узла к корню, достаточно простого логического возврата:
private boolean trace(Node parent, Node node) {
boolean found = (node.data == parent.data)
if (!found && parent.left != null) {
found = trace(parent.left, node);
}
if (!found && parent.right != null){
found = trace(parent.right, node);
}
if (found) {
System.out.println(parent.data);
}
return found;
}
Если вы вам нужен путь от корня к узлу, вы можете передать список для получения узлов по порядку:
private boolean trace(Node parent, Node node, List path) {
boolean found = (node.data == parent.data)
if (!found && parent.left != null) {
found = trace(parent.left, node);
}
if (!found && parent.right != null){
found = trace(parent.right, node);
}
if (found) {
path.add(0, parent);
}
return found;
}
в качестве альтернативы вы можете построить путь на обратном пути и вернуться в виде списка.
private List trace(Node parent, Node node) {
List path = null;
if (null != node) {
if (node.data == parent.data) {
path = new ArrayList();
} else {
path = trace(parent.left, node);
if (null == path) {
path = trace(parent.right, node);
}
}
if (null != path) {
path.add(0, parent);
}
}
return path;
}
Что-то вроде этого?
public Stack<Node> findPath(Node src, Node dest, Stack<Node> alreadyCollected) {
if (src == dest)
return alreadyCollected;
if (src.left == null && src.right == null)
return null;
if (src.left != null) {
Stack<Node> toTheLeft = new Stack<Node>(alreadyCollected);
toTheLeft.push(src.left);
Stack<Node> result = findPath(src.left, dest, toTheLeft);
if (result != null)
return result;
}
List<Node> toTheRight = new Stack<Node>(alreadyCollected);
return findPath(src.right, dest, toTheRight);
}
Возвращает логическое значение из трассировки и решает, продолжать ли поиск на основе значения, возвращаемого рекурсивным вызовом.
Вот рекурсивная функция без использования стека. Рекурсия технически эквивалентна стеку, и вам не нужен стек при рекурсии.
PS: Я пишу псевдокод. Перепишите его сами, чтобы он скомпилировался :)
bool trace(Node curr, Node n, Path path){
if(curr == null)
return;
if(n == curr){
path.insertAtEnd(curr);
return true;
}
if(trace(curr.left, n, path)){
path.insertAtEnd(curr);
return true;
}
if(trace(curr.right, n, path)){
path.insertAtEnd(curr);
return true;
}
return false
}