java - Recursive Binary Search Tree Insert

Question

So this is my first java program, but I've done c++ for a few years. I wrote what I think should work, but in fact it does not. So I had a stipulation of having to write a method for this call:

tree.insertNode(value);

where value is an int. I wanted to write it recursively, for obvious reasons, so I had to do a work around:

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

Thanks for any advice.

score 18 · Accepted Answer

// 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;
}

萨米尔·苏库马兰

score 3 · Accepted Answer

代码看起来与重载函数有点混淆。假设成员变量 '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);
}

score 2 · Accepted Answer

你应该看看这篇文章。它有助于实现树形结构和搜索、插入方法：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;
}

score 0 · Accepted Answer

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

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

score 0 · Accepted Answer

但是当你的时候温度在哪里insertNode？？如果 root 不为空，您当前的实现 temp 会丢失。

我想你想要类似的东西

root.getLeft().insertNode(temp);

和

root.getRight().insertNode(temp);

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

java - Recursive Binary Search Tree Insert

5 回答 5

Related

Reference