Rekursiver binärer Suchbaum Einfügen

Question

Also das ist mein erstes Java-Programm, aber ich habe C++ für ein paar Jahre getan. Ich habe geschrieben, was ich denke, sollte funktionieren, aber in der Tat nicht. Also musste ich eine Methode für diesen Anruf schreiben:

tree.insertNode(value); 

wo Wert ist ein Int. Ich wollte es rekursiv schreiben, aus offensichtlichen Gründen, also musste ich um eine Arbeit tun:

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

Vielen Dank für jede Beratung.

Answer 1

Sie können das Standardobjekt Integer (Wrapper für primitive int) verwenden, anstatt einen neuen Objekttyp Node zu erstellen. Am spätesten java Integer/int Auto-Boxen wird unterstützt. Daher kann Ihre Methode insertNode(int key) das Argument Integer mitnehmen (stellen Sie sicher, dass es nicht null ist).

EDIT: Pls ignorieren obigen Kommentar. Ich habe deine wahre Frage nicht verstanden. Sie müssen insertNode() überladen. Ich glaube, Du hast recht.

Answer 2

aber wo ist Temp, wenn Sie insertNode ?? Bei der aktuellen Implementierung ist die temporäre Temperatur verloren, wenn root nicht null ist.

Ich glaube, Sie wollen etwas, wie

root.getLeft().insertNode(temp); 

und

root.getRight().insertNode(temp); 

das heißt den neuen Knoten einzufügen (temp) entweder auf der linken oder rechten Teilbaum.

Answer 3

Der Code sieht mit überladenen Funktionen etwas verwirrend aus. Unter der Annahme, Membervariablen ‚links‘ und ‚rechts‘ jeweils das linke Kind und rechtes Kind des BSTree zu sein, können Sie versuchen, es in der folgenden Art und Weise der Umsetzung:

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

Sie sollten sich diesen Artikel ansehen. Es hilft, eine Baumstruktur zu implementieren und suchen, einfügen Methoden: 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; 
}