Rekursive Suchbäume iterativ umwandel

[Halunke41]

Guten Tag,

mein Kollege und ich sind neu in der Programmierung und als Aufgabe haben wir uns einen Suchbaum aus dem Internet genommen und diesen wollen wir iterativ schreiben.

Der Code:

Code: Alles auswählen

def node(l,v,r) :
    return [l,v,r]

def empty() :
    return []

def left(l) :
    return l[0]

def right(l) :
    return l[2]

def value(l) :
    return l[1]

def is_empty(t) :
    return t == []

def empty_to_node(t,v) :
    if is_empty(t) :
      t.extend([empty(),v,empty()])


def empty_st() :
    return empty()

def elem(v,t) :
    
    if is_empty(t) :
        return False
    elif v < value(t) :
        return elem(v,left(t))
    elif v > value(t) :
        return elem(v,right(t))
    else :
        return True
    
def add(v, t) :
    if is_empty(t) :
        empty_to_node(t,v)
        return True           # value added successfully
    elif v < value(t) :
        return add(v,left(t))
    elif v > value(t) :
        return add(v,right(t))
    else :
        return False    # value already in tree
    
def empty_search_tree() :
    return empty()

test_tree = node(node(empty(),2,empty()),5,node(empty(),7,node(empty(),10,empty())))

print(elem(3,test_tree))
print(add(8,test_tree))
print(test_tree)

for i in range(12) :
    print((i,elem(i,test_tree)))

Dabei wollen wir uns auf def elem und def add beziehen.
Wie würdet ihr vorgehen?
Wir haben überlegt mit while oder for in schleifen zu Arbeiten.
Vielen dank im Vorraus

[__deets__]

Ihr *wollt*? Oder ihr *sollt*? Und was heisst iterativ schreiben? Was soll denn da iteriert werden?

[sparrow]

Mit den Hausaufgaben war die Tage schon jemand da. Den Beitrag findest du bestimmt

[Sirius3]

Beim Programmieren kommt es auf Lesbarkeit an, einbuchstabige Variablennamen sind nur schlecht lesbar. Magische Indexwerte genausowenig. Eingerückt wird immer mit 4 Leerzeichen pro Ebene.
`empty_to_node` tut einfach nichts, wenn die Node nicht leer ist, das kann zu schwer zu findende Fehler führen. Im Fehlerfall sollte nicht einfach "nichts" passieren, sondern eine Fehlermeldung ausgegeben werden.
Warum gibt es `empty_st`?
`elem` sollte `is_value_in_tree` heißen, wie ich schon im anderen Thread von Deinem Kollegen geschrieben hatte.
`empty_search_tree` ist die dritte Variante von `empty`. Warum nur?

Hier das ganze mal in einigermaßen lesbar:

Code: Alles auswählen

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

    def __str__(self):
        return f"<{self.left}, {self.value}, {self.right}>"


def is_value_in_tree(value, tree):
    if tree is None:
        return False
    elif value < tree.value:
        return is_value_in_tree(value, tree.left)
    elif value > tree.value:
        return is_value_in_tree(value, tree.right)
    else:
        return True


def add(value, tree):
    if value < tree.value:
        if tree.left is None:
            tree.left = Node(value)
            return True
        return add(value, tree.left)
    elif value > tree.value:
        if tree.right is None:
            tree.right = Node(value)
            return True
        return add(value, tree.right)
    else:
        return False

test_tree = Node(left=Node(2), value=5, right=Node(7, right=Node(10)))

print(is_value_in_tree(3, test_tree))
print(add(8, test_tree))
print(test_tree)

for i in range(12):
    print((i, is_value_in_tree(i, test_tree)))

oder gleich mit einer `Tree`-Klasse:

Code: Alles auswählen

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

    def __str__(self):
        return f"<{self.left}, {self.value}, {self.right}>"


class Tree:
    def __init__(self, values):
        self.node = None
        for value in values:
            self.add(value)

    def __contains__(self, value, node=None):
        def contains(node):
            if node is None:
                return False
            elif value < node.value:
                return contains(node.left)
            elif value > node.value:
                return contains(node.right)
            else:
                return True
        if self.node is None:
            return False
        else:
            return contains(self.node)

    def add(self, value, node=None):
        if node is None:
            if self.node is None:
                self.node = Node(value)
            else:
                self.add(value, self.node)
        elif value < node.value:
            if node.left is None:
                node.left = Node(value)
                return True
            return self.add(value, node.left)
        elif value > node.value:
            if node.right is None:
                node.right = Node(value)
                return True
            return self.add(value, node.right)
        else:
            return False

    def __str__(self):
        return '<>' if self.node is None else str(self.node)

test_tree = Tree([5,2,7,10])

print(3 in test_tree)
print(test_tree.add(8))
print(test_tree)

for i in range(12):
    print((i, i in test_tree))

Der Ansatz mit einer while-Schleife ist mal gar nicht so schlecht.