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

Построение бинарного дерева из двумерного массива - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Построения графика на С http://www.cyberforum.ru/cpp-beginners/thread36316.html
Помогите очень нужно создать прогу yf C построения графика функции.Чтоб вводить любую ф-цию и строился ее график.Типа елементарние sin,cos,квадратична и т.п. Добавлено через 2 часа 49 минут 26 секунд ну врахувать крок, поч. и кон. значения....
C++ Люди помогите с Оборотной матрицей Вот написал , а не пашет. #include<stdio.h> #include<math.h> #include<conio.h> float a,x,e,c,d; int i,j,k,n,h; main() { m2: Printf("\n vvedit n \n"); scanf("\n %d",&n); http://www.cyberforum.ru/cpp-beginners/thread36315.html
Задача на файловые функции C++
Собственно задача вот в чем: Дан файл вещественных чисел с именем Name1. Создать два новых файла с именами Name2 и Name3, первый из которых будет содержатьэлементы исходного файла с четными номерами(0,2,4...), а второй - с нечетными (1,3,5...) Я написал приблизительно код, но где-то в алгоритме похоже ошибка, помогите пожалуйста.. #include <stdio.h> #include <stdlib.h> #include <conio.h>...
Dev C C++
как и где тут использовать "malloc" ??? #include <stdio.h> int main () { int n, a, i; scanf ("%d", &n);
C++ Структура в MVSC++ http://www.cyberforum.ru/cpp-beginners/thread36279.html
прога с помощью структуры . Надо создать программу которая выводит инфу на экран о жителях заданного дома на заданной улице. В проге должны быть имя , фамилия , отчество,( жильца) номер дома, номер квартиры и название улицы. Поиск осуществляется по номеру дома и названию улицы.если данные введены не верно то должно выводить сообщение о ошибке.
C++ Зачем нужен массив указателей на функцию и как его использовать? народ подскажите пожалуйста, зачем нужен массив указателей на функцию и как его использовать. подробнее

Показать сообщение отдельно
Deiron
25 / 25 / 1
Регистрация: 25.05.2009
Сообщений: 98

Построение бинарного дерева из двумерного массива - C++

26.05.2009, 17:02. Просмотров 8096. Ответов 25
Метки (Все метки)

Стыдно, если честно, об этом просить, но "возник стопор" и путных идей не приходит.
Суть задачи:
Есть массив n*n состоящий из целых чисел. Надо создать бинарное дерево по следующему принципу:
значение индексного поля корня - всегда равно 0.
В 0 ряде выбирается два минимальных элемента (за исключением 0;0), меньший из которых становится левым (одно поле структуры будет равно номеру строки, второе самому элементу), другой правым.
Смотрим строку с номером, соответствующим номеру того столбца, в котором находился наш элемент (то есть, если в качестве левого мы взяли элемент массива, находившийся в столбце 3, то мы будем просматривать 3 строку). Там снова выбираем два минимальных элемента. Исключением будет элемент 3;0.
Далее, надо заполнять каждую из ветвей до тех пор, пока в поиске минимумов не останется только один элемент (столбцы, номера которых мы уже прошли из поиска минимумов исключаются), который становится листом.

Если говорить на примере, то из такой таблицы:
- 1 9 2
8 - 2 2
7 9 - 6
5 3 4 -

должно получиться следующее дерево (приведены значения индексных полей):
0
/ \
1 3
/ \ / \
2 3 2 1
| | | |
3 2 1 2
Нумерация строк и столбцов здесь естественно СИшная.
Буду очень благодарен, если поможете с этим делом.
Если кому-либо интересно, зачем мне это - сообщаю: для решения задачи коммивояжера "жадным" алгоритмом. Но в этой модификации алгоритма выбирается не один самый близкий город, а два наиболее близких.

Добавлено через 18 часов 27 минут 53 секунды
Как-то криво я задачу сформировал ((. Попробую по другому:
есть n городов. Стоимость перемещения из города в город - известна, причем стоимость перемещения из a в b может отличаться от стоимости перемещения из b в a. Нужно пройти все города и вернуться в 1й. Алгоритм нахождения минимального пути следующий:
ищем 2 города, путь до которых из данного города имеет минимальную стоимость.
Продолжаем искать такие города до тех пор, пока не будет сформирован путь по всем городам. (например, 1-2-3-4-5-1 или 1-3-5-2-6-4-1) В конечном итоге должно получится 2(n-1) путей из которых потом надо выбрать наименьший. Я планировал сделать это через бинарное дерево, однако пока не выходит ни одного нормального алгоритма.
Буду благодарен, если кто-нибудь сможет подсказать, каким образом можно решить эту задачу.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 18:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru