Baum

[HBOX]

Hallo zusamen,

das ist mein erster Beitrag in einem Deutschen Java Forum. Ich komme aus Portugal und studiere an einer Uni. Deutsch habe ich in der Schule gelernt, also verzeiht meine Rechtschreibfehler.

Ich muss ein Program in Java schreiben das folgendes macht:

1º es wird eine zahlenkette gelesen, und dann muss daraus ein Baum entstehen.

2º Alle Blätter und Knoten die vertikal übereinander stehen müssen addiert werden!

Siehe Bild: z.B. (4+11=15) (10+7=17) (6+9=15)

Ich habe zur Hilfe ein Bild bereit stehen!


Freue mich über jeden Tip und bedanke mich schon mal im Vorraus

mfg

 

[Landei]

Willkommen im Forum!

Wie soll das Einlesen genau stattfinden? Und kann es "Überlappungen" geben (könnte z.B. die 8 ein weiteres Blatt "über" der 11 haben)?

Als Datenstruktur bietet sich natürlich (wer hätte das gedacht?) ein Baum aus Knoten an:

public class Node {
   private int value;
   private Node left = null;
   private Node right = null;
   public Node(int value, Node left, Node right) {
      this.value = value; 
      this.left = left;
      this.right = right; 
   }
   public int getValue() { return value; }
   public Node getLeft() { return left; }
   public Node getRight() { return right; }

   public List<Node> childrenOnVerticalPosition() {
        List<Node> result = new ArrayList<Node>();
        if (left != null) { result.addAll(left.searchPos(-1)); } 
        if (right != null) { result.addAll(right.searchPos(1)); }
        return result;
   }
   private List<Node> searchPos(int pos) {
        List<Node> result = new ArrayList<Node>();
        if (pos == 0) { result.add(this); } 
        if (left != null) {  result.addAll(left.searchPos(pos-1));  } 
        if (right != null) {  result.addAll(right.searchPos(pos+1));  }
        return result;
   }
 
}

childrenOnVerticalPosition sollte von einem Knoten alle Kinder liefern, die sich genau "unter" ihm befinden (egal wieviel Ebenen tief).

 

[Noctarius]

Offtopic:
Du hast Deutsch in der Schule gelernt? Oo Echt jetzt? Na dann mal willkommen im Club der Menschen, die mindenstens einen deutschen Satz fehlerfrei schreiben können. Damit bist du weit über vielen Deutschen angesiedelt

 

[Landei]

Ja, dein Deutsch ist wirklich gut.

 

[HBOX]

Danke für die Hilfe Landei! Also es wird keine überlappungen geben. Mir ist noch nicht klar wie aus einer Zahlenkette ein Baum wird

 

[Landei]

Der einzige Fall den ich kenne, bei der aus einer gegebenen Zahlenkette ohne weitere Angaben ein binärer Baum wird, wäre ein Baum zum Sortieren. Also, wenn man die Zahlen 10 ,3 ,4 ,7, 12, 2 "hineinwirft", kommt...

       10
      /  \
     3   12
    / \
   2   4
         \
          7

...heraus.

 

[HBOX]

Wie kann ich dann den "Baum zum Sortieren" mit dem oben genannten Cod verbinden?

 

[Landei]

class Node {
   private int value;
   private Node left = null;
   private Node right = null;

   public Node(int value) {
      this.value = value; 
   }

   ...  //andere Methoden wie oben
 
   public void insert(int newValue) {
      if (newValue < value) {
         if (left == null) {
            left = new Node(newValue); 
         } else {
            left.insert(newValue);
         }
      } else if (newValue > value) {
         if (right == null) {
            right = new Node(newValue); 
         } else {
            right.insert(newValue);
         }
      }       
   }
}

int[] values = new int[]{10 ,3 ,4 ,7, 12, 2};
Node root = new Node(values[0]);
for(int v : values) {
   root.insert(v);
}

 

[MQue]

Der einzige Fall den ich kenne, bei der aus einer gegebenen Zahlenkette ohne weitere Angaben ein binärer Baum wird, wäre ein Baum zum Sortieren. Also, wenn man die Zahlen 10 ,3 ,4 ,7, 12, 2 "hineinwirft", kommt...

       10
      /  \
     3   12
    / \
   2   4
         \
          7

...heraus.

Mal ne blöde Frage, wenn ich die Wurzel so wähle, dass diese ganz am Rand ist (angenommen es handelt sich um das ABC) und die Wurzel ist Z, dann sind ja bei einem binären Baum alle einträge links davon, d.h. es gibt rechts von der Wurzel keine Zweige, was macht man da dagegen, damit das nicht passiert:

Wenn ich habe:

BinaerBaum bb = new BinaerBaum();
bb.insert("Z");     // wenns so anfängt, hab ich ein Problem, oder?
bb.insert("A");
bb.insert("F");

[CODE]

 

[eRaaaa]

naja neusortieren nehme ich an
also halt so ordnen, dass dann F die wurzel ist. dann passts ja wieder. A linkerteilbaum, Z rechter teilbaum.

 

[MQue]

naja neusortieren nehme ich an
also halt so ordnen, dass dann F die wurzel ist. dann passts ja wieder. A linkerteilbaum, Z rechter teilbaum.

Das dauert aber ziemlich, den ganzen Baum neu aufzubauen, das kann ja nicht Sinn der Übung sein, wenn ich in der falschen Reihenfolge hinzufüge, dass es dann um einiges länger dauert -> alle Knoten auslesen -> nach der Mitte suchen, Baum neu aufbauen.
lg

 

[Landei]

Es gibt Algorithmen zum nachträglichen Ausbalancieren von Bäumen, und spezielle "Baumarten" (wie Rot-Schwarz-Bäume), die dafür sorgen, dass der Baum schon beim Einfügen immer balanciert bleibt.