List to BinaryTree

[ramirez]

Hi,
ich möchte eine Methode implementieren , die eine Liste bekommt und eine BinBaum<T> zurückgibt
ich habe schon eine BinBaum<T> Klasse geschrieben.

1.Frage: wie kann ich eine Liste zu einem Baum konvertieren ?
2.Frage: Wenn ich schon einen Baum gesetzt habe, gebe ich einfach die Referenzvariable auf die BinBaum<T> zurück ?

 

[bERt0r]

Du hast doch sicher eine Funktion add(T dings) oder einfuegen(T dings) in deiner BinBaum Klasse.
Also erstellst du einen neuen Baum, iterierst du die Liste durch, und fügst jedes Element der Reihe nach ein.

BinBaum<T> returnBaum=new Binbaum<T>();
Iterator it=listeVonTs.iterator();
while(it.hasNext())
{T teil=it.next();
returnBaum.add(teil);
}
return returnBaum;

 

[ramirez0]

Ich hab leider keine add-Methode in der BinBaum-Klasse, nur drei Konstruktoren von der Art:
BinBaum<T>()

BinBaum<T>(T t)

BinBaum<T>(BinBaum<T>, T t, BinBaum<T>)

Das heiß ich muss mir den Baum irgendwie aus den Konstruktoren zusammenbauen, nur wie?

 

[Marcinek]

Das geht nicht.

Du benötigst add und remove methoden.

 

[Landei]

Theoretisch geht 1) schon ohne add-Methode in BinBaum selbst, nur dass dann die add-Methode sozusagen "extern" ist, mit Teil-Bäumen herumhantiert und die ganze Logistik selbst übernehmen muss. Es ist auch kein Problem, wenn der Baum unveränderlich ist.

Hübsches OO sieht aber anders aus.

 

[Landei]

Der Beweis:

public class BinBaum<T> {
    
    private final T value;
    private final BinBaum<T> left, right;
    
    public BinBaum() {
        this(null);
    }        
    
    public BinBaum(T value) {
        this(null,value,null);
    }
    
    public BinBaum(BinBaum<T> left, T value, BinBaum<T> right) {
        this.left = left;
        this.value = value;
        this.right = right;
    }

    @Override
    public String toString() {
        String leftStr = left == null ? "" : left.toString();
        String rightStr = right == null ? "" : right.toString();
        return "(" + leftStr + value + rightStr + ")";
    }
    
}

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class BinTest {
    public static void main(String[] args) {
        Random r = new Random();
        List<Integer> intList = new ArrayList<Integer>();
        for(int i = 0; i < 20; i++) {
            intList.add(r.nextInt(100));
        }
        System.out.println(intList);
        System.out.println(makeBin(intList));
    }
    
    public static BinBaum<Integer> makeBin(List<Integer> list) {
        if (list.isEmpty()) {
            return new BinBaum<Integer>();
        } else if (list.size() == 1) {
            return new BinBaum<Integer>(list.get(0));
        } else {
            int pivot = list.get(0);
            List<Integer> left = new ArrayList<Integer>();
            List<Integer> right = new ArrayList<Integer>();
            for(int i = 1; i < list.size(); i++) {
                (list.get(i) <= pivot ? left : right).add(list.get(i));
            }
            return new BinBaum<Integer>(makeBin(left), pivot, makeBin(right));
        }
    }
}

Ausgabe:

[45, 42, 87, 18, 33, 37, 70, 81, 32, 87, 65, 36, 70, 27, 18, 17, 27, 81, 74, 64]
(((((17)18(null))18((((27)27(null))32(null))33((36)37(null))))42(null))45((((64)65(70))70(((74)81(null))81(87)))87(null)))

Um Frage 2) zu beantworten, ja du gibst einfach eine Referenz zurück, genau wie es in meinem Code die Methode makeBin tut.

 

[bERt0r]

Landei, was du hier BinBaum nennst ist kein Baum sondern ein Knoten. Der ganze OO-Sinn hinter einer Klasse die BinBaum heisst ist der, dass sie sich um die Einfüge, Such und Entfernungsmechanismen kümmern soll. Solche "Lösungsvorschläge" sind für Anfänger gefährlich, sowas lernt man sich falsch ein und dann steht man irgendwann vor einer Wand.

 

[Landei]

Du irrst dich, genau so werden unveränderliche Bäume definiert.

Siehe z.B. hier: Immutability in C# Part Six: A Simple Binary Tree - Fabulous Adventures In Coding - Site Home - MSDN Blogs oder hier: Tree Tutorial - Progzoo
Binary Tree, nicht "Binary Node" oder so...

Veränderliche Bäume sehen natürlich anders aus, und ihre Knoten ähneln unveränderlichen Bäumen (nur dass die Knoten eben veränderlich sind). Das ändert aber nichts an der Tatsache...

Dass das kein schönes OO ist, habe ich schon geschrieben. Funktionieren tut es trotzdem. Und wenn der TO schreibt, seine BinBaum-Klasse hat keine add-Methode, muss ich halt davon ausgehen.

 

[Anonym]

Landei, was du hier BinBaum nennst ist kein Baum sondern ein Knoten.

