遞歸二進制搜索樹插入

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