Innere Knoten zählen in einem binären Baum

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
Mindychen
User
Beiträge: 6
Registriert: Sonntag 12. Februar 2017, 04:07

Hallo ihr lieben,

ich habe am Ende des Monats eine Klausur in Info 1 und bin gerade dabei dafür zu lernen.
Wir hatten eine Probeklausur in der es eine Aufgabe gibt, wo ich einfach nicht darauf komme, wie man die lösen könnte.

Die Aufgabe selber lautet:

Im Folgenden gehen wir davon aus, dass die Knoten eines Binärbaumes als Tupel (left, label, right) repräsentiert werden, wobei left der linke Teilbaum, label die Makierung und right der Rechte Teilbaum ist.
Der leer Baum wird durch None repräsentiert.

Schreiben Sie die Funktion inner_nodes(tree), die für einen übergebenen Binärbaum tree die Anzahl der inneren Knoten zählt und zurück gibt.

Ich wollte es zunächst mit der mit vertrauteren Definition [label, left, right] versuchen und dachte
vielleicht kanne ich die Preorder traversierung irgendwie verändern, die Knoten die es findet in eine Liste schreiben, das klappt jedoch alles nicht, da die rekursion dabei Probleme macht.

Code: Alles auswählen

def preorder(node):
    if node is not None:
        print(node[0])
        preorder(node[1])
        preorder(node[2])
Wir haben in der Vorlesung nicht viel anderes erhalten, ein Beispiel der Postorder_implementierung, Search in Tree und eine Searchtree Implementierung.

Ich habe wenig hilfreiches im Internet gefunden, da dort alles mit Klassen gelöst worden ist, was jedoch in dieser Aufgabe nicht gefragt ist, da es ja nur eine einzelen aufgabe ist zu dem thema, die genau so heißt wie oben geschrieben. Der b) Teil in dem soll man nur einen test schreiben.
Es sollte auch relativ wenig Code genügen da es ja eine Klausuraufgabe ist (und auch relativ wenig Platz zum Lösung hinschreiben gegeben wurde).

Ich dachte man müsste irgendwie überprüfen können ob ein Knoten ein Blatt ist und wenn nicht ihn dann in eine Liste schreiben und dann die elemente der liste zählen.

Aber wie gesagt durch die wenige Hilfestellung aus der Vorlesung habe ich keine Ahnung wie ich das anstellen könnte. Ich hatte ja den Ansatz ob man z.B. die obige preorder-funktion umschreiben könnte, meine Versuche scheiterten. Geht das überhaupt als Ansatz oder ist das totaler Mist?

Ich hab 3 verschiedene Bücher hier zu Python, aber in keinem wird auch nur Bäume erwähnt. :/
Kann mir jemand helfen? Bin etwas verzweifelt und hab auch ganz schön angst vor der klausur. :?
Zuletzt geändert von Anonymous am Sonntag 12. Februar 2017, 10:41, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Am sinnvollsten ist erstmal ein paar Beispiele zu wählen, die sollten so einfach wie möglich sein und doch alle möglichen Fälle abdecken. In diesem Fall bieten sich dazu 3 Beispiele an:
  • Blatt / Leerer Baum: None
  • Innerer Knoten: (None, 'label', None)
  • Innerer Knoten mit nicht-leeren Teilbäumen: ((None, 'left', None), 'middle', (None, 'right', None))
Überleg dir was inner_nodes zurückgeben muss damit es für das erste Beispiel das richtige Ergebnis zurück gibt, ignorier dabei die anderen Beispiele. Wenn du das geschafft hast schau dir das nächste Beispiel an und verändere inner_nodes so, dass es das richtige Ergebnis für das erste und das zweite Beispiel zurückgibt usw.

Wenn inner_nodes mit diesen 3 Beispielen funktioniert und es halbwegs sinnvoll implementiert ist, sollte es immer funktionieren. Um nochmal sicherzugehen, kann man sich aber auch hier nochmal ein paar komplexere Beispiele überlegen.
Mindychen
User
Beiträge: 6
Registriert: Sonntag 12. Februar 2017, 04:07

Danke danke für deine Antwort!
Kann ich denn Strukutren vergleichen, also sagen wenn das die Form hat (None, "irgendwas", None) dann mache das und das?
Das war eigentlich mein größtes Problem. Die Knoten sehen ja alles unterschiedlich aus nur die Form ist gleich.

Hmm ich wollte es urprünglich mit einer If-Schleife und dem Gleichheitsoperator == machen. Ich weiß gar nicht wie ich in den nächsten Knoten gehen könnte außer durch Rekursion und die macht dann wiederum probleme.

