BST插入（根，值）递归方法

Question

编辑：我想出来了——放弃了这个设计，重新开始，它成功了！谢谢你的建议。

我正在做一个BST算法的家庭作业，我绝望地被困在插入方法上。我在网上找到的所有资源都有一个与我创建的版本相似的版本，但是我没有通过教授给我们的JUnit测试。我可以通过基本情况（root.payload==value的空根和二叉树）。不过，我似乎无法通过下一个测试。这是我的插入（root， value）方法代码：

public static Node<Integer> insert(Node<Integer> root, Integer value) {
    if (root == null) {
        root = new Node<>(value);
    } else if (root.payload.equals(value)) {
        return root;
    } else if (value < root.payload) {
        return root.left = insert(root.left, value);
    } else {
        return root.right = insert(root.right, value);
    }
    return root;
}

最终返回的是原始的根节点，但根据我的理解，最后返回的值应该是我的新节点。我看了我的教科书和一些在线资源，它们都有与此设计非常相似的东西，所以我很困惑为什么它不起作用。我尝试了一些其他设计，但它们最终都是NullPointerException。给我们的JUnit测试验证我们是否将节点插入了正确的位置，此外还检查了Node的有效负载。我没有通过这两个测试。这是我们第一次使用递归的作业，所以我在这方面还是相当新手。如果有任何指导，将不胜感激！

Answer 1

public static Node<Integer> insert(Node<Integer> root, Integer value) {
    if (root == null) {
        root = new Node<>(value);
    } else if (value < root.payload) {
         root.left = insert(root.left, value);
    } else if (value > root.payload) {
         root.right = insert(root.right, value);
    }
    return root;
}

这将在正确的位置添加值并返回根。您可以打印树以检查是否相同

Answer 2

如果您希望方法中返回的值是新插入的节点，您还必须在elseIF子句中添加返回语句，以便在递归堆栈展开时返回新创建的节点。检查下面的代码

public static Node<Integer> insert(Node<Integer> root, Integer value) {
if (root == null) {
    root = new Node<>(value);
} else if (value <= root.payload) {
    return root.left = insert(root.left, value);   // add a return here
} else {
   return  root.right = insert(root.right, value);  // add a return here
}
return root;

}