Binärbaum

[Manfred]

Kann mir jemand erklären wie ich den in Java programmiere, bzw. eine gute Seite zur allgemeinen erklärung nennen?

Danke

 

[Beni]

Das hier kennst du?

Tipp: java binary tree tutorial

 

[foobar]

Binärbaum

 

[Casper]

//als erste diese Klasse

class Knoten {
  // Nutzdaten
  private int info ;
  // Verwaltungsdaten
  private Knoten left_ref ;
  private Knoten right_ref ;

  public Knoten (int info) {
    this.info = info ;
    left_ref  = null ;
    right_ref = null ;
  }  // endmethod Knoten

  public int getInfo () {
    return info ;
  }  // endmethod getInfo

  public Knoten getLeft () {
    return left_ref ;
  }  // endmethod getLeft

  public Knoten getRight () {
    return right_ref ;
  }  // endmethod getRight

  public void setLeft (Knoten left_ref) {
    this.left_ref = left_ref ;
  }  // endmethod setLeft

  public void setRight (Knoten right_ref) {
    this.right_ref = right_ref ;
  }  // endmethod setRight

  public void printInfo () {
    System.out.print ("Nutzdaten des Knoten: ");
    System.out.println (info) ;
  }  // endmethod printInfo
}  // endclass Knoten

//danach den Binärbaum

class Suchbaum {
  private Knoten wurzel_ref ;

  public Suchbaum () {
    wurzel_ref = null ;
  }  // endmethod Suchbaum

  private void add (Knoten knoten_ref, Knoten neu_ref) {
    if (neu_ref.getInfo () <= knoten_ref.getInfo ()) {
      // weiter im linken Teilbaum
      if (knoten_ref.getLeft () == null) {
        knoten_ref.setLeft (neu_ref) ;
      } else {
        add (knoten_ref.getLeft (), neu_ref) ;
      }
    } else {
      // weiter im rechten Teilbaum
      if (knoten_ref.getRight () == null) {
        knoten_ref.setRight (neu_ref) ;
      } else {
        add (knoten_ref.getRight (), neu_ref) ;
      }
    }  // endif
  }  // endmethod add

  public void addKnoten (int info) {
    Knoten neu_ref = new Knoten (info) ;
    if (wurzel_ref == null) {
      wurzel_ref = neu_ref ;
    } else {
      add (wurzel_ref, neu_ref) ;
    } // endif
  }  // endmethod addKnoten

  public void inorderTraverse () {
    inorder (wurzel_ref) ;
  }  // endmethod inorderTraverse

  private void inorder (Knoten knoten_ref) {
    if (knoten_ref != null) {
      // Reihenfolge: linker Teilbaum - Knoten - rechter Teilbaum
      inorder (knoten_ref.getLeft ()) ;
      knoten_ref.printInfo () ;
      inorder (knoten_ref.getRight ()) ;
    }  // endif
  }  // endmethod inorder

  public void preorderTraverse () {
    preorder (wurzel_ref) ;
  }  // endmethod preorderTraverse

  private void preorder (Knoten knoten_ref) {
    if (knoten_ref != null) {
      // Reihenfolge: Knoten - linker Teilbaum - rechter Teilbaum
      knoten_ref.printInfo () ;
      preorder (knoten_ref.getLeft ()) ;
      preorder (knoten_ref.getRight ()) ;
    }  // endif
  }  // endmethod preorder

  public void postorderTraverse () {
    postorder (wurzel_ref) ;
  }  // endmethod postorderTraverse

  private void postorder (Knoten knoten_ref) {
    if (knoten_ref != null) {
      // Reihenfolge: linker Teilbaum - rechter Teilbaum - Knoten
      postorder (knoten_ref.getLeft ()) ;
      postorder (knoten_ref.getRight ()) ;
      knoten_ref.printInfo () ;
    }  // endif
  }  // endmethod postorder
}  // endclass Suchbaum

//und eine Testklasse

class SuchbaumTest {
  public static void main (String [ ]  args) {
    int [ ] feld_ref = {5, 10, 2, -1, 0, 4, 3, 5, 7, 7, 9, 8, -4, 12} ;
    Suchbaum baum_ref = new Suchbaum () ;

    // Suchbaum erstellen
    for (int i = 0; i < feld_ref.length; i++) {
      baum_ref.addKnoten (feld_ref [i]) ;
    }
    // Suchbaum traversieren
    System.out.println ("Baum nach preorder traversiert:") ;
    baum_ref.preorderTraverse () ;
    System.out.println ("----------------------------------") ;
    System.out.println ("Baum nach inorder traversiert:") ;
    baum_ref.inorderTraverse () ;
    System.out.println ("----------------------------------") ;
    System.out.println ("Baum nach postorder traversiert:") ;
    baum_ref.postorderTraverse () ;
    System.out.println ("----------------------------------") ;
  }  // endmethod main
}  // endclass