Ich frag mich gerade auch ob einen Denkfehler habe.
Ich hätte jetzt gesagt Blatt ist (None, label, None).
innererknoten nur das: ((None, 'left', None), 'middle', (None, 'right', None))
Blatt / Leerer Baum: None
Innerer Knoten: (None, 'label', None)
Innerer Knoten mit nicht-leeren Teilbäumen: ((None, 'left', None), 'middle', (None, 'right', None))
Kannst du mir vllt nochmal ein Tipp geben womit man es implementieren könnte? (if, rekursion)
Ich habe keine Ahnung wie ich sagen kann was ein innere Knoten ist, außer mit dem Gleichheitsoperator == was ja so nicht klappt, da sie ja nicht immer genau gleich sind.

Ich probiers heute abend nochmal. Aber wahrscheinlich muss ich es dann lassen, ich hab schon gestern zu lange zeit damit verbracht darüber zu googlen und die inorder umzuschreiben.
Ich find die Aufgabe irgendwie total mies, es gab in den Übungsblättern 2 Aufgaben über Bäume und auch allgemein, es wird etwas eingeführt und dann geht man davon aus, dass das reicht und man es kann :D . Ich habe erst bei einem Vorkurs aus dem Internet etwas sicherheit im Programmieren bekommen, in dem sich Lösungansätze wiederholt haben in verschiedene Aufgaben, so das sich etwas festigen konnte.

Aber danke dir vielmals!
BlackJack

@mindychen: Also erst einmal ganz wichtig: http://if-schleife.de/

Strukturen vergleichst Du in dem Du die Einzelkomponenten die Dich auf die Werte prüfst die einen inneren Knoten ausmachen. Wie gesagt: Am besten „entpackst“ Du das Tupel auf Namen und machst die Vergleiche mit den benannten Werten. Dann wird das gleich lesbarer. „Pattern matching“ kennt Python nicht. Das ginge in Haskell. :-)

Für Tests auf `None` verwendet man in der Regel ``is`` und ``is not`` statt ``==`` und ``!=`` weil es den Wert `None` garantiert nur einmal gibt. (Singleton)

Warum macht die Rekursion Probleme? Und welche? Das ist eine klassische Aufgabe zum Thema Rekursion/rekursive Datenstruktur. Und die Implementierung ist auch sehr einfach und kurz. Man muss eigentlich nur Rekursion verstanden haben. Dazu muss man Rekursion verstehen. ;-)

Ich würde sagen die Definition von Blatt/Innerer Knoten von DasIch ist falsch und hätte auch gesagt das sein innerer Knoten ein Blatt ist. In der Aufgabe steht ja das `None` der leere Baum ist. Das ein leerer Baum gleichzeitig ein Blatt sein soll steht da nicht. Und ein Blatt ist üblicherweise als Knoten ohne Kinder definiert. Was auf (None, 'irgendwas', None) IMHO zutrifft, denn leere Bäume sind ja keine Kindknoten.

Allerdings ist innerer Knoten nicht *nur* das 3. Beispiel, denn es gibt noch zwei andere Varianten.
Mindychen
User
Beiträge: 6
Registriert: Sonntag 12. Februar 2017, 04:07

oh, ja klar meinte doch if-abfragen :D *haha* :oops:
ok, danke danke danke!

es hilft mir sehr wenigstens sicher die Richtung zu wissen, dann wirkt es nicht so aussichtslos.
eigentlich hatte ich rekursionen schon ganz gut mittlerweile verstanden. Am Anfang hab ich sie total gehasst, aber dann viele Aufgaben die man auch einfach ohne Rekursion hätte Implementieren können alle mit Rekursion gelöst :D.
Aber an der baum Struktur mit diesen verschachtelten listen bzw. jetzt tupeln tue ich mich etwas schwer.,

ich mach mich gleich nochmal dran.
BlackJack

@Mindychen: Die Baumstruktur ist ja aber genau der Grund warum eine rekursive Funktion Sinn macht, eben weil es eine rekursive Datenstruktur ist. Der ”Trick” ist eigentlich immer nur in der Funktion bei einem Aufruf nicht zu viel machen zu wollen. Mir hat es am Anfang geholfen so zu tun als wenn man schon eine Funktion hat, die die Aufgabe löst. Also zum Beispiel `magic_inner_nodes()`. Und nun kann man eine `inner_nodes()`-Funktion für *einen* Knoten im Baum schreiben, die diese `magic_inner_nodes()` verwendet. Wenn man das gemacht hat, kann man den oder die Aufrufe von `magic_inner_nodes()` einfach in `inner_nodes()`-Aufrufe ändern, denn diese Funktion macht ja jetzt was sie soll unter der Voraussetzung man hat eine Funktion die das macht. Rekursion halt. :-)

