Изучение языка программирования Python
Структуры данных: деревья. (Учебник §18)
жүктеу/скачать 1,23 Mb. Pdf көрінісі
|
python
| Структуры данных: деревья. (Учебник §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 , содержащую в себе введенное число пользователя с клавиатуры. |