Дерево
Пустое дерево.
Операции
Нажмите кнопку обхода, чтобы увидеть последовательность узлов.
Идея BST
Вставка в BST
void Push(Node *&root, int data) {
if (root == 0) {
root = new Node;
root->n = data;
root->left = root->right = 0;
}
else if (data < root->n) Push(root->left, data);
else if (data > root->n) Push(root->right, data);
}Симметричный обход (даёт отсортированную последовательность)
void InOrder(Node *p) {
if (!p) return;
InOrder(p->left);
cout << p->n << " ";
InOrder(p->right);
}Задание
- Вставьте последовательность 50, 30, 70, 20, 40, 60, 80. Какой из обходов даёт отсортированный вывод?
- Вставьте 100, 110, 120 в подряд. Что произошло со структурой дерева?
- Удалите узел с двумя потомками. Какой элемент встанет на его место?
- Реализуйте подсчёт количества листьев в дереве.
- Реализуйте проверку, является ли дерево сбалансированным (AVL-условие).