Mal mit Haskell ein Beispiel wie das in einer Sprache mit „pattern matching“ aussehen kann auf so einer Baumstruktur zu operieren:
[codebox=haskell file=Unbenannt.hs]data Tree a = Node (Tree a) a (Tree a)
| Nil
deriving Show

fac 0 = 1
fac n = n * fac (n - 1)

evaluate Nil = 0
evaluate (Node Nil n Nil) = read n
evaluate (Node left "+" right) = evaluate left + evaluate right
evaluate (Node left "*" right) = evaluate left * evaluate right
evaluate (Node left "!" Nil) = fac $ evaluate left

main :: IO ()
main =
let tree = Node (Node (Node Nil "23" Nil) "*" (Node Nil "42" Nil))
"+"
(Node (Node Nil "5" Nil) "!" Nil)
in do
putStrLn $ show $ evaluate tree
[/code]
Mindychen
User
Beiträge: 6
Registriert: Sonntag 12. Februar 2017, 04:07

Danke dir.
Ich hab meinen Tutor geschrieben, der hat es mir dann mit einem Pseudocode erklärt, damit habe ich es dann geschafft. x)
Im Nachinein war mein Problem, dass ich es nur mit einer einzelnden Rekursion probiert habe.
Es aber zwei gebraucht hat:

Code: Alles auswählen

return countInnerNodes(tree[0]) + countInnerNodes(tree[2]) + 1
Also ich kanns jetzt nachvollziehen und habe auch eine Funktion für Blätter und für alle Knoten geschrieben, jedoch die denkweise um darauf zu kommen ist jetzt noch nicht so da :D.

Bräuchte vllt noch andere Aufgaben die man so ähnlich löst um es noch besser zu begreifen und alleine dann drauf zu kommen (fibonacci ist ja z.B. eine aber die kenne ich schon).
Es war überhaupt gar nicht auf meinen Schirm zwei Rekursionen zu nutzen, daher war es wirklich unlösbar so für mich :D.
BlackJack

@Mindychen: In der Traversierungsfunktionen sind ist doch auch ein rekursiver Aufruf für den rechten und den linken Teilbaum und so eine Funktion hattest Du doch schon im ersten Beitrag‽

Ich würde wie schon mal geschrieben dringend von den ”magischen” Indexzugriffen Abstand nehmen und das Tupel ”entpacken”. Es wird viel verständlicher wenn man mit Namen operiert statt mit 0, 1, und 2. Dann kommt man auch eher darauf, dass man zwei rekursive Aufrufe in der Funktion braucht.

Die ``+ 1`` am Ende sieht falsch aus. Das würde ja nur stimmen wenn es sich bei `tree` auch tatsächlich um einen inneren Knoten handelt.

Fibonacci ist aber eigentlich eine Funktion bei der die rekursive Lösung vorsichtig ausgedrückt suboptimal ist. Es macht mehr Sinn Sachen rekursiv zu lösen wo das auch Sinn macht weil man die nicht so leicht durch eine Schleife ersetzen kann.

Ich habe übrigens gerade Modul gefunden mit dem man Python-Funktionen „pattern matching“ per Decorator verpassen kann. Mal das Haskellprogramm damit ausgedrückt:

Code: Alles auswählen

from math import factorial
from patterns import patterns


@patterns
def evaluate():
    if (None, n, None): int(n)
    if (left, '+', right): evaluate(left) + evaluate(right)
    if (left, '*', right): evaluate(left) * evaluate(right)
    if (left, '!', None): factorial(evaluate(left))


def main():
    tree = (
        ((None, '23', None), '*', (None, '42', None)),
        '+',
        ((None, '5', None), '!', None)
    )
    print(evaluate(tree))


if __name__ == '__main__':
    main()
Mindychen
User
Beiträge: 6
Registriert: Sonntag 12. Februar 2017, 04:07

ah oki :). ja, danke für den tipp! ich werde in zukunft es erstmal versuchen zu "entpacken" :). im prinzip kam ich dann auch so drauf, mein tutor hatte mir nur einen pseudo code mit (left, lable, right) geschickt, dadurch hatte ich dann besser verstanden was wirklich konkret gefragt ist (das return war aber schon so dargestellt wie unten).

