Эта функция принимает список и корневой узел и формирует binary search tree, каждый раз - разное.
def create_lists(dic, ls, node): #creates left and right lists for a node & updates a dict
ind=ls.index(node.data)
ls1=(ls[:ind]) # can be empty, no index error
ls2=ls[ind+1:] # can be empty, no index error
dic[node]=(ls1, ls2)
return dic
def create_childs (dic, node): #creates left and right childs for a parent & updates a dict
import random
if dic[node][0]:
intL=random.choice(dic[node][0])
node.left=Node(intL)
dic=create_lists(dic, dic[node][0], node.left)
if dic[node][1]:
intR=random.choice(dic[node][1])
node.right=Node(intR)
dic=create_lists(dic, dic[node][1], node.right)
del dic[node]
return dic
def bin_srch_tr(ls, root):
# ls must be sorted in increased order!
print(root)
import random
dic=dict()
dic=create_lists(dic, ls, root)
dic = create_childs(dic, root)
while dic:
dic2=dic.copy()
for node in dic:
print('node' , node.data, dic) # current node & all node objects with left & right lists per node in a dic
dic2 = create_childs(dic2, node)
dic=dic2
return root
ls=[1,2,3,4,5,6,7]
root=Node(4) # root where data is int, left & right are None
print(bin_srch_tr(ls, root))
