Sortie incorrecte: Implémentation de l'arbre de recherche binaire en utilisant Java

Question

Je suis nouveau à Java et j'ai essayé d'implémenter un BST mais le programme ne sort que la dernière valeur insérée. Est-ce que je me trompe en ce qui concerne ce que mon root_node montre? Voici mes codes sources pour Tree.java et Node.java.

Tree.java

public class Tree { 

    private Node root_node; 

    public void Tree() { 
     this.root_node = null; 
    } 

    public void insertNode (int value) { 

     root_node = insertNode(root_node, value); 
    } 

    public Node insertNode (Node node, int insert_value) { 

     if (node == null) { 
      return (new Node(insert_value)); 
     } 
     else { 
      if (node.getNodeValue() < insert_value) 
       node = insertNode(node.getLeftNode(), insert_value); 
      else 
       node = insertNode(node.getRightNode(), insert_value); 

      return (node); 
     } 
    } 

    public void printNode() { 

     printNode(root_node); 
    } 

    public void printNode (Node node) { 

     if (node != null){ 

      System.out.print(node.getNodeValue() + " "); 

      printNode(node.getLeftNode()); 
      printNode(node.getRightNode()); 
     } 
    } 

    public static void main(String[] args) { 

     Tree tree = new Tree(); 

     tree.insertNode(54); 
     tree.insertNode(87); 
     tree.insertNode(11); 
     tree.insertNode(25); 

     tree.printNode(); 
    } 
} 

Node.java

public class Node { 

    private int node_value; 

    private Node left_node, right_node; 

    public Node(int root_value) { 

     this.node_value = root_value; 

     this.left_node = null; 
     this.right_node = null; 

    } 

    public int getNodeValue() { return (this.node_value); } 

    public Node getLeftNode() { return (this.left_node); } 

    public Node getRightNode() { return (this.right_node); } 
} 

L'erreur est que mon code source affiche uniquement le dernier pas inséré. ce qui est de 25 dans ce cas.

Answer 1

L'implémentation de insertNode est incorrecte. Vous appelez toujours cette méthode avec:

root_node = insertNode(root_node, value); 

Et si vous regardez la méthode:

if (node == null) { 
    return (new Node(insert_value)); 
} 
else { 
    if (node.getNodeValue() < insert_value) 
     node = insertNode(node.getLeftNode(), insert_value); 
    else 
     node = insertNode(node.getRightNode(), insert_value); 

    return (node); 
} 

Au premier appel, la première condition if correspondra , un nouveau nœud sera créé et affecté à root_node dans l'appelant.

Mais alors, dans les appels suivants, que se passera-t-il? Le premier if ne correspond pas, donc le bloc else sera pris. Mais alors, les deux branches réaffectent le paramètre node de la méthode. Ainsi, les effets de la méthode else resteront dans la méthode insertNode, donc aucune autre valeur ne sera ajoutée. Outre la réécriture de la méthode insertNode, vous aurez également besoin d'autres modifications. Par exemple, actuellement il n'y a aucun moyen de définir ou de modifier les nœuds gauche et droit d'un nœud. Vous devrez ajouter quelque chose pour cela, soit par des setters ou des constructeurs.

Par exemple, avec les setters ajoutés, cela fonctionnera:

public Node insertNode(Node node, int insert_value) { 
    if (node == null) { 
     return new Node(insert_value); 
    } 
    if (node.getNodeValue() < insert_value) { 
     node.setLeftNode(insertNode(node.getLeftNode(), insert_value)); 
    } else { 
     node.setRightNode(insertNode(node.getRightNode(), insert_value)); 
    } 
    return node; 
    } 

Answer 2

Ce qui semble arriver est que cette erreur sur:

Vous créez votre root_node avec le premier appel (devrait être appelé rootNode conventions suivantes java). Ensuite, vous appelez soit getLeftNode ou getRightNode, mais ceux-ci n'existent pas, donc je suppose qu'ils retournent null.

 if (node.getNodeValue() < insert_value) 
      node = insertNode(node.getLeftNode(), insert_value); 
     else 
      node = insertNode(node.getRightNode(), insert_value); 

renvoie null au deuxième appel. Maintenant, votre root_node est à nouveau vide, ce qui signifie que vous n'avez que la dernière valeur insérée, etc. Cela semble donc être la raison pour laquelle votre code ne renvoie que la dernière valeur de nœud lorsque vous appelez print.

Answer 3

En vous Tree classe, le mehtod public Node insertNode (Node node, int insert_value) est pas correctement, Shoude comme ceci:

 if (node.getNodeValue() < insert_value) { 
      Node left = insertNode(node.getLeftNode(), insert_value); 
      node.left_node = left; 
     } 

     else { 
      Node right = insertNode(node.getRightNode(), insert_value); 
      node.right_node=right; 
     } 

vous devez sauver la nouveau nœud qui retourne par le insertNode dans le champ de nœud leftchild ou le champ de nœud rightchild dans lequel nœud actuel, sinon, le printNode va juste imprimer le nœud root et retourner, car le root Le nœud enfant gauche ou droit du nœud est null.