Code: Alles auswählen

def countInnerNodes(tree):
    if tree == None:
        return 0
    elif len(tree) == 1:
        return 0
    elif tree[0] == None and tree[2] == None:
        return 0
    else:
        return countInnerNodes(tree[0]) +1 + countInnerNodes(tree[2])
Also so sieht die funktion aus. Ja oben in meiner preorderfunktion werden aber einzelene rekursionen (also nicht zusammen addiert oder sonst was) und vorallem konnte ich mich da an der postorder funktion aus der Vorlesung orientieren.
Aber ja ehrlich gesagt fand ich die auch schwer zu verstehen.
Die Funktion funktioniert auch bei allen getesten bäume :)
Zuletzt geändert von Anonymous am Montag 13. Februar 2017, 09:31, insgesamt 1-mal geändert.
Grund: Quelltext in Python-Codebox-Tags gesetzt.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@Mindychen: zumindest der zweite Fall sollte bei einem fehlerfrei definierten Baum nicht auftreten. Da würde ich Python in einen ValueError laufen lassen:

Code: Alles auswählen

def count_inner_nodes(tree):
    left, label, right = tree
    if left is right is None:
        return 0
    result = 1
    if left is not None:
        result += count_inner_nodes(left)
    if right is not None:
        result += count_inner_nodes(right)
    return result
Mindychen
User
Beiträge: 6
Registriert: Sonntag 12. Februar 2017, 04:07

ahja genau, das ist mir schon mal passiert, dass ich die None 's vergessen habe. ich war schon müde und dachte man müsste auch einen knoten eingeben können ohne fehler also (lable), aber das müsste ja dann (None, lable, None) heißen. :oops:
BlackJack

@Sirius3: Dein Code funktioniert nicht für den leeren Baum, der ist in der Aufgabe ja einfach als `None` definiert.

@all: Das `patterns`-Modul hat mich zur Programmiersprache Coconut gebracht. Das ist eine Obermenge von Python um funktionale Konstrukte wie „pattern matching“ erweitert. Der Compiler spuckt reguläres Python aus.

Code: Alles auswählen

from math import factorial


def is_inner_node(None) = False

@addpattern(is_inner_node)
def is_inner_node((None, _, None)) = False

@addpattern(is_inner_node)
def is_inner_node(_) = True


def count_inner_nodes(None) = 0

@addpattern(count_inner_nodes)
def count_inner_nodes((left, _, right) as node) =
    (
        (0 if is_inner_node(node) else 1)
        + count_inner_nodes(left)
        + count_inner_nodes(right)
    )


def evaluate(None) = 0

@addpattern(evaluate)
def evaluate((None, n, None)) = int(n)

@addpattern(evaluate)
def evaluate((left, '+', right)) = evaluate(left) + evaluate(right)

@addpattern(evaluate)
def evaluate((left, '*', right)) = evaluate(left) * evaluate(right)

@addpattern(evaluate)
def evaluate((left, '!', None)) = left |> evaluate |> factorial


def main():
    tree = (
        ((None, '23', None), '*', (None, '42', None)),
        '+',
        ((None, '5', None), '!', None)
    )
    tree |> count_inner_nodes |> print
    tree |> evaluate |> print


if __name__ == '__main__':
    main()
Zum Vergleich noch mal das ganze Programm in Haskell:
[codebox=haskell file=Unbenannt.hs]
data Tree a = Node (Tree a) a (Tree a)
| Nil
deriving Show

isInnerNode Nil = False
isInnerNode (Node Nil _ Nil) = False
isInnerNode _ = True

countInnerNodes Nil = 0
countInnerNodes node @ (Node left _ right) =
let thisCount = if isInnerNode node then 1 else 0
leftCount = countInnerNodes left
rightCount = countInnerNodes right
in thisCount + leftCount + rightCount

fac 0 = 1
fac n = n * fac (n - 1)

evaluate Nil = 0
evaluate (Node Nil n Nil) = read n
evaluate (Node left "+" right) = evaluate left + evaluate right
evaluate (Node left "*" right) = evaluate left * evaluate right
evaluate (Node left "!" Nil) = fac $ evaluate left

main :: IO ()
main =
let tree = Node (Node (Node Nil "23" Nil) "*" (Node Nil "42" Nil))
"+"
(Node (Node Nil "5" Nil) "!" Nil)
in do
putStrLn $ show $ countInnerNodes tree
putStrLn $ show $ evaluate tree[/code]
Antworten