递归二进制搜索树插入

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

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

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

Answer 2

但是，当你在哪里温度insertNode？使用当前的实现如果root不为null，则temp会丢失。

我想你想要像

root.getLeft().insertNode(temp); 

和

root.getRight().insertNode(temp); 

即要插入新的节点（TEMP）到左或右子树。

Answer 3

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

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

萨米尔Sukumaran

Answer 5

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