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

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

根据您的需要，您将始终必须以顺序方式（如 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);}
}

Answer 2

首先，您需要一种算法来根据其值找到特定节点。这可以通过以预序、中序或 post 顺序遍历树来轻松完成（参见 Tree Traversal on Wikipedia, especially Implementation of Depth-first search）。此算法 returns 来自递归，如果已找到该项目：

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

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

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

How to find a value in binary expression tree?

java

algorithm

binary-tree

data-structures