Blödsinn, jeder "Knoten" in einem Baum ist per Definition ein Baum.
Davon abgesehen ist eine add Methode bei einem Binär Baum sowieso fehl am Platze.

 

[bERt0r]

Es ging mir hier gar nicht darum, ob man in c# so unveränderliche Bäume konstruiert, oder jeglichen "Blödsinn" den ihr mir hier unterstellt.
Mir ging es nur darum, dass es gefährlich ist, mit so einer absolut nicht objektorientierten Lösung daherzukommen, bevor der TO nicht genau sowas fordert. Ramirez hat nicht erwähnt dass der Binärbaum unveränderlich sein soll.
Er hat auch gesagt er hat die Klasse selbst geschrieben, also wird die nicht schon vorgegeben sein.
Ich bestreite ja gar nicht dass dein Code funktioniert ist, und du sagst ja auch selber dass es nicht schönes OO ist, meine Aussage bezog sich darauf, dass jemand der Java gerade lernt es eben nicht so, sondern objektorientiert lernen sollte. Eine Binärbaum Bearbeitung wie du sie gezeigt hast, ist mir nur mehr aus Pascal-Zeiten in Erinnerung.

 

[Landei]

Eine Binärbaum Bearbeitung wie du sie gezeigt hast, ist mir nur mehr aus Pascal-Zeiten in Erinnerung.

Das ist schade. Pascal hat einiges richtig gemacht, was C und C++ falsch gemacht haben, wobei es allerdings etwas zu konservativ war. Aber man kann auch in Pascal gute Programme schreiben.

Der Stil meines Beispiels ist nicht imperativ, er ist funktional, und ist ganz normal in Sprachen wie Haskell oder Scala. Dass das in Java nicht "schön" aussieht, ist größtenteils der Fehler von Java, denn in anderen OO-Sprachen mit funktionalen Elementen (C#, Python, Ruby...) könnte man es durchaus "hübsch" machen - und ebenso in Java 8.

OO ist keine heilige Kuh, es löst einige Probleme, und schafft ein paar andere, darunter ziemlich haarige. Der hier gezeigte Stil kann z.B. in einer heterogenen Baumstruktur der "OO-Lösung" (sowohl der normalen Implementierung wie auch dem abscheulichen Visitor Pattern) überlegen sein.

Was man den Anfängern wirklich beibringen sollte ist, dass in der IT jede Art von Dogmatismus fehl am Platz ist - denn wenn sie erst einmal auf die Menschheit losgelassen werden, wird weder OO- noch funktionionale Programmierung noch so wie heute aussehen.

 

[Landei]

Um den Punkt zu verdeutlichen, wie elegant diese Lösung im Kern eigentlich ist, hier exakt der gleiche Code in Haskell, inklusive der drei unterschiedlichen Konstruktoren (die hier aber unterschiedliche Namen bekommen müssen):

data BinBaum a = Branch a (BinBaum a) (BinBaum a) 
                 | Leaf a 
                 | Nil 
                 deriving Show

makeBin [] = Nil
makeBin [x] = Leaf x
makeBin (x:xs) = Branch x left right where
    left = makeBin $ filter (<= x) xs
    right = makeBin $ filter (> x) xs

Auf unsere Beispieldaten angewandt:

Branch 45 (Branch 42 (Branch 18 (Branch 18 (Leaf 17) Nil) (Branch 33 (Branch 32 (Branch 27 (Leaf 27) Nil) Nil) (Branch 37 (Leaf 36) Nil))) Nil) (Branch 87 (Branch 70 (Branch 65 (Leaf 64) (Leaf 70)) (Branch 81 (Branch 81 (Leaf 74) Nil) (Leaf 87))) Nil)

Denkst du, man (und das schließt Anfänger ein) sollte solche Techniken nicht kennen, nur weil sie nicht "OO" genug sind?

 

[Dekker]

...
Denkst du, man (und das schließt Anfänger ein) sollte solche Techniken nicht kennen, nur weil sie nicht "OO" genug sind?

Um das mal vorweg zu nehmen. Der Stil den man da benutzt der ähnelt auch sehr den von funktionalen Programmiersprachen.
Es ist eigentlich egal in welchem Stadium des lernens man ist, im Grunde genommen sollte man alle diese Techniken zumindest mal gesehen haben. Beides hat an bestimmten Stellen seine Vor- und Nachteile.

Wobei ich ehrlich sagen muss, von alleine wäre ich nie auf die Idee gekommen das so zu Implementieren. Man stumpft irgendwie gegen solche Lösungen ab und sucht irgendwie immer erstmal nach einer OO Lösung. Ka wies den anderen hier geht, aber fällt mir an mir immer wieder auf

 

[diggaa1984]

kommt mir ja schwer bekannt vor die aufgabe

man kann das per rekursion lösen wenn man sich daran hält, dass zu einem Listenindex i, dessen Element den Inhalt des Wurzelknotens eines BinBaumes darstellt, das Listenelement 2*i den Wurzelknoten des linken Unterbaumes und das Listenelement (2*i)+1 den Wurzelknoten des rechten Unterbaumes darstellt.

für i >= 1 .. das heisst, da muss man diesen Bereich noch auf die eigentlichen Indizes der Listen (beginnend bei 0) mappen.