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

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

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

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

02.11.2016, 23:25. Просмотров 424. Ответов 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++
Как сделать балансировку бинарного дерева поиска? template &lt;class T, class I&gt; class node { private: T x; //ключ I...

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

Написать шаблон бинарного дерева с функцией распечатки дерева - C++
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного дерева с функцией распечатки дерева *(+(d,e),c) в виде...

Создание бинарного дерева из бинарного файла - C++
struct Bin { string name; string city; int players; int score; }; void ReadFromBin(Point*&amp; Tree) { Bin q;

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MrGluck
Модератор
Эксперт CЭксперт С++
7210 / 4376 / 638
Регистрация: 29.11.2010
Сообщений: 11,887
03.11.2016, 11:26 #2
Если нужно бинарное дерево с автоматической балансировкой - посмотрите на реализацию АВЛ дерева или К/Ч дерева.
lyubortk
0 / 0 / 0
Регистрация: 02.11.2016
Сообщений: 2
05.11.2016, 05:14  [ТС] #3
В этой задаче вообще не идет речи о дереве поиска. Тут у вершин даже значений нет.
Нужно просто "отрезать" некоторые поддеревья. Кажется, что очень легко, но определенная группа тестов не проходит.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2016, 05:14
Привет! Вот еще темы с ответами:

Обход бинарного дерева - C++
может есть у кого такой пример или похожий??или часть какая нибудь?

Создание бинарного дерева - C++
Есть задания и я знаю как их сделать, но не понимаю, как создать и вывести на экран бинарное дерево. Подскажите пожалуйста, ссылки, коды,...

Обход бинарного дерева С++ - C++
Нужна помощь! Просмотрел много источников, но так и не нашёл своего ответа...Суть задачи состоит в том что, мне нужно при обходе...

Глубина бинарного дерева - C++
На одном сайте, вроде как сурьезном читаю про деревья. столкнулся вот с таким примером вычисления глубины дерева // Эта функция...


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

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

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