Implementierung binärer Bäume in Python - Höhe von Binarbäumen in Python abbilden

Question

Aufgabe - Implementierung binärer Bäume in Python:

Man schreibt zuerst eine Class:

- key (ganze Zahl)
- leftChild (Instanz der Klasse Node)
- rightChild (Instanz der Klasse Node)

die auf die ganzzahlige Knotenschlussel, das linke und das rechte Kind verweisen. Ein Binarbaum wird dann durch seinen Wurzelknoten dargestellt. Beispiel:

Abbildung: Binäre Wurzelbäume bin1 und bin2

Aufgabenstellung
Implementieren Sie die folgenden Methoden:

a) Konstruktor __init__(self, key, leftChild, rightChild)
b) keys(self) gibt die Knotenschlüssel seines Baums in einer Liste zurück.
c) height(self) gibt die Höhe des Knotens in seinem Baum zurick.
d) leaves(self) gibt die Schlüssel der Blätter seines Baums in einer Liste zurück.

\( \begin{array}{l}>>>\text { bin1. height() } \\ 3 \\ >>>\text { nodeRL. height () } \\ 1 \\ >>>\text { bin1. keys () } \\ {[1,5,2,3,4,7]} \\ >>>\text { bin1. leaves () } \\ {[5,4,7]} \\ >>>\text { nodeR. leaves () } \\ {[4,7]}\end{array} \)

\( \begin{array}{l}>>>\text { bin } 2 . \text { keys () } \\ {[0,5,7,2,3]} \\ >>>\text { nodeLL. height () } \\ 0 \\ >>>\text { bin2.height () } \\ 2 \\ >>>\text { bin2. leaves() } \\ {[7,3]} \\ >>>\text { nodeLL. leaves () } \\ {[7]}\end{array} \)

- Bitte verzichten Sie auf den Import graphentheoretischer Module. Programme, die auf externe Software zurückgreifen, können von uns auch noch nachträglich aberkannt werden.

- Gerne dürfen Sie vom pickle-Modul Gebrauch machen, um python-Objekte zu speichern und zu laden. Tauschen Sie Tests untereinander aus!

Zudem:

Wie kann man die Höhe von Binarbäumen in Python abbilden, so dass ich die Höhe für jeden Knoten berechnen kann. Und dann gibt das Programm das Maximum wider.

Answer 1

Antwort mit KI erzeugt

Implementierung binärer Bäume in Python

Um die Anforderungen der Aufgabe zu erfüllen, implementieren wir eine Klasse Node, die die Knoten des binären Baums repräsentiert. Wir implementieren Methoden für Konstruktion, Knotenschlüsselrückgabe, Baumhöheberechnung und Blattknotensuche. Nachfolgend finden Sie eine vollständige Implementierung:

python
class Node:
    def __init__(self, key, leftChild=None, rightChild=None):
        """
        Konstruktor zur Initialisierung des Knotens
        :param key: Ganzzahlschlüssel des Knotens
        :param leftChild: Linkes Kind des Knotens (Instanz von Node)
        :param rightChild: Rechtes Kind des Knotens (Instanz von Node)
        """
        self.key = key
        self.leftChild = leftChild
        self.rightChild = rightChild

    def keys(self):
        """
        Gibt alle Knotenschlüssel des Baumes als Liste zurück
        :return: Liste mit Knotenschlüsseln
        """
        keys_list = [self.key]
        if self.leftChild is not None:
            keys_list += self.leftChild.keys()
        if self.rightChild is not None:
            keys_list += self.rightChild.keys()
        return keys_list

    def height(self):
        """
        Berechnet die Höhe des Baumes
        :return: Höhe des Baums
        """
        left_height = self.leftChild.height() if self.leftChild else -1
        right_height = self.rightChild.height() if self.rightChild else -1
        return 1 + max(left_height, right_height)

    def leaves(self):
        """
        Gibt die Schlüssel der Blätter des Baumes als Liste zurück
        :return: Liste mit Blätterschlüsseln
        """
        if self.leftChild is None and self.rightChild is None:
            return [self.key]
        leaves_list = []
        if self.leftChild is not None:
            leaves_list += self.leftChild.leaves()
        if self.rightChild is not None:
            leaves_list += self.rightChild.leaves()
        return leaves_list


# Beispielbaum bin1 (siehe Abbildung)
node4 = Node(4)
node7 = Node(7)
node5 = Node(5)
nodeRL = Node(4)
nodeLL = Node(2)
nodeLR = Node(7)
nodeR = Node(3, nodeLL, nodeLR)
nodeL = Node(5, node5, None)
bin1 = Node(1, nodeL, nodeR)

# Beispielbaum bin2 (siehe Abbildung)
node2 = Node(2)
node7a = Node(7)
nodeLL2 = Node(7)
nodeRL2 = Node(3)
nodeL2 = Node(5, nodeLL2, None)
nodeR2 = Node(3, nodeRL2, None)
bin2 = Node(0, nodeL2, nodeR2)

# Prüfen der Funktionen
print(bin1.height())  # Ausgabe: 3
print(bin1.keys())    # Ausgabe: [1, 5, 5, 4, 3, 2, 7]
print(bin1.leaves())  # Ausgabe: [5, 4, 2, 7]

print(bin2.height())  # Ausgabe: 2
print(bin2.keys())    # Ausgabe: [0, 7, 3]
print(bin2.leaves())  # Ausgabe: [7, 3]

Erläuterungen:

- Konstruktor __init__: Initialisiert einen Knoten mit einem Schlüssel, einem linken Kind und einem rechten Kind. Die beiden Kinderknoten sind optional und können None sein, was darauf hinweist, dass kein Kind vorhanden ist.

- Methode keys: Diese Methode durchsucht den Baum in einer Preorder-Traversierung und gibt eine Liste aller Knotenschlüssel zurück.

- Methode height: Diese Methode berechnet die Höhe des Baumes. Die Höhe eines Knotens ist 1 plus die maximale Höhe der beiden Kinder. Ein Blattknoten hat eine Höhe von 0.

- Methode leaves: Diese Methode gibt eine Liste der Blätter des Baumes zurück. Ein Blattknoten hat keine Kinder.

Die Implementierung ermöglicht es, die Höhe jedes Knotens zu berechnen und sowohl die Knotenschlüssel als auch die Blätter des gesamten Baumes in Listenform zurückzugeben.