Edellinen ja seuraava

Toteuta kurssimateriaalin mukainen binäärihakupuu, joka sisältää metodit prev ja next edellisen ja seuraavan alkion hakemiseen. Toteuta metodit kurssimateriaalissa kuvatulla tavalla.

Metodin prev tulee palauttaa suurin alkio, joka on pienempi kuin parametrina annettu alkio. Vastaavasti metodin next tulee palauttaa pienin alkio, joka on suurempi kuin parametrina annettu alkio. Jos haluttua alkiota ei ole olemassa, metodien tulee palauttaa None.

Toteuta tiedostoon prevnext.py luokka TreeSet seuraavan mallin mukaisesti. Tehtäväsi on täydentää metodit prev ja next. 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 prev(self, value):
        # TODO

    def next(self, value):
        # TODO

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

    numbers.add(3)
    numbers.add(2)
    numbers.add(5)
    numbers.add(7)

    print(numbers.prev(5)) # 3
    print(numbers.prev(4)) # 3
    print(numbers.prev(3)) # 2
    print(numbers.prev(2)) # None

    print(numbers.next(4)) # 5
    print(numbers.next(5)) # 7
    print(numbers.next(6)) # 7
    print(numbers.next(7)) # None