Hallo ich hab noch ne Frage zu Bäumen, hab davon leider echt nicht viel Ahnung. Jedenfalls hab ich noch ne Aufgabe in der es darum geht zu prüfen ob das Level eines B-Baums korrekt ist. Hier hab ich mal den Code Schnipsel

Code :

1 2 3 4 5 6 7 8 9 10

// Gibt die Höhe des Baums zurück, wenn sich alle Blätter     // auf demselben Niveau befinden, ansonsten -1.     // Das Kriterium eines B-Baums, dass alle Blätter     // denselben Abstand zur Wurzel haben sollen ist also     // erfüllt, wenn ein Wert >= 0 zurückgegeben wird.       public static int levelsOK(BNode node)     {             }

Natürlich soll die methode wieder rekursiv aufgerufen werden. Ich weiss diesmal aber leider gar nicht wo ich anfangen soll. Bin für Tipps wie immer sehr dankbar.

Ich würde es etwa so versuchen:

Code java:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

//Tiefe des ersten Knotens muss 1 sein public static int getTreeDepth(BNode node, int actualDepth) {     if(node.getLeft() == null && node.getRight() == null) //Blatt gefunden, gib' Länge des Zweiges zurück     {         return actualDepth;     }     else     {         int leftDepth = (node.getLeft() != null) ? getTreeDepth(node.getLeft(), actualDepth + 1) : actualDepth;         int rightDepth = (node.getRight() != null) ? getTreeDepth(node.getRight(), actualDepth + 1) : actualDepth;         return (rightDepth > leftDepth) ? rightDepth : leftDepth;     } }

Das sieht eigentlich ganz gut aus, aber ich darf bei der Methode keinen weiteren Paramater mehr einfügen. Das is ja bei mir das Problem weshalb ich da auf keine Lösung komme.

Doch es geht. Ich poste die Lösung mach so, dass sie nicht direkt lesbar ist. Mit makieren des Quelltexts kannst du sie dir dann ansehen.

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public static int levelsOK(BNode node) {     BNode left = node.getLeft();     BNode right = node.getRight();     if(left == null && right == null) {         return 1;     }     if(left == null && right != null) {         return -1     }     if(left != null && right == null) {         return -1;     }         int depthL = levelsOK(left) + 1;     int depthR = levelsOK(right) + 1;         return depthL == depthR ? depthL : -1; }

Ich hab jetzt keine Code parat, aber eine Frage. Redest du von Binären Bäumen oder von B-Bäumen? Denn die beiden bisher geposteten Codes beziehen sich auf Binäre Bäume, aber der Titel sagt "B-Baum".

http://de.wikipedia.org/wiki/B-Baum <> http://de.wikipedia.org/wiki/Bin%C3%A4rbaum

Ich meine tatsächlich B-Bäume.

@ technoblade, ich werde mir den Code heute morgen mal angucken. Hoffentlich komm ich damit weite

Ohh, das mit dem BBaum war mir nicht bewusst, dachte das B stünde für binär.
Aber der Algorithmus lässt sich ja leicht auf Bäume mit jeweils n-Kindknoten übertragen.
Ich gehe mal davon aus, dass über BNode immer ein Array mit der Liste der Kindknoten. Wie ich in Wikipedia gelesen habe ist die Länge dieser Array durch das Level bestimmt. Daher gehe ich davon aus, dass das Array
immer die angepasste Größe hast, also in dem Fall, dass der Baum nicht ausgeglichen ist die Felder mit null gefüllt werden. Sollte also der Baum nach unten hin zuende sein sind alle Felder auf null gesetzt. Abhängig von einer ggf. etwas anderen Implementierung der BNode-Klasse muss der Algorithmus natürlich angepasst werden.

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public static int levelsOK(BNode node) {     BNode[] childs = node.getChilds();     boolean nul = childs[0] == null;     for(int i = 1; i < childs.length; i++) {         if((childs[i] == null) != nul) {             return -1;         }     }     if(nul) {         return 1;     }       int depth = levelsOK(childs[0]);     for(int i = 1; i < childs.length; i++) {         int tmp = levelsOK(childs[i]);         if(tmp != depth) {             return -1;         }     }         return depth; }

Warum machst du den Code denn bitte unsichtbar? was soll das bringen?

ich komm trotzdem nicht weiter. ich kann euch ja hier mal die kompletten klassen zeigen

1. Klasse BNode:

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

