Лабораторная работа 16, Деревья в Python

Дерево (tree) — одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов.

Является связным графом, не содержащим циклы.

Идеально подходит для представления иерархической структуры.

Структура дерева

1.   Деревья состоят из узлов (nodes), которые имеют 0 или более прямых потомков (children) или узлов-потомков (child nodes). 

2.   Узел называется родителем (parent) для своих потомков. 

3.   Каждый узел имеет (не более) одного родителя. 

4.   Если родители упорядочены некоторым образом, то мы получаем 

упорядоченное дерево (ordered tree). 

5.   Деревья с корнями (rooted trees), т. е. имеющие один особый узел, называемый корнем (root) дерева. 

6.   Корень – это единственный узел, который не имеет родителя.

7.   Узлы, не имеющие ни одного потомка, называются листьями (leaves) или узлами-листьями (leaf nodes).

ТЕРМИНОЛОГИЯ

1.  Путь (path) в дереве – это последовательность узлов, в которой каждый узел является потомком предыдущего. 

2.   Путь из x в y существует , если первым узлом (в последовательности) является x, а последним – y. 

3.   Всегда существует путь из корня в каждый узел дерева. 

4.  Длина пути (length of the path) – это число переходов или ребер (edges), которое на единицу меньше числа узлов в конкретном пути. 

5.   Все потомки (descendants) узла x – это все узлы y, для которых существует путь из x в y. 

6.   Если y – потомок x, то x является предком (ancestor) y. 

7.   Если задано дерево T и узел n в нем, то поддерево с корнем n (subtree rooted at n) – это дерево, корнем которого является узел n, и оно содержит всех потомков узла n. 

8.  Глубина (depth) узла – это длина пути к этому узлу из корня. 

9.  Высота (height) дерева – максимальная глубина любого узла в дереве. 

Операции с деревьями:

1. Поиск — нахождение узла в дереве.
2. Вставка — добавление нового узла.
3. Удаление — удаление узла и перераспределение его дочерних узлов.
4. Обходы дерева:
   • Прямой (Pre-order): корень → левое поддерево → правое поддерево.
   • Симметричный (In-order): левое поддерево → корень → правое поддерево.
   • Обратный (Post-order): левое поддерево → правое поддерево → корень.
   • По уровням (Level-order): узлы обрабатываются по уровням от корня.

Задания 

1. Реализация дерева с произвольным числом потомков. Реализуйте класс для дерева. Добавьте методы:

• Вставка дочернего узла.
• Поиск узла по значению.
• Удаление узла.

3. Подсчет узлов дерева. Напишите функцию, которая считает количество узлов в дереве.

4. Определение высоты дерева. Реализуйте функцию, которая возвращает высоту дерева — максимальную длину пути от корня до листа.

5. Проверить присутствие элемента в наборе данных