Информатика • 11 класс

Реализация деревьев. Бинарные деревья (Python)

Дерево – это структура данных, где элементы (узлы) связаны отношениями «родитель-потомок».
Бинарное дерево – частный случай дерева, где каждый узел имеет не более двух потомков.
Обозначения ниже в таблице: Node – узел общего дерева, BinaryNode – узел бинарного дерева, data – данные узла, children – список потомков, left – левый потомок, right – правый потомок, r – корень дерева, a, b – временные узлы.

Аспект	Общее дерево	Бинарное дерево
Структура узла	class Node: def __init__ (self, data): self.data = data # данные узла self.children = [] # список потомков	class BinaryNode: def __init__(self, data): self.data = data self.left = None # левый потомок self.right = None # правый потомок
Потомки	Любое количество	Только 0, 1 или 2
Создание узлов	r = Node (1) a = Node (2) b = Node (3) r.children.append (a) r.children.append (b)	r = BinaryNode (1) a = BinaryNode (2) b = BinaryNode (3) r.left = a r.right = b

Аспект

Общее дерево

Бинарное дерево

Структура узла

class Node:

def __init__ (self, data):

self.data = data
# данные узла

self.children = []
# список потомков

class BinaryNode:

def __init__(self, data):

self.data = data

self.left = None
# левый потомок

self.right = None
# правый потомок

Потомки

Любое количество

Только 0, 1 или 2

Создание узлов

r = Node (1)

a = Node (2)

b = Node (3)

r.children.append (a)

r.children.append (b)

r = BinaryNode (1)

a = BinaryNode (2)

b = BinaryNode (3)

r.left = a

r.right = b

Было полезно?