Двоичное дерево (binary tree) — дерево, в котором у каждого узла не больше двух детей: левый и правый. Двоичные деревья лежат в основе деревьев поиска, куч и деревьев выражений. Термины и обходы общего дерева мы разобрали в предыдущей теме; теперь реализуем двоичное дерево и изучим его свойства.
Класс узла и in-order
В узле есть value, left и right; отсутствующий ребёнок равен None. In-order обход: левое поддерево, узел, правое поддерево. Он возможен только для двоичного дерева, а в двоичном дереве поиска выдаст значения по порядку.
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def sample():
return Node(1, Node(2, Node(4), Node(5)), Node(3, None, Node(6)))
def inorder(node):
if node is None:
return []
return inorder(node.left) + [node.value] + inorder(node.right)
print(inorder(sample()))[4, 2, 5, 1, 3, 6]Высота, число узлов, диаметр
Высоту пустого дерева считаем -1: тогда лист даёт 1 + max(-1, -1) = 0. Диаметр — число рёбер в самом длинном пути дерева. Самый длинный путь через узел равен высота левого + высота правого + 2 (при соглашении о высоте -1). Считается за один обход, O(n).
def height(node):
if node is None:
return -1
return 1 + max(height(node.left), height(node.right))
def count(node):
if node is None:
return 0
return 1 + count(node.left) + count(node.right)
def diameter(root):
best = 0