递归二叉搜索树插入

Question

这是我的第一个Java程序，但我已经学了几年的C++。我写了我认为应该可以工作的代码，但实际上它并没有起作用。所以我必须写一个方法来调用：

tree.insertNode(value);

其中value是一个整数。由于明显的原因，我希望以递归方式编写它，所以我不得不做一个变通：

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

感谢任何建议。

- Nick Sinklier

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

- user2986935

Answer 2

代码中有一些重载函数，看起来有点混乱。假设成员变量'left'和'right'分别是BSTree的左子树和右子树，您可以尝试按照以下方式实现：

 public void insert(Node node, int value) {
    if (value < node.value)
    {
        if (node.left != null)
        {
            insert(node.left, value);
        } 
        else
        {     
            node.left = new Node(value);
        }
    } 
    else if (value > node.value)
    {
        if (node.right != null)
        {
            insert(node.right, value);
        }
        else
        {
            node.right = new Node(value);
        }
    }
}

........
public static void main(String [] args)
{ 
     BSTree bt = new BSTree();
     Node root = new Node(100);
     bt.insert(root, 50);
     bt.insert(root, 150);
}

- Arkanoid

---

如果传入的节点是null呢？我们仍然需要先设置根节点。 - DannyD

Answer 3

您应该查看这篇文章。它有助于实现树形结构和搜索、插入方法：http://quiz.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/

// This method mainly calls insertRec()
void insert(int key) {
   root = insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {

    /* If the tree is empty, return a new node */
    if (root == null) {
        root = new Node(key);
        return root;
    }

    /* Otherwise, recur down the tree */
    if (key < root.key)
        root.left = insertRec(root.left, key);
    else if (key > root.key)
        root.right = insertRec(root.right, key);

    /* return the (unchanged) node pointer */
    return root;
}

- L01c

---

我们能否将第二个方法insertRec重命名为insert，并在从主方法传递参数时，将要插入的值传递到此insert方法中，而不是创建两个不同的方法？ - Shrijan Aryal

Answer 4

但是在你的`insertNode`函数中，`temp`在哪里呢？如果根节点不为空，那么当前的实现方式下`temp`将会丢失。

我认为你可能想要这样的处理方式：

root.getLeft().insertNode(temp);

和

root.getRight().insertNode(temp);

即将新节点（temp）插入到左子树或右子树中。

- user000001

Answer 5

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

编辑：请忽略上面的评论。我没有理解您的真正问题。您将不得不重载insertNode()。我认为您是正确的。

- Bimalesh Jha