Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
lyubortk
0 / 0 / 0
Регистрация: 02.11.2016
Сообщений: 2
#1

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

02.11.2016, 23:25. Просмотров 194. Ответов 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;
}
Прошу помощи с задачей. Спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.11.2016, 23:25     Балансировка бинарного дерева
Посмотрите здесь:

Построение бинарного дерева C++
C++ Вывод бинарного дерева
Построение бинарного дерева C++
C++ Обход бинарного дерева
Создание бинарного дерева C++
C++ Высота бинарного дерева
C++ Запись бинарного дерева
C++ Балансировка дерева
C++ Реализация бинарного дерева С++
Глубина бинарного дерева C++
Удаление из бинарного дерева C++
C++ Обход Бинарного дерева

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт CЭксперт С++
 Аватар для MrGluck
6228 / 3473 / 425
Регистрация: 29.11.2010
Сообщений: 9,179
03.11.2016, 11:26     Балансировка бинарного дерева #2
Если нужно бинарное дерево с автоматической балансировкой - посмотрите на реализацию АВЛ дерева или К/Ч дерева.
lyubortk
0 / 0 / 0
Регистрация: 02.11.2016
Сообщений: 2
05.11.2016, 05:14  [ТС]     Балансировка бинарного дерева #3
В этой задаче вообще не идет речи о дереве поиска. Тут у вершин даже значений нет.
Нужно просто "отрезать" некоторые поддеревья. Кажется, что очень легко, но определенная группа тестов не проходит.
Yandex
Объявления
05.11.2016, 05:14     Балансировка бинарного дерева
Ответ Создать тему
Опции темы

Текущее время: 01:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru