blattorientierter binärer Suchbaum

[ToniKukoc]

Hallo

wir müssen den Aufbau eines blattorientierten binären Suchbaums implementieren,also quasi eines B-Baums,jedoch darf hier in einem Blatt nur ein Wert gespeichert werden.Die inneren Knoten sind nur Wegweiser,die Blätter unten sind aufsteigend sortiert.
Als Beispiel:3,7,13,15,20,23,29,30

-----------------------15
-------------7 ---------------------23
-------3 ---------13 ---------20----------29
---|3| -|7|--|13|--|15|--|20|-|23|---|29|--|30|



Kann mir da jemand helfen?

 

[Landei]

Das ergibt irgendwie keinen Sinn. Wenn ich für den oben gegebenen Baum die 15 suche, woher weiß ich dann, ob ich links oder rechts gehen soll?

 

[ToniKukoc]

Es ist so definiert dass das linke Kind immer <= ist und das rechte >
Die Suche nach x ist definiert mit v als Knoten
while v = kein Blatt (also letzter Knoten ohne Zeiger auf iwas)
if x <= v.key = v.left
else v = v.right

Ich weiß es ist extrem umständlich und ich finde es in dieser Form auch nirgendwo,deshalb bitte ich hier um Hilfe bei der Implementierung

 

[diggaa1984]

dann musst aber in der 3. zeile noch die 23 durch ne 20 ersetzen .. flüchtigkeitsfehler

die frage die sich aber uns stellen sollte .. wie weit ist dein eigener ansatz, wo hakts, was macht probleme?

 

[ToniKukoc]

Danke habs verbessert

Naja im Grunde ist es ja ein normaler Binärbaum,ich weiß jedoch nicht wie ich dann diese Blätter unten wieder anfügen kann,also wie ich da wieder drauf zugreife.

 

[Landei]

public class BinTree {

    private BinNode root;

    private static class BinNode {
        BinNode left;
        BinNode right;
        int value;
        BinNode(int value) {
            this.value = value;
        }
        public boolean isLeaf() {
            return left == null && right == null;
        }

        public void add(int value) {
            if (value <= this.value && left != null) {
                left.add(value);
            } else if (value > this.value && right != null) {
                right.add(value);
            } else if (value <=  this.value && left == null) {
                left = new BinNode(value);
                left.add(this.value);
            } else if (value > this.value && right == null) {
                right = new BinNode(value);
                if (left == null) {
                    left = new BinNode(this.value);
                }
            }
        }

        public String toString() {
          if (isLeaf())  {
              return " " + value;
          } else {
              return (left != null ? left.toString() : "") +
                     (right != null ? right.toString() : "");
          }
        }

    }

    public void add(int value) {
        if (root == null) {
            root = new BinNode(value);
        } else {
            root.add(value);
        }
    }

    public String toString() {
        return root == null ? "<empty>" : root.toString();
    }

    public static void main(String... args) {
        BinTree tree = new BinTree();
        for(int i : new int[]{15,23,7,13,20,29,3,30}) {
          tree.add(i);
        }
        System.out.println(tree);
    }

}