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

дерева в глубину (pre-order, in-order, post-order). Реализация. Примеры.

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

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

Дерево

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

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. ...

Прямой (pre-order)

Порядок обхода вершин

void pre_order(struct Node*){
    if (node == NULL){
        return;
    } 
    //посещение
    printf("%d", node->data); //1
    pre_order(node->left); //2
    pre_order(node->right); //3
}

От корневого узла в левое дерево, потом в правое дерево.

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

Порядок обхода вершин

void in_order(struct Node*){
    if (node == NULL){
        return;
    } 
    //посещение
    in_order(node->left); //2
    printf("%d", node->data); //1
    in_order(node->right); //3
}

Обойти левое дерево, корневой узел, правое дерево

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

Порядок обхода вершин

void post_order(struct Node*){
    if (node == NULL){
        return;
    } 
    //посещение
    post_order(node->left); //2
    post_order(node->right); //3
    printf("%d", node->data); //1
}

Сначала левое, потом правое, в конце - корневой узел.

🤣Три стадии опьянения бауманца:

1. Достал(корень 1), поссал(левое 2), забыл стряхнуть(правое 3). pre-order

2. Поссал(левое 2), достал(корень 1), забыл стряхнуть(правое 3). in-order

3. Поссал(левое 2), стряхнул (правое 3), забыл достать (корень 1). post-order

Анекдот не в изначальной формулировке К. Л. Тассова. Он отредактирован для правильного запоминания обхода дерева.