treewalk

[sh33p]

Ich habe bisher folgende Klassen (siehe unten). Der Baum besitzte die Ordnungseigenschaft:
Alle Zahlen, die in Objekten des linken Teilbaums eines beliebigen Knotens
gespeichert sind, sind echt kleiner als die Zahl, die im Knoten selbst
gespeichert ist, und alle Zahlen im rechten Teilbaum sind echt groesser
als die Zahl des Knotens selbst.

Ich möchte jetzt den Baum sortiert ausgeben.(siehe Methode treewalk). Wie benutze ich in meine Metode die Methode operate zur Ausgabe?

public class BinaryNode {
     private BinaryNode father, leftSon, rightSon;
     private int value;
     
     
      public BinaryNode(int i) {
       father = leftSon = rightSon = null;
       value = i;
     }
     public boolean contains(int v){
     
     if(this.value == v){
       return true;
     }
     else if(this.value > v && this.leftSon !=null){
       return this.leftSon.contains(v);
     }
     else if(this.value < v && this.rightSon !=null){
       return this.rightSon.contains(v);
     }
     return false;
     
     }
     
     public void insert(int v){
      if(this.value < v){
        if(this.rightSon == null){
          BinaryNode n = new BinaryNode(v);
          n.father = this;
          this.rightSon = n;
        }
        else{
          this.rightSon.insert(v);
        }
        }
      else if(this.value > v){
          if(this.leftSon == null){
            BinaryNode s = new BinaryNode(v);
            s.father = this;
            this.leftSon= s;
          }
          else{
            this.leftSon.insert(v);
          }
        }
  }
  

    public void treewalk(NodeOperation f) {

    if(this.value > leftSon.value){
        leftSon.treewalk(f);

    }
     
    if(this.value < rightSon.value){
      rightSon.treewalk(f);
    }
    }
}
interface NodeOperation {
     public void operate(int v);
}
 public class PrintNodeValue implements NodeOperation {
     public void operate(int v) {
       System.out.print(" - " + v);
     }
   }

 

[Beni]

Mit anderen Worten: du möchtest das Visitor-Pattern anwenden. Da musst du deine "treewalk"-Methode leicht anders schreiben. Zum einen müssen immer alle Kinder besucht werden, zum anderen musst du auch "operate" aufrufen. Etwa so:

public void treewalk(NodeOperation f) { 
    // falls es einen linkes Kind gibt: besuchen
    if(leftSon != null){
        leftSon.treewalk(f); 
    }
     
    // alle kleineren Werte wurden besucht...
    f.operate( this.value );
    // ... und jetzt können wir dir restlichen, grösseren Werte besuchen.

   // falls es ein rechtes Kind gibt: besuchen
    if(rightSon != null){
      rightSon.treewalk(f);
    }
}

 

[sh33p]

wir durchlaufen also als 1. den linken teilbaum bis zum ende,wo der kleinste wert steht.
dann gehen wir durch rekursion wieder nach oben und geben mit operate jeden wert des knotens aus.
anschließend machen wir das selbe für den rechten teilbaum.right?

 

[Beni]

Ja, und weil...

Alle Zahlen, die in Objekten des linken Teilbaums eines beliebigen Knotens
gespeichert sind, sind echt kleiner als die Zahl, die im Knoten selbst
gespeichert ist

... sollte das dann aufsteigend sortiert sein.