Программа Python для реализации структуры данных двоичного дерева
Дерево — это структура данных, состоящая из узлов. Узлы соединены ребрами. Самый верхний узел называется корнем, а самый нижний узел называется листьями. Листья — это узлы, у которых нет дочерних элементов.
Двоичное дерево
Бинарное дерево — это дерево, в котором каждый узел может состоять максимум из двух дочерних элементов. Это означает, что каждый узел может иметь либо 0, либо 1, либо 2 дочерних узла, но не более того. Каждый узел в двоичном дереве состоит из трех полей:
Данные
Указатель на левого дочернего элемента
Указатель на нужного дочернего элемента
Полное двоичное дерево. Бинарное дерево называется полным двоичным деревом, если все уровни полностью заполнены, кроме последнего уровня, и все узлы должны быть как можно левее.
Строгое/правильное двоичное дерево. Бинарное дерево называется строгим или правильным двоичным деревом, если каждый узел имеет ноль или два дочерних элемента.
Идеальное двоичное дерево. Бинарное дерево называется идеальным двоичным деревом, если все узлы имеют по два дочерних узла и все конечные узлы находятся на одном уровне.
Сбалансированное двоичное дерево. Бинарное дерево называется сбалансированным, если разница между высотой левого поддерева и высотой правого поддерева не превышает одного (0 или 1).
Построение двоичного дерева из заданного массива
Пример
Если корневой узел присутствует в i-м индексе, то левый дочерний узел будет присутствовать в (2*i+1)-м индексе, а правый дочерний узел будет присутствовать в (2*i-1)-м индексе. Мы будем использовать эту концепцию для построения двоичного дерева из элементов массива.
class TreeNode:
def __init__(self,data,left=None,right=None):
self.data=data
self.left=left
self.right=right
def insert_into_tree(root,arr,i,l):
if i<l:
print(arr[i])
temp=TreeNode(arr[i])
root=temp
root.left=insert_into_tree(root,arr,i*2+1,l)
root.right=insert_into_tree(root,arr,i*2+2,l)
return root
arr=[1,2,3,4,5]
i=0
l=len(arr)
root=TreeNode(arr[0])
insert_into_tree(root,arr,i,l)
Выход
1
2
4
5
3