Z5-Rešenja
Functions
# file: 'functions.py'
def inorder_tree_walk(x):
if x != None:
inorder_tree_walk(x.left)
print(x.data.a2)
inorder_tree_walk(x.right)
def tree_search(x, k):
if x == None or x.data.a1 == k:
return x
if k < x.data.a1:
return tree_search(x.left, k)
else:
return tree_search(x.right, k)
def tree_minimum(x):
while x.left != None:
x = x.left
return x
def tree_maximum(x):
while x.right != None:
x = x.right
return x
def tree_successor(x):
if x.right != None:
return tree_minimum(x.right)
y = x.p
while y != None and x == y.right:
x = y
y = y.p
return y
def tree_insert(T, z):
y = None
x = T
while x != None:
y = x
if z.data.a1 < x.data.a1:
x = x.left
else:
x = x.right
z.p = y
if y == None:
T = z
elif z.data.a1 < y.data.a1:
y.left = z
else:
y.right = z
return T
def tree_delete(T, z):
if z.left == None:
transplant(T, z, z.right)
elif z.right == None:
transplant(T, z, z.left)
else:
y = tree_minimum(z.right)
if y.p != z:
transplant(tree_delete, y, y.right)
y.right = z.right
y.right.p = y
transplant(T, z, y)
y.left = z.left
y.left.p = y
def transplant(T, u, v):
if u.p == None:
T = v
elif u == u.p.left:
u.p.left = v
else:
u.p.right = v
if v != None:
v.p = u.p
def inorder_tree_walk_list(x, l):
if x != None:
inorder_tree_walk_list(x.left, l)
l.append(x.data)
inorder_tree_walk_list(x.right, l)
functions.py
Node
# file: 'node.py'
class Node:
"""
Tree node: left child, right child and data
"""
def __init__(self, d = None, l = None, r = None):
"""
Node constructor
@param A node data object
"""
self.left = l
self.right = r
self.data = d
class Data:
"""
Tree data: Any object which is used as a tree node data
"""
def __init__(self, val1, val2):
"""
Data constructor
@param A list of values assigned to object's attributes
"""
self.a1 = val1
self.a2 = val2
node.py
Tree
# file: 'tree.py'
from functions import *
class Tree(object):
def __init__(self, r = None):
self.root = r
def inorder_tree_walk(self):
return inorder_tree_walk(self.root)
def tree_search(self, k):
return tree_search(self.root, k)
def tree_minimum(self):
return tree_minimum(self.root)
def tree_maximum(self):
return tree_maximum(self.root)
def tree_successor(self, x):
return tree_successor(x)
def tree_insert(self, z):
self.root = tree_insert(self.root, z)
def tree_delete(self, z):
return tree_delete(self.root, z)
def transplant(self, u, v):
transplant(self.root, u, v)
def inorder_tree_walk_list(self, l):
inorder_tree_walk_list(self.root, l)
tree.py
Zadatak 1
# file: 'z5-1.py'
import sys
from node import Data, Node
from tree import Tree
import random
def random_list(min, max, elements):
list = random.sample(range(min, max), elements)
return list
if __name__ == "__main__":
L = random_list(0, 10, 10)
print(L)
T = Tree()
for i in L:
d = Data(i, str(i))
z = Node(d)
T.tree_insert(z)
print("\n--- inorder_tree_walk TEST ---")
T.inorder_tree_walk()
print("\n--- tree_search TEST ---")
k = 8
x = T.tree_search(k)
print("Element" , k, "found" if x != None else "not found")
k = 12
x = T.tree_search(k)
print("Element" , k, "found" if x != None else "not found")
print("\n-- tree_successor TEST ---")
k = 2
x = T.tree_search(k)
y = T.tree_successor(x)
print("Successor(", x.data.a2, ") = ", y.data.a2)
print("\n--- tree_minimum, tree_maximum TEST ---")
min = T.tree_minimum()
max = T.tree_maximum()
print("min: ", min.data.a2, " max: ", max.data.a2)
print ("\n--- delete(2) TEST ---")
x = T.tree_search(2)
T.tree_delete(x)
T.inorder_tree_walk()
print("\n--- inorder_tree_walk_list TEST ---")
l = []
T.inorder_tree_walk_list(l)
print([x.a1 for x in l])