递归二进制搜索树插入

Question

所以这是我的第一个java程序,但我已经完成了几年的c ++.我写了我认为应该有用的东西,但实际上并没有.所以我有一个规定,必须为这个电话写一个方法:

tree.insertNode(value);

其中value是int.我想以递归的方式写它,原因很明显,所以我不得不做一个解决方法:

public void insertNode(int key) {
    Node temp = new Node(key);

    if(root == null) root = temp;

    else insertNode(temp);
}

public void insertNode(Node temp) {
    if(root == null)
        root = temp;

    else if(temp.getKey() <= root.getKey())
        insertNode(root.getLeft());

    else insertNode(root.getRight());
}

谢谢你的建议.

Answer 1

// In java it is little trickier  as objects are passed by copy.
// PF my answer below.

// public calling method

public void insertNode(int key) {
    root = insertNode(root, new Node(key));
}

// private recursive call

private Node insertNode(Node currentParent, Node newNode) {

    if (currentParent == null) {
        return newNode;
    } else if (newNode.key > currentParent.key) {
        currentParent.right = insertNode(currentParent.right, newNode);
    } else if (newNode.key < currentParent.key) {
        currentParent.left = insertNode(currentParent.left, newNode);
    }

    return currentParent;
}

Sameer Sukumaran

Answer 2

您可以使用标准Integer（原始 int 的包装）对象而不是创建新的对象类型Node。最新的 java支持Integer/int自动装箱。因此你的方法也insertNode(int key)可以接受Integer参数（确保它不为空）。

编辑：请忽略上面的评论。我不明白你真正的问题。你将不得不超载insertNode()。我想你是对的。