Bitteschön, vielleicht hilft dir das ja...hoffe du verstehst den Code, ansonsten frag mich!!

Gruß Casper[/code]

 

[T-Bone]

Hey
die letzte Meldung zu dem Thema ist zwar schon etwas her, allerdings war dies der Thread der noch am meisten zu meinem Problem passen würde.
Und es wir einem ja geraten nicht einfach neue Meldungen zu starten, wenn es zu dem Thema schon was gibt

Wie gesagt, mein Problem ist eine Methode für einen Binärbaum. int[] z() kriege ich nicht zum Laufen,
Ich habe bereits eine Methode geschrieben, die den Baum nach Blättern absucht und diese zählt! Nur die Methode, die diese Blätter nacheinander IN-ORDER in ein Array packen soll will nicht funktionieren :-(!
Vielleicht habt ihr ne Idee.

[ Wusste jetzt nicht ob ich den ganzen code posten soll. Müsst euch ja nicht alles durchlesen ;-) ]

class Baum{
    Knoten Wurzel;
    Baum(int Zahl){
        Wurzel=new Knoten(Zahl);
    }

// ANZAHL der Blätter
    int b(){
        if (Wurzel==null)return 0;
        else return b(Wurzel);
    }
    int b(Knoten k){
        if(k.links==null && k.rechts==null){
            return 1;
        }
        else if(k.links!=null && k.rechts==null){
            return b(k.links);
        }
        else if(k.links==null && k.rechts!=null){
            return b(k.rechts);
        }
        else{
            int links, rechts;
            links=b(k.links);
            rechts=b(k.rechts);
            return links+rechts;
        }
    }

// ARRAY, das Zahlen der Blätter enthält    <<<--------------------- PROBLEM-!!!------------------
    int[] z(){
        return z(Wurzel);
    }
    int[] z(Knoten k){
        int[] temp=new int[b()];
        if(k==null) return null;
        else{
            if(k.links==null && k.rechts==null){
                temp[temp.length]=k.Zahl;
            }
            else if(k.links!=null&&k.rechts==null){
                return z(k.links);
            }
            else if(k.rechts!=null&&k.links==null){
                return z(k.rechts);
            }
            else{
                z(k.links);
                z(k.rechts);
            }
            return temp;
        }
    }

// EINFÜGEN
    void einfuegen(int Zahl){
        Wurzel=einfuegen(Zahl, Wurzel);
    }
    Knoten einfuegen(int Zahl, Knoten k){
        Knoten temp;
        if(k==null) temp=new Knoten(Zahl);
        else{
            if(Zahl<k.Zahl)k.links=einfuegen(Zahl, k.links);
            else k.rechts=einfuegen(Zahl, k.rechts);
            temp=k;
        }
        return temp;
    }

// AUSGABE
    void print(){
        System.out.println("Baum:  -<print>-");
        print(Wurzel, 0);
    }
    void print(Knoten k, int einruecken){
        if(k!=null){
            print(k.links, einruecken + 2);
            for(int i=1; i<=einruecken; i++) System.out.print(" ");
            System.out.println(k.Zahl);
            print(k.rechts, einruecken+2);
        }
    }
}

class Knoten{
    int Zahl; 
    Knoten links, rechts;
    Knoten(int Zahl){
        this.Zahl=Zahl;
    }
}

public class Hauptprogramm{
    public static void main(String[]args){
        Baum testbaum=new Baum(20);
        testbaum.einfuegen(15);
        testbaum.einfuegen(12);
        testbaum.einfuegen(14);
        testbaum.einfuegen(23);
        testbaum.einfuegen(21);
        testbaum.einfuegen(30);
        testbaum.einfuegen(3);
        testbaum.einfuegen(1);
        testbaum.einfuegen(4);
        testbaum.print();
        System.out.println("Baum hat " + testbaum.b() + " Blätter!\n");
        int[] z=testbaum.z();
        for(int i=0; i<z.length; i++){
            System.out.println("Stelle " + i + ": " + z[i]);
        }
    }
}

Über Tips würde ich mich sehr freuen
Wo ich auch noch dran sitze sind:
- Höhe eines Baumes

Gruss Timo

 

[Illuvatar]

Nur eine Anmerkung: Laut Suns Coding Conventions sollte man Variablen immer klein schreiben :!: