Как найти значение в бинарном дереве выражений?

Question

Для дерева, например, например:

Как я могу сказать, найти значение 3 (не важно, какое значениеиз 3, но после того, как один найден, поиск должен завершиться) в этом дереве и, возможно, изменить его на 7 или другое число, но после этого прекратить обход дерева?Все алгоритмы, которые я нашел в сети, всегда будут проходить по всему дереву, или когда они ищут определенное значение, тогда это BST, который здесь не применим.Я не могу предоставить пример кода, так как не знаю, с чего начать с этой проблемой.

class Node {

    String value;
    Node left, right;

    Node(String item) {
        value = item;
        left = right = null;
    }

    boolean isLeaf() {
        return (left == null) && (right == null);
    }
}

Answer 1

Во-первых, вам нужен алгоритм, чтобы найти конкретный узел на основе его значения.Это может быть легко сделано путем обхода дерева в предварительном порядке, в порядке или после заказа (см. Обход дерева в Википедии , особенно Реализация поиска в глубину ).Этот алгоритм возвращается из рекурсии, если элемент был найден:

Node findNode(Node root, String value) {
    if (root == null) return null; // no such node
    if (value.equals(root.getValue())) return root; // the node itself contains the value

    Node n = findNode(root.getLeft(), value); // search left sub-tree
    if (n != null) return n; // we've found it in the left sub-tree

    return findNode(root.getRight(), value); // search right sub-tree
}

После этого можно легко поменять значение в дереве:

void exchange(Node root, String value, String newValue) {
    Node n = findNode(root, value);
    n.setValue(newValue);
}

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

Answer 2

В зависимости от того, что вы хотите, вам всегда придется начинать обход своего дерева от корневого элемента (я предполагаю, что у вас изначально есть доступ к корню) последовательным образом (как в BFS или DFS).Поскольку ваше дерево не является BST (или деревом, имеющим какие-то особые отношения между узлами), мы не сможем выполнить поиск определенного узла быстрее, чем обычный последовательный поиск по всем узлам.

ПримерПсевдокод BFS;

Initialize Queue q;
q.add(root);

while(q is not empty){
    Node node = q.pop();

    if(Node equal to 3){ // or any value you want
        node.val = 7;
        return;
    }

    if(node.left!=null){q.add(node.left);}
    if(node.right!=null){q.add(node.right);}
}