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

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

Восстановить пароль Регистрация
 
lyubortk
0 / 0 / 0
Регистрация: 02.11.2016
Сообщений: 2
02.11.2016, 23:25     Балансировка бинарного дерева #1
Попалась одна на вид простая задача. Код написал, но не проходит 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++ Обход Бинарного дерева

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,416
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     Балансировка бинарного дерева
Ответ Создать тему
Опции темы

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