🌲29. Динамические структуры данных. Деревья. Корень, лист, высота вершины, глубина дерева. Бинарное..

дерево и бинарное дерево поиска. Алгоритмы их обработки.

Динамическая структура данных

• Это структуры данных, память под которые выделяется и освобождается по мере необходимости. Примером таких структур можно считать деревья, списки, очередь, стек.

Дерево

Дерево - связанный ациклический граф.

G = (V, E)

• Вершина(узел) - это элемент из множества V

• Ребро - это элемент из множества Е .

• Корень - узел без "родителя".

• Лист - узел без "детей".

Высота узла - длина самого длинного пути из этого узла до какого-либо листа.

Высота дерева - высота корневого элемента.

Глубина(уровень) вершины - длина пути до корневого узла.

Глубина(уровень) дерева - длина самого длинного пути от какого-то листа до корня.

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

• Дерево, в котором у каждого узла существует не более 2 детей.

struct Node{
    int data;
    struct Node *left;
    struct Node *right;
};

Бинарное дерево поиска

• Это бинарное дерево, у которого левый элемент всегда меньше родителя, а правый - всегда больше.

Операции над деревом

1. Добавление узла в дерево

2. Удаление узла из дерева

3. Поиск узла в дереве

4. Обход дерева

4.1. В глубину

4.1.1. Прямой(pre-order)

4.1.2. Симметричный/поперечный(in-order)

4.1.3. В обратном порядке(post-order)

4.2. В ширину

5. Другие

5.1. Получить всех "братьев" узла.

5.2. Получить "родителя" узла.

5.3. ...