Datenstruktur auf SET prüfen in O(n)

Bitte aktiviere JavaScript!
Etwas wie:

Java:
    public boolean isSet() {
        AtomicBoolean hasSetProperty = new AtomicBoolean(true);
        Consumer<X> visitor = new Consumer<X>() {
            private X previous;

            public void accept(X current) {
                if (previous != null && previous.compareTo(current) == 0) {
                    hasSetProperty.set(false);
                }
            }
        };

        visitInorder(root, c);

        return c.get().
    }

    private void visitInorder(Node<T> n, Consumer<T> c) {
        if (n != null) {
            visitInorder(n.getLeft(), c);
            c.accept(n.value);
            visitInorder(n.getRight(), c);
        }
    }
 
Da fällt mir auf, das sollte auch ohne Visitor funktionieren.
Bevor der Visitor in's Spiel kam, hatte ich folgenden Gedanken:
Java:
    public boolean isSet() {
        return isSet(root, null);
    }
    
    private boolean isSet(Node currentNode, X stillSuspicious) {
        if (currentNode==null) {
            return true;
        } else if (currentNode.value.equals(stillSuspicious)) {
            return false;
        } else if (!isSet(currentNode.right, stillSuspicious)) {
            return false;
        } else {
            return isSet(currentNode.left, currentNode.value);
        }
    }
EDIT: Formatierungsfehler beseitigt
 
Zuletzt bearbeitet:
Ich weiß leider nicht was ein Visitor ist :(
Aus diesem Grund kann ich leider auch nicht viel mit deinem Code anfangen @mihe7
sorry!

if (!isSet(currentNode.right, stillSuspicious)) { return false;
o_O kann mir das irgendwie jemand erklären.

Ich hatte gestern Abend eben noch die Idee In-Order Iterativ zu machen.
Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
current -> 1
push 1: Stack S -> 1
current -> 2
push 2: Stack S -> 2, 1
current -> 4
push 4: Stack S -> 4, 2, 1
current = NULL

Step 4 pops from S
a) Pop 4: Stack S -> 2, 1
b) print "4"
c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything.

Step 4 pops again.
a) Pop 2: Stack S -> 1
b) print "2"
c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
Stack S -> 5, 1
current = NULL

Step 4 pops from S
a) Pop 5: Stack S -> 1
b) print "5"
c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
a) Pop 1: Stack S -> NULL
b) print "1"
c) current -> 3 /*right of 5 */

Step 3 pushes 3 to stack and makes current NULL
Stack S -> 3
current = NULL

Step 4 pops from S
a) Pop 3: Stack S -> NULL
b) print "3"
c) current = NULL /*right of 3 */

Traversal is done now as stack S is empty and current is NULL.
Quelle: https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
Wobei mir dort gerade eben aufgefallen ist das der java code sogar dort stehen würde :D
Dann hätte ich meinen Vorgänger Knoten. Mein Gedanken Problem ist wenn ich doch Rekursive durchlaufe und in meinem Baum ganz Links angekommen bin (der letzte Knoten von Links), dann hätte ich ja das Problem wie bekomme ich den Value (Inhalt) dieses Knotens weiter gereicht. Das meinte ich Gestern mit dem Verwirrenden Code.

Ich sollte echt aufhören hier zu Posten wenn man den ganzen Tag vor solchen Aufgaben sitzt (dann bin ich reichlich verwirrt irgendwann :D).

Werde den TreeBag noch komplett aus programmieren :)

Wäre super Lieb wenn ihr mir noch erklären könntet was @Meniskusschaden sein if dort oben macht das verstehe ich nicht wirklich :(

Danke nochmals für eure netten Kommentare :)

Dann wäre die Lösung gar nicht so kompliziert wie ich es mir vorgestellt hatte mhhh... :)
 
So hier mal mein Baum.
Das von @Meniskusschaden läuft wieso keine Ahnung!

Ich muss mir das ganze Theoretisch auch erst wieder richtig anschauen bevor ist dort weiter mit den Aufgaben mache denn da ist nochmal einiges unklar :(

Bäumchen:
Java:
public class TreeBagg<X extends Comparable<X>> {

    private class Node {
        X value;
        Node left, right;

        Node() {

        }

        Node(X x) {
            value = x;
        }

        Node(X x, Node l, Node r) {
            value = x;
            left = l;
            right = r;
        }
       
    public String toString() {
            return value.toString();
        }
    }

    private Node root;

      public boolean isSet() {
            return isSet(root, null);
        }
       
        private boolean isSet(Node currentNode, X stillSuspicious) {
            if (currentNode==null) {
                return true;
            } else if (currentNode.value.equals(stillSuspicious)) {
                return false;
            } else if (!isSet(currentNode.right, stillSuspicious)) {
                return false;
            } else {
                return isSet(currentNode.left, currentNode.value);
            }
        }
   
    public boolean isEmpty() {
        return root == null;
    }
   
    public boolean insert(X element) {
        if (isEmpty()) {
            root = new Node(element);
            return true;
        } else
            insert(element, root);
        return true;
    }

    private Node insert(X element, Node node) {
        if (node == null)
            node = new Node(element);
        else {
            //Duplikate werden links einfuegt
            if (element.compareTo(node.value) <= 0)
                node.left = insert(element, node.left);
            else
                node.right = insert(element, node.right);
        }
        return node;
    }
   
    public void postorder() {
        postorder(root);
    }

    private void postorder(Node n) {
        if (n != null) {
            postorder(n.left);
            postorder(n.right);
            System.out.print(n+" ");
        }
    }
   
     
}

Main:
Java:
public class TreeBaggMain {
    
    public static void main(String[] args) {
          
        TreeBagg<Integer> tb = new TreeBagg<>();
        
        tb.insert(3);
        tb.insert(2);
        tb.insert(2);
        tb.insert(2);
        tb.insert(44);
        tb.insert(1);
        tb.inorder();
        System.out.println();
        
        System.out.println(tb.isSet());
    }

}
Output:
1 2 2 2 3 44
false
 
Ich weiß leider nicht was ein Visitor ist
Ein Besucher :) Man stelle sich plastisch vor, dass ein Besucher jeden Knoten des Baums "besucht". Im Code sieht das so aus, dass für jeden Knoten die Methode eines übergebenen Objekts (dem Besucher) aufgerufen wird, wobei der jeweilige Knoten als Parameter mitgegeben wird.

Was den Code von @Meniskusschaden betrifft: stillSuspicious ist der Wert des Knotens, in dessen linken Teilbaum Du Dich befindest (oder eben null, wenn Du Dich noch in keinem linken Teilbaum befindest). Hintergrund ist, dass Duplikate eines Werts nur im linken Teilbaum existieren können (im rechten Teilbaum sind alle Werte strikt größer).
 
Danke nochmals :) jetzt habe ich es soweit verstanden doch auf solch eine Lösung wäre ich nicht gekommen.
Wobei das hier ja noch einfacher ist als das was ich vor hatte :)

Liebe Grüße
 
LOL, da sieht man's wieder: das Netz vergisst nichts, selbst wenn man eine Sekunde nach dem Post seinen Unfug wieder entfernt :)
:DWar eben die letzte Gelegenheit, meinen Ansatz doch noch irgendwie rein zu schmuggeln. An sich ist die Visitor-Variante ja schon der professionellere Weg - nur vielleicht nicht ganz anfängergemäß.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben