0

我有一个 Java 中的二叉搜索树作业，其中给了我完整的 Tree 和 Node 类以及一个 SearchTree 类，我将在其中完成搜索和插入方法。搜索应该返回与搜索键对应的节点的值。

这里是 Tree 类，这里是 Node 类。我的搜索和插入方法如下。

看来我已经接近了，但是测试将键 0 和值 2 插入 Tree[Node[0,1,null,null]] 会导致 Tree[Node[0,1,null,null] 而不是正确的 Tree [节点[0,2,null,null]]。我在这里不明白什么？

public static Object search(Tree tree, int key) {
    Node x = tree.getRoot();
    while (x != null) {
        if (key == x.getKey()) {
            return x.getValue();
        }
        if (key < x.getKey()) {
            x = x.getLeft();
        } else {
            x = x.getRight();
        }            
    }
    return null;
}

public static void insert(Tree tree, int key, Object value) {
    if (tree.getRoot() == null) {
        tree.setRoot(new Node(key, value));
    }
    Node juuri = tree.getRoot();
    while (juuri != null) {
        if (key == juuri.getKey()) {
            return;
        } else if (key < juuri.getKey()) {
            if (juuri.getLeft() == null) {
                juuri.setLeft(new Node(key, value));
                return;
            } else {
                juuri = juuri.getLeft();
            }
        } else {
            if (juuri.getRight() == null) {
                juuri.setRight(new Node(key, value));
                return;
            } else {
                juuri = juuri.getRight();
            }
        }
    }
}
4

1 回答 1

1

那么我看到的问题是你的树中的关键值是独一无二的。insert在这个 if 语句中，如果您看到键已经在树中，您将离开您的方法而不添加节点。

 if (key == juuri.getKey()) { 
      return;
 }

在您的示例中（如果我理解正确） 0 已经在树中，因此再次插入 0 时没有任何变化。根据您的示例，我假设您想在密钥相同的情况下对节点进行更新。所以这段代码可以做到。

if (key == juuri.getKey()) {
     juuri.setValue(value);
     return;
}
于 2013-02-18T17:32:08.380 回答