В задаче имеем следующие входные данные:
6
-2 0 2
8 4 3
9 0 0
3 6 5
6 0 0
0 0 0
4
6 9 7 8
где первое число количество вершин двоичного дерева поиска, в последующих строках хранятся данные о вершинах. первое число это ключ вершины, второе - номер строки описания левого ребенка, третье - номер строки описания правого ребенка, если левого или правого ребенка нет то номер строки в котором они должны были описаны равен 0. Следующие число - это количество запросов на удаление. Дальше идут ключи - корни поддеревьев, которые нужно удалить.
В выходных данных нужно вывести количество оставшихся вершин в дереве, после выполнения каждого запроса на удаление одного поддерева с заданным ключом. Поддерева с заданным ключом может не существовать.
В этом случае выходные данные будут следующими.
5 4 4 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
struct data
{
int value, left, right;
bool is_delete;
};
vector <data> data_tree;
int nodes = 0;
void input()
{
int size_tree;
in >> size_tree;
if (size != 0)
{
for (int i = 0; i < size_tree; i++)
{
data add;
in >> add.value >> add.left >> add.right;
add.is_delete = false;
data_tree.push_back(add);
}
}
}
void remove(int index, int key)
{
// если узел считается удаленным то не можем двигаться дальше
if (data_tree[index].is_delete == true)return;
// если узел равен нашему ключу то говорим, что он удален и выходим
if (data_tree[index].value == key)
{
data_tree[index].is_delete = true;
return;
}
// двигаемся дальше по дереву
if (data_tree[index].left != 0)remove(data_tree[index].left - 1, key);
if (data_tree[index].right != 0)remove(data_tree[index].right - 1, key);
// считаем количество пройденных узлов
nodes++;
}
void delete_sub_tree()
{
int size_tree, key;
in >> size_tree;
// ввод запросов и удаление поддеревьев
for (int i = 0; i < size_tree; i++)
{
nodes = 0;
in >> key;
remove(0, key);
out << nodes << endl;
}
}
int main()
{
input(); // ввод данных
delete_sub_tree(); // удаление поддеревьев
in.close();
out.close();
}
Бинарное дерево строить не стал так как входные данные и так обладают достаточным и необходимым условием двоичного дерева поиска. (Каждый элемент имеет ссылку на левого и правого ребенка)
Удаление узла делать не стал так как это изменит расположение узлов в векторе, что нарушит структуру дерева, поэтому при удаление просто говориться, что поддерево с узлом удалено (bool is_delete).
Проблема в том, что данный алгоритм не проходит по времени с большим количеством данных. Начиная с 65000 вершин. Не знаю как можно ускорить этот алгоритм. Для того, чтобы найти в дереве узел с заданным ключем нужно обходить дерево начиная с корня (быстрее не придумаешь) O(log(n)). может быть input() замедляет работу программы.