[Java] String representatie van een binary tree

[dtech]

Hallo,

ik probeer in java een binary tree te maken. Nu lukt dit op zich best aardig met twee klassen (node en tree, waarbij tree meer een wrapper is), maar ik zit een beetje in m'n maag met de toString.

Het liefste zou ik zo'n soort plaatje willen genereren:

code:

                    |root|
         |node|            |node|
    |node|    |node|          |node|
                                 |node|

Nou is dit natuurlijk heel erg lastig, maar zoiets zou ook al mooi zijn:

code:

|root|
|node|    |node|
|node|    |node|              |node|
                                                                      |node|

Maar ik heb geen idee hoe ik dat het beste kan aanpakken.
Het enige wat ik kon bedenken dat echt een redelijk resultaat was is alles op te slaan in een 2D-array (lees: heel inefficiënt)
Ook level-order geeft niet echt het gewenste resultaat, al dan niet met verschillende manieren die ik heb geprobeerd om newlines te genereren.

Iemand een idee?

[asfaloth_arwen]

Recursief printen/boom doorlopen? Misschien dat je met http://cslibrary.stanford.edu/110/BinaryTrees.html een stuk in de richting komt (5. printTree() en 6.printPostorder) Geen implementatie, maar wel een hint hoe je het kan aanpakken.

Mocht je er niet uitkomen zoek in nog even in het boek algorithms in Java wat ik hier heb staan, weet dat het daar in staat

[ Voor 21% gewijzigd door asfaloth_arwen op 07-03-2009 21:12 ]

[user109731]

Ik zou het idd met een Postorder traversal proberen. Daarmee 'bezoek' je elke node nadat je z'n child-nodes hebt gehad. Hierbij geef je dan telkens de breedte van de onderliggende boom door. In de parent weet je dan hoe breed beide bomen samen zijn en met die info kun je die node zelf tekenen, etc. Om de parent netjes te centreren moet je immers weten hoe breed de onderliggende bomen zijn.

Wellicht handig om een string-array te gebruiken (een string per level), zodat je daar telkens aan kunt toevoegen... Lastigste is als de rechterboom hoger is dan de linkerboom, zoals in jouw voorbeeld. In dat geval moet je de strings voor de laatste rijen eerst padden zodat je goed uitkomt.

[ Voor 28% gewijzigd door user109731 op 07-03-2009 23:32 ]

[_Erikje_]

Probleem komt me bekend voor (als in been there, done that).
Een veelgebruikte oplossing is om de nodes en edges apart op de slaan in twee lijsten. Nodes hebben direct geen relatie met andere nodes, de relatie is in de lijst met edges gedefinieerd. De nodes zitten ook in een lijst.

Om het mooi weer te kunnen geven moet je 2 dingen weten.
a hoeveel ranks zijn (hoeveel niveaus in de boom)
b welke rank heeft de meeste nodes (rank[i].size())

Dus eerst alle ranks berekenen.
Dan weet je gelijk a en is b heel gemakkelijk te berekenen...
De rest is door jou in te vullen....

[KopjeThee]

Zoiets?

[Soultaker]

Stel dat je een volledige gebalanceerde binaire boom hebt, dan kun je de nodes vrij simpel identificeren aan de hand van de rij en kolom waarin ze voorkomen:

code:

         (1,1)
   (2,1)       (2,2)
(3,1) (3,2) (3,3) (3,4)

De eerste rij bevat dus 1 node, de tweede 2, de derde 4, en zo steeds verdubbelen. Ervan uitgaande dat je een node kan vinden aan de hand van zijn rij en kolom, kun je makkelijk de gewenste uitvoer genereren, uitgaande van een vaste regelbreedte W:

Java:

for (int row = 1; row <= height; ++row)
{
    int width = W/(1<<(row-1));
    String line = "";
    for (int col = 1; col <= row; ++col)
    {
        // Get string for this node
        Node node = getNode(root, row, col)
        String s = node == null ? "" : node.toString();

        // Pad to width
        while (s.length() + 2 <= width) s = " " + s + " ";
        if (s.length() < width) s = s + " ";

        // Add to line
        line += s;
    }
    System.out.println(line);
}

Dan vraag twee: hoe vind je een node aan de hand van zijn locatie? Gebruik een functie getNode(root,row,col) die de node op rij row en kolom col ten opzichte van de root node root vindt. We kunnen daarbij gebruik maken van de wetenschap dat rij N uit 2^N-1 nodes bestaat, dus weten we altijd of een gezochte kolom zich in de linker of rechter subtree van de root node bevindt:

Java:

Node getNode(Node node, int row, col)
{
    if (node == null) {
        return null;
    } else if (row == 1) {
        return node;  // col must be 1 too
    } else if (col <= (1<<(row-2)) {
        return getNode(node.left, row + 1, col);
    } else {
        return getNode(node.right, row + 1, col - (1<<(row-2)));
    }
}

Merk op dat ik een controle op node == null toegevoegd heb. Het gevolg daarvan is dat deze functie ook goed werkt als de binaire boom niet volledig gebalanceerd is (en er dus bepaalde nodes ontbreken).

In totaal levert dit een O(N log N) oplossing op terwijl O(N) ook mogelijk is, maar aangezien je toch geen supergrote bomen wil printen maakt het in de praktijk weinig uit.

(Disclaimer: code is ongetest, dus kan nog fouten bevatten; was meer als pseudocode bedoeld.)

[ Voor 4% gewijzigd door Soultaker op 08-03-2009 16:01 ]