Обходы бинарного дерева
Сгенерируйте бинарное дерево поиска и пройдите по шагам прямой, симметричный или обратный обход с помощью рекурсивной функции C++.
Всё моделируется в этом браузере; ничего не отправляется на сервер.
Посещает узел, затем левое поддерево, затем правое.
Функция вызывается с узлом 60
Функция вызывается с узлом 60
Бинарное дерево
Вывод
Ни один узел ещё не посещён
- Не посещён
- Выполняется
- В стеке
- Посещён
Шаг 1 / 44
Код
#include <iostream>
using namespace std;
class Node { // Узел хранит значение и указатели на двух потомков
private: // Приватные атрибуты: к ним обращаются только методы
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
void preorder(Node* node) { // Обходит поддерево с корнем node
if (node == nullptr) return; // Базовый случай: в пустом поддереве нечего посещать
cout << node->getValue() << " "; // Посещает узел: обрабатывает его значение
preorder(node->getLeft()); // Обходит левое поддерево
preorder(node->getRight()); // Обходит правое поддерево
} // Возвращается к вызывающему коду
Node* insert(Node* root, int v) { // Вставляет v в дерево поиска и возвращает корень
if (root == nullptr) return new Node(v); // Пустое место: новый узел помещается сюда
if (v < root->getValue()) // Меньшие значения идут влево, большие — вправо
root->setLeft(insert(root->getLeft(), v));
else
root->setRight(insert(root->getRight(), v));
return root;
}
Node* buildTree() { // Строит дерево, вставляя значения по одному
int values[] = {60, 45, 85, 68, 21, 55, 32}; // Значения показанного дерева в порядке вставки
Node* root = nullptr;
for (int v : values) root = insert(root, v);
return root;
}
int main() {
Node* root = buildTree(); // Дерево из анимации, уже построенное
preorder(root); // Первый вызов, из main
cout << endl; // Конец обхода
return 0;
}