Insertion d'éléments dans un arbre binaire en Java

Question

J'ai écrit un code pour insérer un élément dans un arbre binaire en Java. Voici les fonctions pour faire la même chose:

public void insert(int data) 
    { 
     root = insert(root, data); 

    } 

    private Node insert(Node node, int data) 
    { 
     if (node == null) 
      node = new Node(data); 
     else 
     { 
      if (node.getRight() == null) 
       node.right = insert(node.right, data); 
      else 
       node.left = insert(node.left, data);    
     } 
     return node; 
    } 

Cependant quand je traverse l'arbre, la réponse que je reçois est fausse. Voici les fonctions traversal (pré-commande):

public void preorder() 
    { 
     preorder(root); 
    } 
    private void preorder(Node r) 
    { 
     if (r != null) 
     { 
      System.out.print(r.getData() +" "); 
      preorder(r.getLeft());    
      preorder(r.getRight()); 
     } 
    } 

Bon alors comme suggéré ici est la définition de la classe Node:

public class Node { 

    public int data; 
    public Node left, right; 

    /* Constructor */ 
    public Node() { 
     left = null; 
     right = null; 
     data = 0; 
    } 
    /* Constructor */ 

    public Node(int d, Node l, Node r) { 
     data = d; 
     left = l; 
     right = r; 
    } 

    //Constructor 
    public Node(int d) { 
     data = d; 
    } 

    /* Function to set link to next Node */ 

    public void setLeft(Node l) { 
     left = l; 
    } 
    /* Function to set link to previous Node */ 

    public void setRight(Node r) { 
     right = r; 
    } 
    /* Function to set data to current Node */ 

    public void setData(int d) { 
     data = d; 
    } 
    /* Function to get link to next node */ 

    public Node getLeft() { 
     return left; 
    } 
    /* Function to get link to previous node */ 

    public Node getRight() { 
     return right; 
    } 
    /* Function to get data from current Node */ 

    public int getData() { 
     return data; 
    } 
} 

Je revérifié l'algorithme de traversal plusieurs fois, et il travaille à la perfection. Je crois que le problème est dans l'algorithme d'insertion. Aucune suggestion?

Answer 1

Si je comprends bien, vous voulez remplir votre arbre binaire en « couches ». Par exemple. vous voulez mettre quelque chose en profondeur 4 seulement si la profondeur 3 est "arbre binaire complet". Ensuite, le problème est lié à l'ensemble de la logique de votre algorithme d'insertion basé sur DFS. En d'autres termes, il insère des éléments de plus en plus profonds d'un côté au lieu de construire un arbre binaire complet des deux côtés. Si vous regardez plus près de votre algorithme d'insertion, vous verrez qu'une fois que vous sautez la sous-arborescence "droite", vous n'y retournerez jamais - même si le sous-arbre "gauche" est déjà un arbre binaire complet. Cela mène à l'arbre qui va pousser de plus en plus profondément sur le côté gauche mais qui ne pousse pas du côté droit.

Parler en langage de programmation. Vous faites:

(node.right != null) && (node.left != null) => insert (node.left) 

mais vous ne pouvez pas le faire (commencez à insérer node.left). Que se passe-t-il si node.left a à la fois des enfants et node.right n'a pas d'enfants? Vous essayerez d'insérer à gauche même vous devriez le faire dans node.right.

Donc, ce que vous avez vraiment besoin de faire pour l'insertion basée sur BFS. Cela signifie que vous traverserez l'arbre pour l'insertion "en couches". La file d'attente devrait être votre nouvel ami ici :-) (pas la pile/récursion):

public void insert(int data) { 
    if (root == null) { 
     root = new Node(data); 
     return; 
    } 

    Queue<Node> nodesToProcess = new LinkedList<>(); 
    nodesToProcess.add(root); 

    while (true) { 
     Node actualNode = nodesToProcess.poll(); 

     // Left child has precedence over right one 
     if (actualNode.left == null) { 
      actualNode.left = new Node(data); 
      return; 
     } 
     if (actualNode.right == null) { 
      actualNode.right = new Node(data); 
      return; 
     } 

     // I have both children set, I will process them later if needed 
     nodesToProcess.add(actualNode.left); 
     nodesToProcess.add(actualNode.right); 
    } 
} 

Answer 2

Votre méthode renvoie noeud donné, mais votre méthode doit retourner noeud inséré qui est node.right ou node.left