postorder iterrativ

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
afroasiate

Mittwoch 30. November 2005, 11:47

Hallo,

ich brauche für die postorder einen iterativen Algorithmus.

Vielleicht kann mir jemand helfen?

Code: Alles auswählen


class node(object):
    """ Klasse für eine einfache Baumstruktur """

    __slots__ = ["left","right","value"]

    def __init__(self, value):
        """ Neuen Knoten des Baumes initialisieren """
        self.left = None
        self.right = None
        self.value = value

    def insert(self, value):
        """ Wert in Baumstruktur einfügen """
        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = node(value)
        else:
            if self.right:
                self.right.insert(value)
            else:
                self.right = node(value)

    def print_tree(self, indent=0):
        """ Baumstruktur darstellen, die Einrückung stellt die Tiefe im Baum dar """
        if self.left:
            self.left.print_tree(indent+1)
        print ("  "*indent)+self.value
        if self.right:
            self.right.print_tree(indent+1)
           
    def inorder(self):
        """ Baum "inorder" als Liste zurückgeben """
        result = [self.value]
        if self.left:
            result = self.left.inorder()+result
        if self.right:
            result = result+self.right.inorder()
        return result

    def preorder(self):
        """ Baum "preorder" als Liste zurückgeben """
        result = [self.value]
        if self.left:
            result = result+self.left.preorder()
        if self.right:
            result = result+self.right.preorder()
        return result

    def postorder(self):
        """ Baum "postorder" als Liste zurückgeben """
        if self.left:
            result = self.left.postorder()
        else:
            result = []
        if self.right:
            result += self.right.postorder()
        result.append(self.value)
        return result


if __name__ == "__main__":
    tree = node("d")
    tree.insert("c")
    tree.insert("f")
    tree.insert("a")
    tree.insert("b")
    tree.insert("e")
    tree.insert("g")
    tree.print_tree()
    print tree.inorder()
    print tree.preorder()
    print tree.postorder()

[/code]
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Mittwoch 30. November 2005, 14:27

Das klingt mir sehr nach einer Hausaufgabe. Was hast du denn bis jetzt versucht, bzw. wo hakt es?

Falls es keine Hausaufgabe ist: warum iterativ? Das ist in diesem Falle sehr unpraktisch, am Ende bastelst du dir den Stack der jetzt für die Rekursion gebraucht wird einfach nach.
afroasiate

Mittwoch 30. November 2005, 21:55

Ja waurm iterativ, gute frage :-)

Es handelt sich um eine Aufgabe für eine Theoretische Infromatik Vorlesung

Die Aufgabe war folgende:

Aufgabe 5.1 Geben Sie einen nicht-rekursiven Algorithmus an, der auf Eingabe eines Baums T die Postorder von T ausgibt. T ist uber die mehrfach verkettete Darstellung und einen Zeiger auf die Wurzel von T gegeben.
Ihr Algorithmus darf hierbei nur konstanten Speicherplatz benutzen { wobei wir die Ausgabe (die nur geschrieben aber nicht gelesen werden darf) und die Eingabe (die nur gelesen aber nicht beschrieben werden darf) nicht mitzahlen.



Den Algorithmus habe ich mittlerweile, Du hattest schon recht der Stack wird einfach nach gebaut.

cu
afro
BlackJack

Donnerstag 1. Dezember 2005, 00:32

Wenn Du den Stack einfach nachgebaut hast, dann hast Du die Aufgabe wahrscheinlich nicht bzw. falsch gelöst. Wieviele Elemente der Stack enthält hängt von der Tiefe des Baums ab, in der Aufgabe steht aber, das der Speicherbedarf von Deinem Algorithmus konstant sein soll, also unabhängig von der Grösse des Baums.
Antworten