给定一棵树,例如:
我怎么说在该树中找到值 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);
}
}
最佳答案
首先,您需要一种算法来根据其值找到特定节点。这可以通过按前序、中序或后序遍历树来轻松完成(请参阅 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);
}
当然你也可以迭代遍历树,但是如果你没有非常大的树,没有理由不使用更简单的递归方法。
关于java - 如何在二叉表达式树中找到一个值?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52991790/