Binären Baum Kinder setzen

[Maultäschle]

Hey,
hab volgendes Problem:
Wenn ich neue knoten hinzufüge, dann bezieht der sich immer auf den Vorgänger, daher kann es sein, dass nicht immer die Zhlen im linken Teilbaum echt kleiner als die Wurzel sind.

    public void setRechtesKind(IBinaryTreeNode<T> rechts) {

        IBinaryTreeNode<T> wurzel = new BinaryTreeNode<T>();

        if (wurzel.getValue().compareTo(rechts.getValue()) > 0) {
            throw new IllegalArgumentException();
        } else if (wurzel.getValue().compareTo(rechts.getValue()) == 0) {
System.out.println("Gleicher Knotenwert!!!!!!");
        } else {
            this.rechts = rechts;
        }

    }

 

[mrBrown]

Wenn ich neue knoten hinzufüge, dann bezieht der sich immer auf den Vorgänger, daher kann es sein, dass nicht immer die Zhlen im linken Teilbaum echt kleiner als die Wurzel sind.

Dein Code zeigt nur den rechten, aber warum sollte das nicht sicher gestellt werden können?

 

[Maultäschle]

Ging eigentlich ums Prinzip. Nicht so sehr um die Richtung. Naja, wenn ich zum Beispiel mit 37 anfange. Rechts Kind 38. Linkes Kind 35. Das rechte Kind vom linken Kind ist 40. Und dann wäre die linke Seite nicht mehr echt kleiner als die Wurzel

 

[mrBrown]

Wie sollte denn die 40 überhaupt links eingeordnet werden?
Wenn man sie einfach dahin setzt, ohne den Regeln zu folgen, ist ja klar dass die Regeln nicht mehr gelten...

 

[Maultäschle]

Kann ich es aber nicht irgendwie programmieren, dass praktisch immer geprüft wird, dass sowas nicht passiert...

 

[mrBrown]

Ja natürlich, das ist doch der Sinn des ganzen. Einen Binärbaum zu schreiben, der die nicht richtig einsortiert hat doch wenig Sinn...

 

[Robat]

Eine Möglichkeit es zu machen wäre es in deiner Add Methode eine rekursive traverse Methode aufzrufen, die solange durch den Baum geht bis sie einen Platz gefunden hat wo sie das Element einfügen kann.
Als kleine Anregung vielleicht mal eine Art Pseudocode:

void add(Node node)
{
     IF root = null
         root = node;
     ELSE
         traverse(root, node);
}

void traverse(Node current, Node nodeToAdd)
{
    IF current.data < nodeToAdd.data
         IF current.left = nul
               current.left = nodeToAdd
         ELSE 
               traverse(current.left, nodeToAdd);
    ELSE IF current.data > nodeToAdd.data
          IF current.right = null
               current.right = null
          ELSE
                traverse(current.right, nodeToAdd);
}

Gruß Robert

 

[Maultäschle]

Muss ich dann die setLinkesKind Methoden löschen?

 

[Maultäschle]

