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

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

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

## **Дерево**

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

G = (V, E)

* **Вершина**(узел) - это элемент из множества V
* **Ребро** - это элемент из множества Е .
* **Корень** - узел без "родителя".
* **Лист** - узел без "детей".

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

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

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

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

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

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

<pre class="language-c"><code class="lang-c">struct Node{
<strong>    int data;
</strong>    struct Node *left;
    struct Node *right;
};
</code></pre>

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

1. Добавление узла в дерево
2. Удаление узла из дерева
3. Поиск узла в дереве
4. Обход дерева

&#x20;      4.1. В глубину

&#x20;             4.1.1. Прямой(pre-order)

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

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

&#x20;      4.2. В ширину

5. Другие

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

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

&#x20;      5.3. ...&#x20;

## **Прямой (pre-order)**

<figure><img src="https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FDy9QMFvpdlh42jEFHes7%2Fimage.png?alt=media&#x26;token=bf5e185c-da08-48e3-a6ab-d3c4d4196938" alt=""><figcaption><p>Порядок обхода вершин</p></figcaption></figure>

```c
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)

<figure><img src="https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FAgA7bMgCcVEtZ76uoRjv%2Fimage.png?alt=media&#x26;token=035e5a85-ae84-4148-a2fc-56f795de13b5" alt=""><figcaption><p>Порядок обхода вершин</p></figcaption></figure>

```c
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)

<figure><img src="https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FVV6JoZrIQA6kF1tytQ8U%2Fimage.png?alt=media&#x26;token=560aa0cc-c06e-4999-8575-54760492526c" alt=""><figcaption><p>Порядок обхода вершин</p></figcaption></figure>

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

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

## :rofl:Три стадии опьянения бауманца:&#x20;

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

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

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

*<mark style="color:orange;">Анекдот не в изначальной формулировке К. Л. Тассова. Он отредактирован для правильного запоминания обхода дерева.</mark>*