> For the complete documentation index, see [llms.txt](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/28.-dinamicheskie-struktury-dannykh.-derevya.-koren-list-vysota-vershiny-glubina-dereva.-obkhod-....md).

# 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="/files/hPhVSvAkVQQmbACQLdcv" 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="/files/7TX8cW8khmdnDFbW02ta" 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="/files/0fQPzHdGJOqkn64N5dln" 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>*


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://op-al.gitbook.io/s-30-voprosy-i-dop.-voprosy/28.-dinamicheskie-struktury-dannykh.-derevya.-koren-list-vysota-vershiny-glubina-dereva.-obkhod-....md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.