#!/usr/bin/env python
# encoding=utf-8 (pep 0263)
nil = None
def addleaf(tree, x):
if tree == nil:
return (nil, x, nil)
left, root, right = tree
if x == root:
return tree
if root > x:
return (addleaf(left, x), root, right)
else:
return (left, root, addleaf(right, x))
def delleaf(tree, x):
if tree == nil:
return nil
left, root, right = tree
if x == root:
if left == nil:
return right
if right == nil:
return left
right1, y = delmin(right)
return (left, y, right1)
if root > x:
return (delleaf(left, x), root, right)
else:
return (left, root, delleaf(right, x))
def delmin(tree):
if tree == nil:
raise ValueError("delmin je treba volat nad neprazdnym stromem")
left, root, right = tree
if left == nil:
return (right, root)
left1, y = delmin(left)
return ((left1, root, right), y)
def show(tree):
show2(tree, 0)
def show2(tree, indent):
if tree == nil:
return
left, root, right = tree
show2(right, indent+2)
print("%s%s" % (" " * indent, root))
show2(left, indent+2)
# demonstracni vypis
if __name__ == "__main__":
print("Binarni stromy")
print("--------------\n")
print("Vytvoreni stromu:")
print("T = addleaf(nil, 6); T1 = addleaf(T, 8); T2 = addleaf(T1, 2); " +
"T3 = addleaf(T2, 4); T4 = addleaf(T3, 1); show(T4) :")
T = addleaf(nil, 6)
T1 = addleaf(T, 8)
T2 = addleaf(T1, 2)
T3 = addleaf(T2, 4)
T4 = addleaf(T3, 1)
show(T4)
print("\nSmazani uzlu s hodnotou 8:")
print("T5 = delleaf(T4, 8); show(T5) :")
T5 = delleaf(T4, 8)
show(T5)
print("\nSmazani uzlu s hodnotou 2:")
print("T6 = delleaf(T5, 2); show(T6) :")
T6 = delleaf(T5, 2)
show(T6)
Binarni stromy
--------------
Vytvoreni stromu:
T = addleaf(nil, 6); T1 = addleaf(T, 8); T2 = addleaf(T1, 2); T3 = addleaf(T2, 4); T4 = addleaf(T3, 1); show(T4) :
8
6
4
2
1
Smazani uzlu s hodnotou 8:
T5 = delleaf(T4, 8); show(T5) :
6
4
2
1
Smazani uzlu s hodnotou 2:
T6 = delleaf(T5, 2); show(T6) :
6
4
1
|