l'insertion de nœuds dans un arbre binaire en java question

Partie de la raison pour laquelle il est déroutant, c'est que le "Nœud" ne devrait pas être un paramètre à la méthode d'insertion, vous devriez être à l'appel d'une méthode d'insertion défini dans le nœud.

Donc, disons que vous avez la "Racine" de nœud dans votre "code"--appelons ça "rootNode" juste pour être obscur.

Ok, donc votre code à insérer dans l'arbre serait:

rootNode.insert(newValue);

Assez facile.

Maintenant de définir cette méthode.

public class Node {
    private int value;
    private Node lower;
    private Node higher;

    public void insert(int newValue) {
        if (newValue < value)
            if(lower == null)
                lower=new Node(value);
            else
                lower.insert(newValue);
        else
            if(higher == null)
                higher=new Node(value);
            else
                higher.insert(newValue);
      }

 //and you'll need a constructor
    public Node(int value) {
        this.value=value;
    }
}

Cela devrait lire beaucoup plus clairement. Je vais frapper "Post" alors je vais le modifier et de comprendre comment facilement lunette que mal, le mal de copie & coller le code.

À la réflexion, je vais le laisser là parce que c'est plus lisible. La meilleure correction que je peux voir, c'est de faire les nœuds d'un tableau, puis vous obtenez:

public class Node {

    private int value;
    private Node[] nodes=new Node[2];
    private final int LOWER=0;
    private final int HIGHER=1;

    public void insert(int newValue) {
        int index=LOWER;
        if (newValue > value)
            index=HIGHER;

        if(nodes[index] == null)
            nodes[index]=new Node(value);
            else
                nodes[index].insert(newValue);
        }
    }

Mais je ne vais pas remplacer l'original parce que, comme je l'ai dit, c'est plus clair.

Je recommande le refactoring livre pour les plus de cette. Il n'a vraiment aider à simplifier votre code une fois que vous obtenez vraiment OO. Passage d'un objet à une méthode statique (qui n'utilise pas de variables de membre) est un don mort.

Avec plus de considérations sur @ted commentaire et OO--getLeft et getRight ne devrait même pas être un problème. Il n'est ni nécessaire à l'extérieur de l'abstraction.

En général, ce que vous avez probablement besoin de ces méthodes de Nœud:

public boolean doesContain(int value) {
     if(value == this.value)
         return true
     else
         return nodes[ this.value < value ? LOWER : HIGHER].doesContain(value);
}

et peut-être

public void getValuesSorted(LinkedList l) {
    nodes[LOWER].getValuesSorted(l);
    l.put(value);
    nodes[HIGHER].getValuesSorted(l);
}

Ensuite, vous n'avez même pas besoin d'exposer que c'est un arbre que vous traitez avec--beter OO abstraction.

OriginalL'auteur Bill K

vous pouvez utiliser le code ci-dessous pour effacer de votre compréhension. La plupart du temps nous ne pas utiliser de toute autre classe, tout peut être fait à l'intérieur d'un seul Nœud de la classe elle-même. voici un exemple très simple qui, je crois, pourrait être utile... Aussi quand je vois que vous avez deux méthodes dans lequel vous avez fourni seulement des données plutôt que de la racine. Croyez-moi il vaut mieux avoir de la racine de votre classe principale. raisonnement que nous avons à portée de main, où jamais nous avons besoin de cache.

public Node insert(Node root, Node newNode) {
if (root == null) { 
    root = newNode;
} else {
    if(root.data > newNode.data) {
        root.left = insert(root.left, newNode);
    } else {
        root.right = insert(root.right, newNode);
    }
}
return root;

}

directement appeler cette méthode à partir de la classe où vous avez initialisé. voici un exemple de plz vérifier..

Node root = new Node(10);
    root.insert(root, new Node(5));
    root.insert(root, new Node(3));
    root.insert(root, new Node(6));
    root.insert(root, new Node(1));

OriginalL'auteur Vrajendra Singh Mandloi

En fait, pour un arbre binaire il n'est pas nécessaire de vérifier si l'insertion d'élément est soit supérieure ou gauche du nœud parent. Je pense qu'il n'est pas nécessaire de vérifier ces conditions. Nous devons prendre l'entrée de l'utilisateur s'insérer à droite ou à gauche.

OriginalL'auteur

Toutes vos solutions ne permettent pas de prendre en accoount qu'arriverait-il si le nœud doit être insérée dans le milieu de l'arbre. Vous êtes en supposant qu'il sera également plus petit ou plus grand. Lorsque vous insérez quelque chose dans le milieu de l'arbre, puis vous vous rendrez compte que l'opération devient plus complexe.

OriginalL'auteur ProgrammerForNow