Hab es jetzt so gemacht, jedoch funktioniert es nicht. Findet ihr den Fehler?

    public void add(BinaryTreeNode<T> current) {
        if (root == null) {
            root = current;
        } else {
            traverse((BinaryTreeNode<T>) root, current);
        }
    }

    public void traverse(BinaryTreeNode<T> current, BinaryTreeNode<T> nodeToAdd) {
        if (current.getValue().compareTo(nodeToAdd.getValue()) > 0) {
            if (current.left == null) {
                current.left = nodeToAdd;
            } else {
                traverse((BinaryTreeNode<T>) current.left, nodeToAdd);

            }
        } else if (current.getValue().compareTo(nodeToAdd.getValue()) < 0) {
            if (current.right == null) {
                current.right = nodeToAdd;
            } else {
                traverse((BinaryTreeNode<T>) current.right, nodeToAdd);
            }
        } else {
            System.out.println("Do nothing");
        }
    }

    public static void main(String[] args) {
        BinaryTreeNode<Integer> neu = new BinaryTreeNode<Integer>();
        System.out.println(neu.getValue());
        neu.setValue(60);
        BinaryTreeNode<Integer> cuurent = new BinaryTreeNode<>();
        cuurent.setValue(42);
        neu.add(cuurent);
        neu.traverse(neu, cuurent);
        System.out.println(neu.getLeftChild());

 

[stg]

Wie in deinen anderen Themen auch:
WAS funktioniert denn nicht? Wie äußert sich dieses "funktioniert nicht". Das soll hier kein Such- und Ratespiel für die anderen sein, sondern DU möchtest doch Hilfe haben.

 

[Robat]

Ich glaube du hast den Sinn dieser traverse(BinaryTreeNode<T> current, BinaryTreeNode<T> nodeToAdd) im Zusammenspiel mit der add(BinaryTreeNode<T> current) noch nicht ganz verstanden.
Immer wenn du ein neues Element adden willst soll folgendes geschehen:
- Wenn der Baum leer ist, dann soll das Element das neue root-Element werden (geschieht bereits in deiner add Methode)
- Wenn der Baum nicht leer ist soll die traverse(..) Methode aufgerufen werden mit dem root Element und dem Element welches geadded werden soll (geschieht bereits in deiner add Methode)

Die traverse(..) sollst du aber niemals selber von außen aufrufen, schon gar nicht mit den Parametern die du momentan übergibst. Ziel der traverse(..) ist es ja, beim root Element anzufangen und dann so lange vorzudringen, bis es einen Platz findet wo das Element, welches hinzugefügt werden soll, rein passt. Du musst also einfach nur add() aufrufen um ein Element hinzuzufügen.

Kleine Frage am Rande:

BinaryTreeNode<Integer> neu = new BinaryTreeNode<Integer>();
...
BinaryTreeNode<Integer> cuurent = new BinaryTreeNode<>();
...
neu.add(cuurent);

Warum rufst du die add(..) über ein BinaryTreeNode<T> Element auf? Ein einzelnes Element braucht doch keine add Methode?
Die gehört eigentlich in die BinaryTree (oder wie auch immer die bei dir heißen mag) Klasse.

---

Ich muss @stg Recht geben.

Hab es jetzt so gemacht, jedoch funktioniert es nicht. Findet ihr den Fehler?

Ist keine Fehlerbeschreibung. Einfach 1, 2 Sätze (mit eventuellem StackTrace) die beschreiben was passiert und was passieren soll. Schon kann man damit arbeiten und vor allem schneller zu einer Lösung kommen

Gruß Robert

 

[Maultäschle]

Okay, dann versuch ich mich künfrig besser auszudrücken.
Nun, meine Frage:
Wie rufe ich dann die add Methode auf?

 

[Robat]

Okay, kurzes Minimalbeispiel:

public class BinaryTree
{
     private Node node;

     public BinaryTree() {
           node = null;
     }
   
     public void add(Node node)
     {
          // so wie besprochen
          ...
     }

     private void traverse(...)
     {
           // so wie besprochen
           ....
     }
}

public class Node
{
     // irgendeine Node Klasse
     private Node nodeLeft;
     private Node nodeRight;
     private int data;

     public Node(int data)
     {
           this.data = data;
     }
    ...
}

public class TestBinaryTree
{
     // irgendeine Klasse zum testen
     public static void main(String[] args)
     {
           BinaryTree tree = new BinaryTree();
      
            Node node1 = new Node(50);    // ---> sollte zum root Element werde
            Node node2 = new Node(25);    // ---> sollte zum leftNode des roots werden
            Node node3 = new Node(75);   // --> sollte zum rightNode des roots werden
            Node node4 = new Node(30);   // --> sollte zum rightNode von node2 werden
  
           tree.add(node1);
           tree.add(node2);        
           tree.add(node3);
           tree.add(node4);
     }
}

Vielleicht hilft dir das ja zu verstehen, was wir in den letzten Posts besprochen haben.