Récursive Binaires De Recherche Arbres Insérer

Donc c'est mon premier programme en java, mais j'ai fait du c++ pour quelques années. J'ai écrit ce que je pense devrait fonctionner, mais en fait il ne l'est pas. J'ai donc eu une stipulation d'avoir à écrire une méthode pour cet appel:

tree.insertNode(value);

où la valeur est un entier (int).
Je voulais l'écrire de manière récursive, pour des raisons évidentes, j'ai eu à faire un travail autour de:

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

Merci pour tous les conseils.

InformationsquelleAutor Nick Sinklier | 2013-02-12
  1. 18
    //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

    InformationsquelleAutor user2986935
  2. 3

    Le code ressemble un peu à confusion avec les fonctions surchargées. En supposant que les variables membres de "gauche" et "droite" à la gauche de l'enfant et de droit de l'enfant de la BSTree respectivement, vous pouvez essayer de la mise en œuvre de la façon suivante:

     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);
}
    • que faire si le nœud passé en est null? Nous aurions encore besoin de définir le nœud racine de la première
    InformationsquelleAutor Arkanoid
  3. 1

    Vous devriez jeter un oeil à cet article. Il contribue à mettre en œuvre une structure de l'arbre et de la recherche, méthodes d'insertion:
    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;
}
    • Pouvons-nous simplement renommer la deuxième méthode - insertRec à insérer et tout en passant des paramètres de la méthode main, passer la valeur à insérer à cette méthode insert au lieu de créer 2 méthodes différentes ?
    InformationsquelleAutor L01c
  4. 0

    Vous pouvez utiliser les Integer (wrapper pour la primitive int) de l'objet au lieu de créer un nouveau type d'objet Node. Sur la dernière version de java Entier/int auto-boxing est pris en charge. Par conséquent, votre méthode insertNode(int key) peut prendre en Integer argument trop (s'assurer qu'il n'est pas null).

    EDIT: Pls ignorer le commentaire ci-dessus. Je ne comprends pas votre question. Vous devrez surcharge insertNode(). Je pense que vous avez raison.

    InformationsquelleAutor Bimalesh Jha
  5. 0

    mais où est temp quand vous insertNode?? Avec votre actuel de mise en œuvre de temp est perdu si la racine n'est pas null.

    Je pense que vous voulez quelque chose comme 

    root.getLeft().insertNode(temp);

    et 

    root.getRight().insertNode(temp);

    c'est à dire À insérer le nouveau Nœud (temp) vers la gauche ou la droite de la sous-arborescence.

    InformationsquelleAutor user000001