java递归二叉搜索树插入

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

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

Answer 2

但是当你insertNode的时候，temp在哪里呢？？在当前实现中，如果root不为null，temp将丢失

我想你想要的是

root.getLeft().insertNode(temp);

及

root.getRight().insertNode(temp);

即，将新节点（temp）插入左侧或右侧子树

Answer 3

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

编辑：请忽略以上评论。我不明白你真正的问题。你必须超载insertNode()。我认为你是对的

Answer 4

// 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 5

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