Структуры данных: деревья. (Учебник §18)
Для определения двоичного дерева потребуется класс –
TreeItem
, в
конструкторе которого будут определяться ссылки на корневой элемент, а
также на его левую и правую ветвь.
class TreeItem:
def __init__(self, data = None):
self.right = None
self.left = None
self.data = data
Определим корневой узел дерева со значением 200 с первым
разветвлением на узлы 50 и 250:
#Корневой элемент
root = TreeItem(200)
#Список, содержащий начальные левый и правый узлы дерева
tree = [TreeItem(50), TreeItem(250)]
root.left = tree[0]
root.right = tree[1]
22
1.
Вставка элемента в дерево:
curItem = root
#Поиск нужного места и вставка нового элемента
while not curItem == None and not curItem.data == inp and not
curItem.data == None:
if curItem.data > inp:
if curItem.left == None or curItem.left.data == None:
tree.append(TreeItem(inp))
curItem.left = tree[-1]
break
else:
#Переход влево
curItem = curItem.left
elif curItem.right == None:
curItem.right = tree[-1]
break
else:
if curItem.right == None or curItem.right.data == None:
tree.append(TreeItem(inp))
curItem.right = tree[-1]
break
else:
#Переход вправо
curItem = curItem.right
2.
Поиск элемента в дереве:
curItem = root
while not curItem == None and not curItem.data == inp and not
curItem.data == None:
prev=curItem
if curItem.data > inp:
curItem = curItem.left
else:
curItem = curItem.right
if curItem == None or curItem.data == None:
print("Такого элемента нет")
Замечание:
Перед тем, как использовать вышеприведенный программные коды,
не забудьте создать переменную
inp
, содержащую в себе введенное число
пользователя с клавиатуры.
|