Das deutsche Python-Forum

Hallo,

als Python-Neuling versuche ich mich gerade an einer rekursiven Funktion zum Durchlaufen eines Baumes:

Ich habe einen Baum aus Objekten der selben Klasse. Jeder Knoten des Baumes kann keine oder beliebig viele Unterknoten aufweisen.
Diesen Baum möchte ich als CSV exportieren. Dazu muss ich jedes "Blatt" (Knoten ohne Kinder) einmal besuchen, den Weg dorthin mitschreiben und diesen dann als Zeile in die Datei abspeichern.

Beispiel:

Code: Alles auswählen

# Baum:
#    +--B
#    !
# A--+
#    !     +--D
#    !     !
#    +--C--E
#          !
# 	   +--F
#
# CSV:
# A
# A, B
# A, C
# A, C, D
# A, C, E
# A. C, F
#
# Python:
class obj:
    def __init__(self, name, children=[]):
        self.name=name
        self.children=children

tree=obj("A",[obj("B",[obj("D"),obj("E"),obj("F")]),obj("C")])

Mein bisheriger Lösungsansatz

Code: Alles auswählen

def nextchild(obj):
    print("call for ",obj.name)
    if (obj.children):
        print("  got child")
        for child in obj.children:
            print ("    name: ",child.name)
            return nextchild(child)
    else:
        print("  last child")

nextchild(tree)

funktioniert leider nicht. Ich würde das Problem gerne auf "Python-Art" lösen. Habt ihr einen Tipp für mich?
Viele Grüße

Alles was es da doch braucht ist ein Argument "path" an nextchild, das per default der leere String ist. Und jeder Aufruf an nextchild fuegt dem einfach den akutellen obj.name hinzu, und reicht den weiter runter. Im Rekursionsbeginn (else-Zweig) kannst du dann den ganzen Pfad ausgeben.

__deets__ hat geschrieben: Mittwoch 31. August 2022, 15:58 Alles was es da doch braucht ist ein Argument "path" an nextchild, das per default der leere String ist. Und jeder Aufruf an nextchild fuegt dem einfach den akutellen obj.name hinzu, und reicht den weiter runter. Im Rekursionsbeginn (else-Zweig) kannst du dann den ganzen Pfad ausgeben.

Das mit dem Pfad ist klar. Den wollte ich über eine globale Variable lösen zu der ich mit jedem Aufruf von nextchild() ein Item hinzufüge und bei jedem Verlassen das jeweils letzte Item lösche.

Mein Problem ist aber, dass die Rekursion nicht wie geplant funktioniert.
Die Ausgabe ist:

Code: Alles auswählen

call for  A
  got child
    name:  B

call for  B
  got child
    name:  D

call for  D
  last child

erwarten würde ich aber

Code: Alles auswählen

call for  A
  got child
    name:  B

call for  B
  got child
    name:  D

call for  D
  last child
    name: E

call for  E
  last child
    name: F
    
call for  F
  last child
    name: C
    
call for  C
  last child

Eine globale Variable ist keine Loesung. Sondern nahezu immer falsch, weil eben eine globale Variable. Und gerade hier ist das doch total offensichtlich: wenn du musst wesentlich mehr Code schreiben, um deinen globalen Zustand wieder auf den Wert vorher zu bekommen, statt einfach durch Argumente dafuer zu sorgen, dass fuer jedes Kind der gerade aktuelle Pfad uebergeben wird.

Und sehe an der Augabe nichts, was sagt, dass geht nicht. Das ist doch richtig. Was genau fehlt dir da?

Das mit dem Pfad als Parameter ist mir noch nicht ganz klar. Kannst du mir da mit ein zwei Zeilen Code auf die Sprünge helfen?
So wie ich die Ausgabe interpretiere läuft der Algorithmus folgenden Weg:
A --> B --> D
wenn also jeder Aufruf eine Zeile CSV ausgibt hätte ich drei Zeilen:
A
A,B
A,B,D

mir fehlen dann aber noch:
A,B,E
A,B,F
A,C

Meinst du das mit dem Path so?

Code: Alles auswählen

def nextchild(obj, path):
    print("call for ",obj.name)
    path.append(obj.name)
    if (obj.children):
        print("  got child")
        for child in obj.children:
            print ("    name: ",child.name)
            if (input()!=""):break
            return nextchild(child)
    else:
        print("PATH: ", path)
        path=path[:-1]

@beQSwa: `obj` ist kein guter Name für eine Klasse. Zum einen erkennt man nicht, das es eine Klasse ist, denn Klassennamen werden in Python per Konventionen in PascalCase geschrieben, das heisst die Worte aus denen der Name zusammengesetzt ist, beginnen mit Grossbuchstaben. Aber auch `Obj` wäre nicht gut, weil a) kryptische Abkürzung und b) absolut nichtssagend. Dieser Wert wird im Kontext von Bäumen in der Regel „Knoten“, oder englisch „node“ genannt, also als Klasse dann `Node`.

Veränderbare Objekte als Defaultwerte sind gefährlich, weil es den Wert nur *einmal* gibt. Das ist bei jeden Aufruf das *selbe* Objekt, und bei Klassen dann auch noch für jedes Exemplar:

Code: Alles auswählen

In [3]: class Node: 
   ...:     def __init__(self, name, children=[]): 
   ...:         self.name = name 
   ...:         self.children = children 
   ...:                                                                         

In [4]: node_a = Node("A")                                                      

In [5]: node_a.children                                                         
Out[5]: []

In [6]: node_b = Node("B")                                                      

In [7]: node_b.children                                                         
Out[7]: []

