Подразделы

Другие разделы

Дата и время

07/01/2026 07:28:12

Авторизация

Структуры данных на основе деревьев

Определения Обходы бинарного дерева Двоичное дерево поиска Система непересекающихся множеств Сбалансированные деревья Декартово дерево Декартово дерево по неявному ключу Дерево отрезков

Обходы бинарного дерева

![width:150px|artree](51471.png)

Прямой (pre-order) обход бинарного дерева:

* Обработать узел
* Обойти левое поддерево
* Обойти правое поддерево

```c++
void preorder(Node* n)
{ if(!n) return;
print(n->value);
preorder(n->left);
preorder(n->right);
}
```

``(+ (* 3 (- 7 4)) 6)`` // используется в функциональных языках (Scheme)

--

Симметричный (in-order) обход бинарного дерева:

* Обойти левое поддерево
* Обработать узел
* Обойти правое поддерево

```c++
void inorder(Node* n)
{ if(!n) return;
inorder(n->left);
print(n->value);
inorder(n->right);
}
```

``((3 * (7 - 4)) + 6)``

--

Обратный (post-order) обход бинарного дерева:

* Обойти левое поддерево
* Обойти правое поддерево
* Обработать узел

```c++
void postorder(Node* n)
{ if(!n) return;
postorder(n->left);
postorder(n->right);
print(n->value);
}
```

``((3 (7 4 -) *) 6 +)``\
``3 7 4 - * 6 +`` // обратная польская (бесскобочная) запись, используется в языке Forth и некоторых калькуляторах

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Структуры данных на основе деревьев

Обходы бинарного дерева