Läpikäynti

Kurssimateriaalin binäärihakupuun toteutuksessa metodi __repr__ muodostaa lineaarisessa ajassa listan, joka sisältää puun alkiot pienimmästä suurimpaan.

Tehtäväsi on toteuttaa tämä metodi uudestaan ilman rekursiota. Metodin tulee antaa sama tulos kuin ennenkin, ja sen tulee toimia edelleen lineaarisessa ajassa.

Et saa vertailla metodissa puun solmuissa olevia arvoja, vaan lista tulee rakentaa sen perusteella, mikä on solmujen järjestys puussa.

Toteuta tiedostoon traversal.py luokka TreeSet seuraavan mallin mukaisesti. Et saa lisätä luokkaan muita metodeja kuin tehtäväpohjassa olevat.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class TreeSet:
    def __init__(self):
        self.root = None

    def add(self, value):
        if not self.root:
            self.root = Node(value)
            return

        node = self.root
        while True:
            if node.value == value:
                return
            if node.value > value:
                if not node.left:
                    node.left = Node(value)
                    return
                node = node.left
            else:
                if not node.right:
                    node.right = Node(value)
                    return
                node = node.right

    def __repr__(self):
        # TODO

if __name__ == "__main__":
    numbers = TreeSet()

    numbers.add(4)
    numbers.add(1)
    numbers.add(2)
    numbers.add(5)
    numbers.add(8)
    numbers.add(7)

    print(numbers) # [1, 2, 4, 5, 7, 8]