Дерево — нелинейная структура для иерархических данных: файловая система, DOM HTML-документа, оргструктура, дерево выражений. Дерево обобщает связный список: у узла не один next, а несколько детей. Циклов нет, а у каждого узла (кроме корня) ровно один родитель.
Термины
| Термин | Смысл |
|---|---|
| Корень (root) | единственный узел без родителя |
| Лист (leaf) | узел без детей |
| Родитель / ребёнок / сиблинг | непосредственно выше / ниже / другие дети того же родителя |
| Предок / потомок | узлы выше / ниже по пути |
| Глубина (depth) | число рёбер от корня до узла (у корня 0) |
| Высота (height) | число рёбер от узла до самого глубокого листа (у листа 0) |
| Уровень (level) | узлы одной глубины |
| Поддерево | узел и все его потомки |
| Степень (degree) | число детей узла |
Высота дерева — это высота корня. В дереве из n узлов n - 1 ребро.
Класс узла
class TreeNode:
def __init__(self, value, children=None):
self.value = value
self.children = children or []
def sample():
return TreeNode("A", [
TreeNode("B", [TreeNode("E"), TreeNode("F")]),
TreeNode("C"),
TreeNode("D", [TreeNode("G")]),
])
def height(node):
return 1 + max((height(c) for c in node.children), default=-1)
def size(node):
return 1 + sum(size(c) for c in node.children)