Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
0 / 0 / 0
Регистрация: 02.11.2016
Сообщений: 2
1

Балансировка бинарного дерева

02.11.2016, 23:25. Просмотров 1853. Ответов 2
Метки нет (Все метки)

Попалась одна на вид простая задача. Код написал, но не проходит 10 тестов из 40.

Кликните здесь для просмотра всего текста
Лидеру команды "Отбой" на День Рождения подарили подвешенное бинарное дерево. Однако, ему не понравилось, что дерево было несбалансировано. Теперь он хочет удалить минимальное количество вершин в дереве, чтобы оно стало сбалансированным. Перед тем, как удалить вершину из дерева, он обязан удалить все вершины из её поддерева.

Напомним, что дерево является сбалансированным тогда и только тогда, когда высота его левого и правого поддеревьев отличается не более чем на 1 (высота пустого равна нулю, а высота дерева из одной вершины - единице). Корнем дерева является вершина 1.

Входные данные

В первой строке входного файла задано целое число n - количество вершин в дереве (1 ≤ n≤ 1111). В следующих n строках заданы по два целых числа left(i) и right(i) - номера левого и правого ребёнка вершины соответственно, или 0, если этого ребёнка не существует.

Выходные данные

В единственной строке выходного файла выведите одно число - искомое минимальное количество удаляемых вершин.
тестирующая система - https://www.e-olymp.com/ru/problems/4150


Мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
#include <list>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    vector<pair<int, int>> arr(n);
 
    int i;
    for (i = 0; i < n; ++i)
    {
        cin >> arr[i].first;
        cin >> arr[i].second;
    }
 
 
    list<int> L;
    list<int>& left = L;
    if (arr[0].first != 0) left.push_back(arr[0].first); //левое поддерево
 
    list<int> R;
    list<int>& right = R;
    if (arr[0].second != 0) right.push_back(arr[0].second); //правое поддерево
 
    int nodes = 1 + left.size() + right.size();
 
    list<int> temp;
    while (left.size() != 0 && right.size() != 0)
    {
        for (auto v : left)
        {
            if (arr[v - 1].first != 0)
            {
                temp.push_back(arr[v - 1].first);
                ++nodes;
            }
            if (arr[v - 1].second != 0)
            {
                temp.push_back(arr[v - 1].second);
                ++nodes;
            }
        }
        left = temp;
        temp.resize(0);
 
        for (auto v : right)
        {
            if (arr[v - 1].first != 0)
            {
                temp.push_back(arr[v - 1].first);
                ++nodes;
            }
            if (arr[v - 1].second != 0)
            {
                temp.push_back(arr[v - 1].second);
                ++nodes;
            }
        }
        right = temp;
        temp.resize(0);
 
 
    }
 
    cout << n - nodes;
    return 0;
}
Прошу помощи с задачей. Спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.11.2016, 23:25
Ответы с готовыми решениями:

Балансировка дерева
Как сделать балансировку бинарного дерева поиска? template &lt;class T, class I&gt; class node {...

Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя - 1 указатель на...

Написать шаблон бинарного дерева с функцией распечатки дерева
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного дерева с функцией...

Построение бинарного дерева на основе не бинарного
В лабораторной работе есть такое задание: Создайте процедуру построения бинарного дерева на основе...

2
Форумчанин
Эксперт CЭксперт С++
8157 / 5005 / 1436
Регистрация: 29.11.2010
Сообщений: 13,458
03.11.2016, 11:26 2
Если нужно бинарное дерево с автоматической балансировкой - посмотрите на реализацию АВЛ дерева или К/Ч дерева.
0
0 / 0 / 0
Регистрация: 02.11.2016
Сообщений: 2
05.11.2016, 05:14  [ТС] 3
В этой задаче вообще не идет речи о дереве поиска. Тут у вершин даже значений нет.
Нужно просто "отрезать" некоторые поддеревья. Кажется, что очень легко, но определенная группа тестов не проходит.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.11.2016, 05:14

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Создание бинарного дерева из бинарного файла
struct Bin { string name; string city; int players; int score; }; void...

Вывод бинарного дерева на экран в виде "дерева"
основная задача: подсчет количества листьев. проблема: при просмотре хочу выводить бин. дерево, в...

Создание бинарного дерева
Есть задания и я знаю как их сделать, но не понимаю, как создать и вывести на экран бинарное...

Реализация бинарного дерева
Доброго времени суток, уважаемые форумчане. Возник вопрос по реализации бинарного дерева на С++, а...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.