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

Перемещение элементов массива на бинарное дерево

06.06.2018, 17:06. Показов 2240. Ответов 8
Метки нет (Все метки)

Добрый день. Помогите пожалуйста, стоит задача сформировать минимальное пирамидальное дерево для поиска на нем определенного элемента (уровня на котором он находится в дереве и позиции на этом уровне). Алгоритм стоит следующий:
1. Сформировать последовательность случайных чисел (без повторений);
2. Занести их в массив;
3. Массив отсортировать по возрастанию (дабы легче было переносить его на дерево и не пришлось сортировать само дерево);
4. Упорядоченный массив перенести на дерево по принципу (в корне стоит a[0] - минимальный элемент, потомки корня - левый a[1], правый a[2], потомки потомков корня слево-направо т.е. a[3] a[4] и тд.
5. Пользователь вводит число и программа ищет это число в дереве, если оно есть то программы пишет уровень и позицию где находится число.
Так вот, с первыми тремя пунктами проблем нет, а вот дальше я не понимаю как записать в виде программы вишесказанное. Пользоваться контейнерами мне запрещено. Буду благодарен за любую помощь. Заранее спасибо.
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
#include<iostream>
using namespace std;
 
//структура узла дерева
struct Node
{
    int value;
    Node* left;
    Node* right;
};
 
//создание массива случайных (неповторяющихся) целых чисел
void create_array(int*& a, int size)
{
    a = new int [size];
    for(int i = 0; i < size; i++)
    {
        a[i] = i + 1;
    }
    for(int i = 0; i < size - 1; i++)
    {
        swap(a[i], a[rand() % size]);
    }
}
 
//вывод массива
void print_array(int *a, int size)
{
    cout << "\nМассив: ";
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
 
//сортировка массива методом выбора
 
void sort_array(int* a, int size)
{
    int min_tmp;
    for(int i = 0; i < size - 1; i++)
    {
        min_tmp = i;
        for(int j = i + 1; j < size; j++)
        {
            if(a[j] < a[min_tmp]) {min_tmp = j;}
        }
        swap(a[i], a[min_tmp]);
    }
}
void main()
{
    setlocale(LC_ALL, "rus");
    int n = 58;
    int *arr;
    create_array(arr, n);
    print_array(arr, n);
    sort_array(arr, n);
    print_array(arr, n);
    system("pause");
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.06.2018, 17:06
Ответы с готовыми решениями:

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при...

Преобразовать идеальное бинарное дерево в бинарное дерево поиска
Всем привет, я создал идельное бинарное дерево и написал к нему функции. Как мне теперь можно...

Бинарное дерево на основе массива
Всем привет. Начал изучать бинарное дерево на основе массива, нужна подсказка, я правильно начал...

Бинарное дерево из элементов файла
Можете пожалуйста помочь. Есть бинарное дерево, надо его формировать из элементов файла (чисел). В...

8
7158 / 6133 / 2801
Регистрация: 14.04.2014
Сообщений: 26,455
06.06.2018, 17:10 2
Через контейнер делай.
0
0 / 0 / 2
Регистрация: 11.10.2016
Сообщений: 116
06.06.2018, 17:12  [ТС] 3
nmcf, я не умею ними пользоваться
0
7158 / 6133 / 2801
Регистрация: 14.04.2014
Сообщений: 26,455
06.06.2018, 19:08 4
C++
1
2
3
4
5
6
7
struct Node
{
    int value;
    Node* left;
    Node* right;
    Node(int v): value(v), left(nullptr), right(nullptr) {}
};
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
std::vector<Node *> a;
int i = 1;
Node *root = new Node(arr[0]);
a.push_back(root);
while (i < n)
{
    for (int j = 0; j < a.size(); j += 2)
    {
        Node *c = a[j];
        a.erase(a.begin() + j);
        a.insert(a.begin() + j, new Node(arr[i++]));
        c->left = a[j];
        if (i == n) break;
        a.insert(a.begin() + j + 1, new Node(arr[i++]));
        c->right = a[j + 1];
    }
}
a.clear();
0
0 / 0 / 2
Регистрация: 11.10.2016
Сообщений: 116
06.06.2018, 20:21  [ТС] 5
nmcf, а как потом делать поиск в таком дереве?
0
7158 / 6133 / 2801
Регистрация: 14.04.2014
Сообщений: 26,455
06.06.2018, 20:42 6
В каком таком? Дерево обычное. Рекурсия.
0
0 / 0 / 2
Регистрация: 11.10.2016
Сообщений: 116
06.06.2018, 20:55  [ТС] 7
nmcf, просто дерево создано из контейнера, я даже не понимаю как к нему обращатся, не то что там что-то искать
0
7158 / 6133 / 2801
Регистрация: 14.04.2014
Сообщений: 26,455
06.06.2018, 21:01 8
Да какая разница как оно создано? Есть корень - root, дальше как обычно.
0
0 / 0 / 2
Регистрация: 11.10.2016
Сообщений: 116
06.06.2018, 21:05  [ТС] 9
nmcf, помогите пожалуйста, я понятия не имею как искать значение (с точным указанием уровня на котором стоит и позиции) в дереве.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.06.2018, 21:05

Бинарное дерево: удаление элементов
Помогите пожалуйста реализовать удаление элементов бинарного дерево, добавление и вывод вроде...

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

Бинарное дерево с использованием статического массива
Помогите пожалуйста с программой. Мне дали вот такое задание: Cпроектировать структуру типа...

Бинарное дерево и поиск элементов в нем
Пытаюсь написать класс для поиска элементов в бинарном дереве. Написал, но у меня не работает...

Бинарное дерево поиска (Количество элементов)
Здравствуйте все. Помогите пожалуйста разобраться с 2 ошибками. 1) Иногда добавляются числа не в...

Запись одинаковых элементов в бинарное дерево
помогите исправить ошибку в программе при записи двувух или более студентов на одну и туже первую...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru