Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/18: Рейтинг темы: голосов - 18, средняя оценка - 4.83
69 / 69 / 35
Регистрация: 06.07.2016
Сообщений: 415
1

Найти второй максимум бинарного дерева поиска

30.01.2017, 19:49. Показов 3501. Ответов 4
Метки нет (Все метки)

Прошу написать какие-нибудь извращенные входные данные для бинарного дерева поиска. Не проходит 7 тестов, хотя какие только входные данные я не пробовал.
1.Само задание - http://informatics.mccme.ru/mo... erid=759#1
2.Код функции, которая ищет второй максимум -
Кликните здесь для просмотра всего текста
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
int tree::second_max(link root)
{
    if (!root->right && !root->left)
    {
        return root->data;
    }
    if (root->right)
    {
        while (root->right->right) 
        {
            root = root->right;
        }
        return (root->right->left) ? (root->right->left->data) : (root->data);
    }
    else if (!root->left->right)
    {
        return root->left->data;
    }
    else
    {
        root = root->left;
        while (root->right->right)
        {
            root = root->right;
        }
        return root->right->data;
    }
}

3.Если есть какая-то ошибка в функции - не показывайте где, напишите просто тест,где она упадет,хочу найти сам.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.01.2017, 19:49
Ответы с готовыми решениями:

Найти второй максимум в двоичном дереве поиска
Собственно, в задаче не проходит один тест. Условие: Выведите второй по величине элемент в...

Алгоритм бинарного дерева поиска
Здравствуйте! Помогите найти информацию по поводу данного алгоритма, может быть какие-то...

Реализация бинарного дерева поиска
Не выводит значения узлов деревьев, как я понял происходит утечка памяти, но я не пойму, что нужно...

Создание бинарного дерева поиска
Людииииии помогите пож-таааа.....Нужно создать бинарное дерево поиска, считывая элементы из текст...

4
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
30.01.2017, 21:07 2
Notoriously,

1 3 4 2
1
69 / 69 / 35
Регистрация: 06.07.2016
Сообщений: 415
30.01.2017, 21:13  [ТС] 3
Цитата Сообщение от HenryDukart Посмотреть сообщение
1 3 4 2
Так выводит же 3. В 2х разных IDE.
0
125 / 125 / 44
Регистрация: 05.10.2013
Сообщений: 462
30.01.2017, 21:16 4
Лучший ответ Сообщение было отмечено Notoriously как решение

Решение

1 4 2 3

Добавлено через 49 секунд
Notoriously, напишите весь код, чтобы удобней было проверять.
1
69 / 69 / 35
Регистрация: 06.07.2016
Сообщений: 415
30.01.2017, 22:20  [ТС] 5
Цитата Сообщение от HenryDukart Посмотреть сообщение
весь код
Кликните здесь для просмотра всего текста
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
 
struct Node
{
    int data;
    Node *right;
    Node *left;
};
 
typedef Node *link;
 
class tree
{ 
    link root;
public :
    tree() { root = NULL; }
    void printt(link root);
    void insert(link *root, int value);
    bool create_node(link *root, int value);
    link* get_root_reference(){ return &root;}
    link get_root() { return root;}
    int second_max(link root);
    ~tree(){}
};
 
int main()
{
 
    tree binary_tree;
    while (true)
    {
        int value ;
        std::cin >> value;
        if (!value)
        {
            break;
        }
        link* root = binary_tree.get_root_reference();
        binary_tree.insert(root,value);
    }
 
    link root = binary_tree.get_root();
    std::cout << binary_tree.second_max(root) << std :: endl;
 
    system("pause");
    return 0;
}
 
void tree :: printt(link root)
{
    if (root)
    {
        printt(root->left);
        std::cout << root->data << "\t";
        printt(root->right);
    }
}
 
void tree :: insert(link *root, int value)
{
    if (!(*root))
    {
        if (create_node(root, value))
        {
            return;
        }
        else
        {
            exit(1);
        }
    }
    if ((*root)->data > value)
    {
        insert(&((*root)->left), value);
    }
    else if ((*root)->data < value)
    {
        insert(&((*root)->right), value);
    }
}
 
bool tree :: create_node(link *root, int value)
{
    if (!(*root = new Node[1]))
        {
            return false;
        }
    (*root)->data = value;
    (*root)->left = (*root)->right = NULL;
    return true;
}
 
int tree::second_max(link root)
{
    if (!root->right && !root->left)
    {
        return root->data;
    }
    if (root->right)
    {
        while (root->right->right)
        {
            root = root->right;
        }
        return (root->right->left) ? (root->right->left->data) : (root->data);
    }
    else if (!root->left->right)
    {
        return root->left->data;
    }
    else
    {
        root = root->left;
        while (root->right->right)
        {
            root = root->right;
        }
        return root->right->data;
    }
}


Добавлено через 7 минут
Цитата Сообщение от HenryDukart Посмотреть сообщение
1 4 2 3
Спасибо, исправил. Осталось дождаться,пока они поднимут сайт,чтобы снова попытаться сдать.
Идти в право от левого потомка правого максимума мне так и не пришло в голову.

Добавлено через 55 минут
Спасибо, дело было именно в этом.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.01.2017, 22:20

Итератор дерева бинарного поиска
Если у нас в качестве коллекции выступают вектора, очереди, стеки и т.п. то там вроде бы всё...

Реализация бинарного дерева поиска
Задача: Реализация бинарного дерева поиска Компилируется нормально, а при запуске выбивает ошибку...

Распечатка бинарного дерева поиска
Много где висит функция void print(int deep, ptree p) { if(p) { print(deep + 1, p-&gt;l); ...

Итератор для бинарного дерева поиска.
Господа, нужен совет знатоков. Бинарное дерево поиска представлено следующей структурой. ...


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

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

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