public class BNode {     // Ordnung des B-Baums     public static final int order = 2;         // Nächstkleinerer Schlüssel im Elternknoten     // (zum Prüfen auf korrekte Sortiereigenschaft).     // Gibt es den nicht, ist dieser Wert mit dem kleinsten     // int-Wert zu belegen.     // Vereinfacht u.a. die Methode 'getChild'.     protected int leftmostKey;         // Feld für die Kinder / Nachfolger der Schlüssel im Knoten.     // Den linken Nachfolger des Schlüssels keys[i] findet man in     // children[i], den rechten Nachfolger in children[i+1];     // dieser ist gleichzeitig der linke Nachfolger von keys[i+1].     protected BNode children[] = new BNode[order*2+1];         // Feld für die im Knoten zu speichernden Schlüssel.     // Der erste Schlüssel wird an Position 0 gespeichert.     // Das Element hinter dem letzten Nutzschlüssel im     // Feld ist reserviert zum Eintragen des rechten Nachfolgers     // des letzten Nutzschlüssels über 'addNode'. Der dort mit-     // gegebene 'Dummy-Schlüssel' ist mit dem größten int-Wert zu belegen.     protected int keys[] = new int[order*2+1];         // Anzahl der im Knoten gespeicherten Schlüssel inklusive des     // ggf. gespeicherten 'Dummy-Schlüssels' am Ende von keys[].     // Gleichzeitig Anzahl der Nachfolger des B-Baum-Knotens.     protected int cKeys;         public BNode(int leftmostKey)     {         this.leftmostKey = leftmostKey;     }         // Gibt die Anzahl der Nachfolger des B-Baum-Knotens zurück.     public int getChildCount()     {         return cKeys;     }         // Gibt den Schlüssel an Position 'no' im Attribut right von Child     // zurück sowie den nächstkleineren Schlüssel im Attribut left.     // Gibt es keinen nächstkleineren Schlüssel, wird leftmostKey zurückgegeben.     // Zusätzlich zu den Schlüsselwerten wird der linke Nachfolger des     // Schlüssels an Position 'no' zurückgegeben.     // Die Methode kann zum Baumdurchlauf verwendet werden.     public Child getChild(int no)     {         if (no >= cKeys)             return null;                     Child c = new Child();         c.left = (no==0) ? leftmostKey : keys[no-1];         c.right = keys[no];         c.leftChild = children[no];                 return c;     }         // Fügt einen neuen Schlüssel zusammen mit dessen     // linkem Nachfolger (Kind) ein.     public void addNode(BNode leftChild, int newKey)     {         if (cKeys<=order*2)         {             children[cKeys] = leftChild;             this.keys[cKeys++] = newKey;                }     } }

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

2. Klasse Child   public class Child {     // In Bezug auf den aktuell betrachteten Schlüssel     // in einem B-Baumknoten wird hier der nächstkeinere Schlüssel     // gespeichert.     public int left;         // Schlüsselwert des aktuell betrachteten Schlüssels     // in einem B-Baumknoten.     public int right;         // Linker Nachfolger des aktuell betrachteten Schlüssels     // in einem B-Baumknoten.     public BNode leftChild; }

und 3 3.Klasse BTrees

Code :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135

public class BTrees {     // Konstanten für 'Dummy-Schlüssel'     private static final int minInt = Integer.MIN_VALUE;     private static final int maxInt = Integer.MAX_VALUE;;         // Durchläuft den B-Baum in Inorder-Reihenfolge, gibt also     // bei bzgl. der Sortierung korrekt aufgebautem B-Baum die     // gespeicherten Schlüssel in aufsteigend sortierter Reihenfolge aus.     // Diese Methodenimplementierung soll Ihnen als Beispiel dienen.     public static void traverseInOrder(BNode node)     {         if (node != null)             for (int i = 0; i < node.getChildCount(); i++)             {                 Child c = node.getChild(i);                 traverseInOrder(c.leftChild);                 if (i < 4)                     System.out.print(c.right+" ");             }     }         // Gibt die Höhe des Baums zurück, wenn sich alle Blätter     // auf demselben Niveau befinden, ansonsten -1.     // Das Kriterium eines B-Baums, dass alle Blätter     // denselben Abstand zur Wurzel haben sollen ist also     // erfüllt, wenn ein Wert >= 0 zurückgegeben wird.     public static int levelsOK(BNode node)     {         // ToDo     }         // Prüft, ob der B-Baum den Sortierkriterien genügt, d.h., ob     // die folgenden zwei Kriterien erfüllt sind     // 1) Die Schlüssel innerhalb eines Knotens sind aufsteigend sortiert.     // 2) Für jeden Schlüssel s innerhalb eines Knotens gilt, dass     //    alle Schlüssel im Teilbaum seines linken Nachfolgers kleiner     //    sind als s und alle Schlüssel im Teilbaum seines rechten     //    Nachfolgers größer sind als s.     // ACHTUNG: Zur Realisierung dürfen Sie die Methode 'traverseInOrder'     //          NICHT verwenden!     public static boolean isSorted(BNode node, int left, int right)     {         // ToDo     }         public static void main(String[] args)     {         BNode trees[] = new BNode[4];                 // Baum 0 aufbauen         // Anlegen der Blätter         BNode tmp01 = new BNode(minInt);         tmp01.addNode(null, 1);         tmp01.addNode(null, 3);         BNode tmp02 = new BNode(4);         tmp02.addNode(null, 5);         BNode tmp03 = new BNode(9);         tmp03.addNode(null, 11);         tmp03.addNode(null, 12);         BNode tmp04 = new BNode(13);         tmp04.addNode(null, 14);         tmp04.addNode(null, 15);         tmp04.addNode(null, 16);         BNode tmp05 = new BNode(17);         tmp05.addNode(null, 20);         tmp05.addNode(null, 22);         tmp05.addNode(null, 30);         tmp05.addNode(null, 59);                 // Wurzel erzeugen und Schlüssel mit Nachfolgern         // hinzufügen         trees[0] = new BNode(minInt);         trees[0].addNode(tmp01, 4);         trees[0].addNode(tmp02, 9);         trees[0].addNode(tmp03, 13);         trees[0].addNode(tmp04, 17);         // addNode(tmp05, maxInt) speichert den rechten Nachfolger         // des letzten Nutzschlüssels 17. Da für addNode immer auch         // ein Schlüsselwert übergeben werden muss, wird hier der         // 'Dummy-Schlüssel' maxInt übergeben.         trees[0].addNode(tmp05, maxInt);                 // Baum 1 (s.o.)         BNode tmp11 = new BNode(minInt);         tmp11.addNode(null, 1);         tmp11.addNode(null, 3);         tmp11.addNode(null, 7);         BNode tmp12 = new BNode(9);         tmp12.addNode(null, 11);         tmp12.addNode(null, 12);         tmp12.addNode(null, 14);         BNode tmp13 = new BNode(minInt);         tmp13.addNode(tmp11, 9);         tmp13.addNode(tmp12, 15);         BNode tmp14 = new BNode(25);         tmp14.addNode(null, 30);         trees[1] = new BNode(minInt);         trees[1].addNode(tmp13, 25);         trees[1].addNode(tmp14, maxInt);                 // Baum 2         BNode tmp21 = new BNode(minInt);         tmp21.addNode(null, 1);         tmp21.addNode(null, 3);         tmp21.addNode(null, 5);         BNode tmp22 = new BNode(4);         tmp22.addNode(null, 5);         tmp22.addNode(null, 8);         BNode tmp23 = new BNode(9);         tmp23.addNode(null, 11);         tmp23.addNode(null, 12);         BNode tmp24 = new BNode(13);         tmp24.addNode(null, 14);         tmp24.addNode(null, 16);         trees[2] = new BNode(minInt);         trees[2].addNode(tmp21, 4);         trees[2].addNode(tmp22, 9);         trees[2].addNode(tmp23, 13);         trees[2].addNode(tmp24, maxInt);                 // trees[3] ist ein leerer B-Baum                 // Beispiel         System.out.println("Beispielausgabe Traversierung:");         traverseInOrder(trees[0]);         System.out.println("\n");                 // Tests         System.out.println("Baum Nr.\tAlle Blätter auf einem Niveau?\tSortierung ok?");         for (int i = 0; i < trees.length; i++)             System.out.println(i + "\t\t\t\t\t" + (levelsOK(trees[i])==-1 ? "nein" : "ja  ") +                                    "\t\t\t\t\t" + (isSorted(trees[i], minInt, maxInt) ? "ja" : "nein"));     } }

wie ihr sehen könnt muss ich da sogar 2 Aufgaben lösen aber ich bekomme nich mal die mit dem Level hin

Hmm, hast recht genodeftest, könnte den Quelltext eig. auch sichtbar, posten war nur so gedacht, weil es ja eig. seine Aufgabe ist.

Also mal zu der Idee des Algorithmus:
Zuerst wird überprüft, auch die passende Anzahl an Kindknoten zu dem aktuellen Knoten vorhanden ist, sollte einer fehlen wird sofort -1 zurückgegeben.
Sollte es keine Kindknoten geben gibt man 1 zurück, da der aktuelle Knoten dann ja das Ende des Baums ist, es wird also nur diese eine Ebene als Tiefe gezählt.

Sollte die passende Anzahl an Kindknoten vorhanden sein, wird die Methode mit jedem der Kindknoten nochmals aufgerufen. liefern alle den selben Wert zurück (gehen also alle gleich weit tiefer), wird diese Tiefe +1, für das Level selber, zurückgegeben.

Konkret für diese implementierung kann ich den Algorithmus nicht liefern, da ich mich dafür erst da reindenken muss.

macht ja nix aber danke für den Tip, ich werd mal was versuchen

Hallo zusammen,

kann mir vlt jemand zu dieser methode

public static int levelsOK(BNode node)
{

}

einen tipp geben? danke euch schonmal!!

brauche dringend hilfe bitte um rückmeldung....

@canimsin:
Bevor du nachfragst, lies doch erstmal den Rest des Themas. Es geht hier bereits die ganze Zeit um genau diese Methode!

@starbug&canimsin:
Es scheint mir, dass ihr den selben Prof habt, oder zumindest Profs mit den selben Aufgabe.
Wie wäre es wenn ihr euch mal gemeinsam an die Aufgabe setzt.

Ich hab da nichts gefunden zu dieser methode leider oder ich befinde mich grad im faleschem forum

Ich würde mich wirklich freuen wenn mir da jemand einen kurzen ansatz geben könnte******

p.s. ich weiss nicht ob Starbug den selben Prof hat wie ich oder nicht dazu kann ich mich selcht äussern da ich hier ganz neu bin nur durch zufall diese eine methode gesehen die ich brauch******