50 lines
1.2 KiB
Python
50 lines
1.2 KiB
Python
# Aufgabe 6: Rekursion
|
|
from dataclasses import dataclass
|
|
from typing import Optional
|
|
|
|
|
|
@dataclass
|
|
class Node[T]:
|
|
mark: T
|
|
left: Optional["Node[T]"] = None
|
|
right: Optional["Node[T]"] = None
|
|
|
|
|
|
type BTree[T] = Optional[Node[T]]
|
|
|
|
|
|
# a)
|
|
def sum_of_subtree(tree: BTree[int]) -> int:
|
|
match tree:
|
|
case None:
|
|
return 0
|
|
case Node(_, left, right):
|
|
tree.mark += sum_of_subtree(left) + sum_of_subtree(right)
|
|
return tree.mark
|
|
|
|
|
|
# b)
|
|
def cut_at[T](tree: BTree[T], at: T) -> BTree[T]:
|
|
match tree:
|
|
case None:
|
|
return None
|
|
case Node(mark, _, _) if mark == at:
|
|
return None
|
|
case Node(mark, left, right): # f(mark)
|
|
return Node(mark, cut_at(left, at), cut_at(right, at))
|
|
|
|
|
|
if __name__ == "__main__":
|
|
t1 = None
|
|
assert sum_of_subtree(t1) == 0
|
|
assert t1 is None
|
|
|
|
t3 = Node(1, Node(2, Node(3), Node(4)), Node(5, Node(6)))
|
|
assert sum_of_subtree(t3) == 21
|
|
assert t3 == Node(21, Node(9, Node(3), Node(4)), Node(11, Node(6)))
|
|
|
|
assert cut_at(None, 42) is None
|
|
t = Node(1, Node(2, Node(3), Node(4)), Node(3, Node(3), Node(6)))
|
|
assert cut_at(t, 1) is None
|
|
assert cut_at(t, 3) == Node(1, Node(2, None, Node(4)))
|