In [8]: node_a.children.append(Node("C"))                                       

In [9]: node_a.children                                                         
Out[9]: [<__main__.Node at 0x7f9f59a4f3c8>]

In [10]: node_b.children  # Ooops.                                              
Out[10]: [<__main__.Node at 0x7f9f59a4f3c8>]

Die übliche Lösung ist `None` als Defaultwert zu setzen und in der Funktion oder Methode dann darauf zu testen und gegebenfalls das `None` durch ein neu erstelltes Objekt zu ersetzen.

`nextchild()` ist kein guter Name denn die macht ja nicht nur etwas mit dem nächsten Kindknoten, und es wird auch gar nicht verraten *was* gemacht wird.

Um die Bedingung bei ``if`` gehören keine Klammern.

Ein bedingungsloses ``return`` in einer Schleife macht keinen Sinn, denn dann ist das letztlich ja gar keine Schleife, denn bei einer Schleife die nur genau einmal durchlaufen wird, kann man nicht wirklich von einer Schleife sprechen.

Zudem sollte einfach Funktion mit ``return`` in *jedem* Zweig etwas zurückgeben.

Statt alles in dieser Funktion zu lösen, wäre es einfacher dort nur die Pfadinformationen zu generieren und das Speichern ausserhalb zu machen. Die Pfadinformationen als Listen, weil man die dann einfach an ein Writer-Objekt aus dem `csv`-Modul verfüttern kann um Daten im CSV-Format zu erstellen. Es bietet sich auch eine Generatorfunktion an, statt erst alle Daten in einer weiteren Liste zu sammeln und die bei jedem rekursiven Aufruf durchzureichen.

Quelltext:

Code: Alles auswählen

#!/usr/bin/env python3
import csv
import sys


class Node:
    def __init__(self, name, children=None):
        if children is None:
            children = []
        self.name = name
        self.children = children


def iter_paths(node, path=None):
    path = [node.name] if path is None else path + [node.name]
    yield path
    for child in node.children:
        yield from iter_paths(child, path)


def main():
    tree = Node("A", [Node("B", [Node("D"), Node("E"), Node("F")]), Node("C")])
    csv.writer(sys.stdout).writerows(iter_paths(tree))


if __name__ == "__main__":
    main()

Ausgabe:

Code: Alles auswählen

A
A,B
A,B,D
A,B,E
A,B,F
A,C

Entspricht nicht der Ausgabe im Kommentar, weil sich auch die Struktur des Baums im Code von der im Kommentar unterscheidet.

Puh, vielen Dank!

Das war genau was ich mir gewünscht hatte: Eine Python-Typische, elegante Lösung für mein Problem - wenn auch eine sehr anspruchsvolle.

Warum Python nach dem "Return" nicht einfach in der aufrufenden Schleife weiter macht wo es vor der Iteration stehen blieb habe ich noch nicht verstanden.
Die Generatoren sind allerdings in der Tat die elegantere Lösung. Das Konzept ist mir neu und offenbar etwas, das die Sprache ausmacht. Daran werde ich noch etwas knabbern. Spannend.
Die Syntax-Tipps nehme ich mir zu herzen. Auch dafür vielen Dank.

@beQSwa: ``return`` beendet die Funktion und kehrt zum Aufrufer zurück. Daher der Name des Schlüsselworts ``return`` = „zurückkehren“ (und „zurückgeben“).

Generatoren, oder allgemeiner Coroutinen, mit denen man unter anderem so etwas wie Generatoren schreiben kann, sind kein Alleinstellungsmerkmal von Python, das gibt es auch in anderen Programmiersprachen.

Wenn man so etwas nicht in der Sprache hat, wäre wahrscheinlich die nächsteinfachere Methode um das Iterieren von der Verarbeitung zu trennen, einen internen Iterator zu schreiben. Also eine Rückruffunktion entgegen zu nehmen, die dann die einzelnen Elemente verarbeitet.

Da die Ausgabe sonst gleich bleiben würde und die Änderung an `iter_paths()` nur minimal ist, habe ich zusätzlich zwei nützliche externe Bibliothek eingebunden: `attr` um die Klassendefinition zu vereinfachen, und `prettyprinter` damit die Ausgabe von solchen Objekten schön auf mehrere Zeilen umgebrochen wird:

Code: Alles auswählen

#!/usr/bin/env python3
import csv
import sys

from attr import attrib, attrs
from prettyprinter import cpprint, install_extras

install_extras(["attrs"])


@attrs
class Node:
    name = attrib()
    children = attrib(factory=list)


def iter_paths(node, callback, path=None):
    path = [node.name] if path is None else path + [node.name]
    callback(path)
    for child in node.children:
        iter_paths(child, callback, path)


def main():
    tree = Node("A", [Node("B", [Node("D"), Node("E"), Node("F")]), Node("C")])
    cpprint(tree)
    print("-" * 70)
    iter_paths(tree, csv.writer(sys.stdout).writerow)


if __name__ == "__main__":
    main()

Ausgabe:

Code: Alles auswählen

Node(
    name='A',
    children=[
        Node(
            name='B',
            children=[Node(name='D'), Node(name='E'), Node(name='F')]
        ),
        Node(name='C')
    ]
)
----------------------------------------------------------------------
A
A,B
A,B,D
A,B,E
A,B,F
A,C

Wobei in der Konsole das über der Trennlinie bunt ist, also mit Syntaxhervorhebung. Das `c` in `cpprint()` steht für „colour“.

Das deutsche Python-Forum

Baum rekursiv durchlaufen

Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen

Re: Baum rekursiv durchlaufen