Выйти из бинарного предварительного обхода до завершения

У меня есть бинарное дерево, состоящее из различных узлов. Я хочу пройти по дереву, используя рекурсию предварительного порядка, найти узел с подходящим описанием (описание) и вернуть его, если он существует. Однако обход продолжает завершаться. Есть ли логическая ошибка, которую я делаю, или алгоритм обхода не подходит?

Вот функция отказа от обхода предварительного заказа, и я вызываю ее ниже:

public Node replaceNodes(Node currentNode, int itemId, String desc) {

if (currentNode == null) {
    System.out.println("null");
}

if (currentNode != null) {
    //System.out.println(desc + " " + currentNode.getDesc());
    if (currentNode.getDesc().matches(desc) 
            && currentNode.getKey() != itemId) {
        System.out.println("returned");
        return currentNode;
        //System.out.println(currentNode.getDesc());
    } else {
        replaceNodes(currentNode.leftChild, itemId, desc);
        replaceNodes(currentNode.rightChild, itemId, desc);
        //System.out.println("replace");
    }
} 

return null;
}


  Node replaceItem = r1Items.replaceNodes(r1Items.
                            getRoot(), searchId, searchNode.getDesc());
                    //check suitable item found

Спасибо. С удовольствием уточню, если нужно.


java binary-tree preorder
person user2699584    schedule 24.03.2015    source источник
comment
Когда вы вызываете метод рекурсивно, вы должны проверить результат, полученный вашими рекурсивными вызовами (replaceNodes(currentNode.leftChild,... и для rightChild), если результат для левого поиска равен null, продолжить правый поиск и вернуть результат правого поиска. Если левый результат поиска не null, верните его.   -  person tomse    schedule 24.03.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

Я думаю, вам нужно что-то вроде следующего в операторе else.

. . . 
} else {
   Node left = replaceNodes(currentNode.leftChild, itemId, desc);
   if(left != null) { return left; }
   Node right = replaceNodes(currentNode.rightChild, itemId, desc);
   if(right != null) { return right; }
}
. . .

Далее немного упрощено

. . . 
} else {
   Node left = replaceNodes(currentNode.leftChild, itemId, desc);
   if(left != null) { return left; }
   return replaceNodes(currentNode.rightChild, itemId, desc);
}
. . .
person FriedSaucePots    schedule 24.03.2015