java - 如何在二叉表达式树中找到一个值？

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

首先，您需要一种算法来根据其值找到特定节点。这可以通过按前序、中序或后序遍历树来轻松完成(请参阅 Tree Traversal on Wikipedia ，尤其是 Implementation of Depth-first search )。如果找到该项目，则此算法从递归返回:

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);
}

当然你也可以迭代遍历树，但是如果你没有非常大的树，没有理由不使用更简单的递归方法。