Inserimento ricorsivo nella ricerca binaria

Question

Quindi questo è il mio primo programma java, ma ho fatto C++ per alcuni anni. Ho scritto quello che penso dovrebbe funzionare, ma in realtà non lo è. Così ho avuto una clausola di dover scrivere un metodo per questa chiamata:

tree.insertNode(value); 

dove il valore è un int. Ho voluto scrivere in modo ricorsivo, per ovvie ragioni, così ho dovuto fare un lavoro intorno:

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

Grazie per qualsiasi consiglio.

Answer 1

È possibile utilizzare l'oggetto standard Integer (wrapper for primitive int) invece di creare un nuovo tipo di oggetto Node. È disponibile l'ultimo java Integer/int auto-boxing. Quindi il tuo metodo insertNode(int key) può contenere anche l'argomento Integer (assicurati che non sia nullo).

MODIFICA: i Pls ignorano il commento sopra. Non ho capito la tua vera domanda. Dovrai sovraccaricare lo insertNode(). Penso che tu abbia ragione.

Answer 2

ma dove è temp quando si insertNode ?? Con la tua attuale implementazione, la temp è persa se root non è nullo.

Penso che si desidera qualcosa di simile

root.getLeft().insertNode(temp); 

e

root.getRight().insertNode(temp); 

vale a dire Per inserire il nuovo nodo (temp) sia alla sottostruttura sinistra o destra.

Answer 3

Il codice sembra un po 'di confusione con le funzioni sovraccariche. Assumendo variabili membro 'sinistra' e 'destra' di essere, rispettivamente, il figlio sinistro e figlio destro del BSTree, si può provare la sua attuazione nel modo seguente:

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

Sameer Sukumaran

Answer 5

Dovresti dare un'occhiata a questo articolo. Aiuta a implementare una struttura ad albero e la ricerca, i metodi di inserimento: 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; 
}