Бинарное дерево поиска (BST)
Начните со случайного бинарного дерева поиска и пошагово вставляйте, ищите или удаляйте значения: с представлением в виде массива и подсветкой кода C++.
Всё моделируется в этом браузере; ничего не отправляется на сервер.
Нет шагов
Нет шагов
Бинарное дерево поиска
Индекс в массиве
Представление в виде массива
Потомки индекса i находятся в 2i+1 и 2i+2.
- Не связан
- Уже пройден
- Сравнивается
- Найден
- Новый
- К удалению
- Преемник
Нет шагов
Код
#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 setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
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;
}
int main() {
Node* root = buildTree(); // Показанное дерево, уже построенное
root = insert(root, v); // Первый вызов, из main
return 0; // Конец операции
}