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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 66, средняя оценка - 4.70
Deiron
25 / 25 / 1
Регистрация: 25.05.2009
Сообщений: 98
#1

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

26.05.2009, 17:02. Просмотров 8136. Ответов 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) путей из которых потом надо выбрать наименьший. Я планировал сделать это через бинарное дерево, однако пока не выходит ни одного нормального алгоритма.
Буду благодарен, если кто-нибудь сможет подсказать, каким образом можно решить эту задачу.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2009, 17:02     Построение бинарного дерева из двумерного массива
Посмотрите здесь:

Построение бинарного дерева C++
C++ Запись массива в виде бинарного дерева и вывод его на экран!
Запись бинарного дерева в файл и восстановление из него этого дерева C++
C++ Построение бинарного дерева на основе не бинарного
Построение бинарного дерева из строки C++
Построение бинарного дерева C++
C++ Вывод бинарного дерева на экран в виде "дерева"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
26.05.2009, 22:00     Построение бинарного дерева из двумерного массива #2
Особо не читывался. В чём суть проблемы то? Не знаешь, как ершать задачу. Не умеешь строить деревья или что? Или тебе нужно тупо выложить готовое решение?
Deiron
25 / 25 / 1
Регистрация: 25.05.2009
Сообщений: 98
26.05.2009, 23:30  [ТС]     Построение бинарного дерева из двумерного массива #3
как решить задачу, я примерно представляю. Даже более, чем примерно. Принцип построения путей по заданному алгоритму из n городов "на словах" - тоже прекрасно понимаю. Но реализовать это в коде тем или иным способом у меня не получается. Через массивы? Не ясно как. Оптимальным методом решения мне кажется построение дерева. Но вот с этим самым построением у меня как раз проблема, потому что до этого с деревьями не работал, только со списками. А там все несколько проще. Если бы Вы могли мне каким-либо образом помочь с построением б. дерева по нужному мне алгоритму, было бы очень хорошо.
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
26.05.2009, 23:39     Построение бинарного дерева из двумерного массива #4
Если ты никогда не работал с деревьями, то лучше почитай литературу, потому как на форуме я просто опухну столько объяснять. Насколько я понял, алгоритм построения дерева ты знаешь (т.е. карандашом на листочке нарисовать сможешь), так что больших проблем у тебя вызвать не должно.

Либо жди, вдруг объявится добрая душа, которая по твоему описанию напишет программу. Но, подозреваю, что у людей будет проблема, чтобы понять твой алгоритм. Я, например, при беглом прочтении не понял. Уровень задачи и тот факт, что способ её решения в теории ты понимешь, подсказывает мне то, что в жизни ты всё-таки собираешься заниматься программированием, а потому всё-таки порекомендовал бы тебе разобраться самому. Ну и если будут конкретные вопросы, то чем сможем поможем
Deiron
25 / 25 / 1
Регистрация: 25.05.2009
Сообщений: 98
27.05.2009, 18:52  [ТС]     Построение бинарного дерева из двумерного массива #5
Ну, на самом деле основной вопрос был: стоит ли заморачиваться с бинарными деревьями для такой задачи. Суть задачи проста - отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
В качестве алгоритма решения преподавателем был задан следующий:
Пункты обхода последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.
Однако, поскольку реализация такого алгоритма слишком проста, то было задано выбирать не один, а два города, путь в которые наиболее выгоден. Соответственно получается не 1 а 2^(n-1) маршрутов, среди которых надо потом выбрать минимальный.
Принцип построения бинарного дерева я понял (все оказалось проще, чем я думал), однако, как адаптировать его под запоминание таких маршрутов, я пока представить не могу. Возможно, есть более оптимальный путь решения, чем через бинарное дерево. Если у вас есть идеи по поводу того, как можно было бы решить эту задачу, прошу изложить их здесь.
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
27.05.2009, 19:34     Построение бинарного дерева из двумерного массива #6
Ну это уже скорее вопрос по алгоритмам, а с математикой у меня совсем плохо
Попробуй в этом разделе спросить http://www.cyberforum.ru/algorithms
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
28.05.2009, 20:14     Построение бинарного дерева из двумерного массива #7
привет всем!помогите пожалуйста!мне надо га си++ написать программу, кторая при вводе какогото арифмитического действия выдает как бы дерево разложения. например (х+5)*(3-(а-8)) и надо чтоб получилось * дальше 2 стрелочки в одной плюс (и из нее отходит опять 2 стрелочки в одной 5 в другой х, вот ) а в другой минус потом из нее 2 стрелочки в одной а в другой минус от нее еще 2 стрелочки в одной а в другой 8, ну короче разложение такое!!подалуйста!!очень надо!!!!!!за деньги, аська 44333649пример
*
/\
+ -
/ \ /\
а 5 2 *
/ \
а -
/\
у 6

Добавлено через 1 минуту 39 секунд
привет всем!помогите пожалуйста!мне надо га си++ написать программу, кторая при вводе какогото арифмитического действия выдает как бы дерево разложения. например (х+5)*(3-(а-8)) и надо чтоб получилось * дальше 2 стрелочки в одной плюс (и из нее отходит опять 2 стрелочки в одной 5 в другой х, вот ) а в другой минус потом из нее 2 стрелочки в одной а в другой минус от нее еще 2 стрелочки в одной а в другой 8, ну короче разложение такое!!подалуйста!!очень надо!!!!!!за деньги, аська 44333649пример
*
/\
+ -
/ \ /\
а 5 2 *
/ \
а -
/\
у 6

Добавлено через 1 минуту 11 секунд
блин, дерево не получается нормалньо нариосвать ну вобщем смысл понятен я надеюсь, пожалуйста, очень прошу, помогите!!
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
29.05.2009, 11:04     Построение бинарного дерева из двумерного массива #8
Представление выражения в двоичном дереве
Посты #3 и #5
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
29.05.2009, 23:44     Построение бинарного дерева из двумерного массива #9
C++ Builder на этом языке желаетльно..(
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
30.05.2009, 11:51     Построение бинарного дерева из двумерного массива #10
Цитата Сообщение от Олесенечек) Посмотреть сообщение
C++ Builder на этом языке желаетльно..(
http://www.cyberforum.ru/cpp-beginners/thread37065.html
Скажем так. Тебе выдали программу, которая уже делает все самые сложные действия, а так же умеет печатать дерево (пусть и не так карасиво, как требует того задание). Причём программу выдали тебе совершенно бесплатно. Вот хватай её и ищи того, кто заденьги тебе доработает её напильником. Поискать можешь, например, здесь http://www.cyberforum.ru/order-program

При этом не забудь указать свою версию builder'а, чтобы в дальнейшем не возникло конфуза
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 16:23     Построение бинарного дерева из двумерного массива #11
а вы можете ща деньги??
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
30.05.2009, 16:26     Построение бинарного дерева из двумерного массива #12
Цитата Сообщение от Олесенечек) Посмотреть сообщение
а вы можете ща деньги??
На семнадцатой итерации чтения вопроса у меня переполнился стек. Но тем не менее буду как наш депутат, заявивший "я книгу не читал, но с автором не солгласен", и отвечу "нет"
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 16:26     Построение бинарного дерева из двумерного массива #13
вы можете за деньги?
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
30.05.2009, 16:28     Построение бинарного дерева из двумерного массива #14
нет
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 17:03     Построение бинарного дерева из двумерного массива #15
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<stdio.h>
#include<stdlib.h>
 
 /* Описание стpуктуpы(элемента стека) */
struct st                
{ char c;struct st *next;};
struct st *push(struct st *, char); 
/* Пpототипы функций */
char DEL(struct st **);
int PRIOR(char);
 
void main(void)
{
  /* Стек опеpаций пуст */
  struct st *OPERS=NULL;                     
  char a[80], outstring[80];
  int k, point;
  do
  { puts("Введите выpажение(в конце '='):");
    fflush(stdin);
    /* Ввод аpифметического выpажения */
    gets(a);                                 
    k=point=0;
      /* Повтоpяем , пока не дойдем до '=' */
    while(a[k]!='\0'&&a[k]!='=')           
    {
    /* Если очеpедной символ - ')' */
      if(a[k]==')')             
                 /* то выталкиваем из стека в выходную стpоку */
      {                                     
              /* все знаки опеpаций до ближайшей */
        while((OPERS->c)!='(')         
              /* откpывающей скобки */
        outstring[point++]=DEL(&OPERS);  
              /* Удаляем из стека саму откpывающую скобку */
        DEL(&OPERS);
      }
                    /* Если очеpедной символ - буква , то */
      if(a[k]>='a'&&a[k]<='z')        
              /* пеpеписываем её в выходную стpоку */
          outstring[point++]=a[k];        
                    /* Если очеpедной символ - '(' , то */
      if(a[k]=='(')                         
              /* заталкиваем её в стек */
          OPERS=push(OPERS, '(');           
      if(a[k]=='+'||a[k]=='-'||a[k]=='/'||a[k]=='*')
      /* Если следующий символ - знак опеpации , то: */
      {                             
                /* если стек пуст */
        if(OPERS==NULL)                     
         /* записываем в него опеpацию */
            OPERS=push(OPERS, a[k]);        
             /* если не пуст */
        else                                 
/* если пpиоpитет поступившей опеpации больше 
               пpиоpитета опеpации на веpшине стека */
        if(PRIOR(OPERS->c)<PRIOR(a[k]))      
        /* заталкиваем поступившую опеpацию на стек */             
            OPERS=push(OPERS, a[k]);      
                   /* если пpиоpитет меньше */
        else                              
        {
          while((OPERS!=NULL)&&(PRIOR(OPERS->c)>=PRIOR(a[k])))
/* пеpеписываем в выходную стpоку все опеpации
                   с большим или pавным пpиоpитетом */
              outstring[point++]=DEL(&OPERS); 
                /* записываем в стек поступившую  опеpацию */
          OPERS=push(OPERS, a[k]);           
        } 
      }
      /* Пеpеход к следующему символу входной стpоки */
      k++;                                    
    }
       /* после pассмотpения всего выpажения */
    while(OPERS!=NULL)                     
     /* Пеpеписываем все опеpации из */
        outstring[point++]=DEL(&OPERS);    
          /* стека в выходную стpоку */
    outstring[point]='\0';                    
       /* и печатаем её */
    printf("\n%s\n", outstring);            
    fflush(stdin);
    puts("\nПовтоpить(y/n)?");
  } while(getchar()!='n');
}
 
/* Функция push записывает на стек (на веpшину котоpого указывает HEAD)
   символ a . Возвpащает указатель на новую веpшину стека */
struct st *push(struct st *HEAD, char a)
{
  struct st *PTR;
  /* Выделение памяти */
  if((PTR=malloc(sizeof(struct st)))==NULL) 
  {
  /* Если её нет - выход */
    puts("ет памяти");exit(-1);             
  }
  /* Инициализация созданной веpшины */
  PTR->c=a;                                
   /* и подключение её к стеку */
  PTR->next=HEAD;           
   /* PTR -новая веpшина стека */
  return PTR;                               
}
 
/* Функция DEL удаляет символ с веpшины стека.
   Возвpащает удаляемый символ.
   Изменяет указатель на веpшину стека */
char DEL(struct st **HEAD)
{
  struct st *PTR;
  char a;
  /* Если стек пуст,  возвpащается '\0' */
  if(*HEAD==NULL) return '\0'; 
  /* в PTR - адpес веpшины стека */
  PTR=*HEAD;                   
  a=PTR->c;
  /* Изменяем адpес веpшины стека */
  *HEAD=PTR->next;         
  /* Освобождение памяти */
  free(PTR);   
   /* Возвpат символа с веpшины стека */                
  return a;                   
}
 
/* Функция PRIOR возвpащает пpиоpитет аpифм. опеpации */
int PRIOR(char a)
{
  switch(a)
  {
    case '*':
    case '/':
         return 3;
 
    case '-':
    case '+':
         return 2;
 
    case '(':
         return 1;
  }
}
эта программа подойдет?
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
30.05.2009, 18:07     Построение бинарного дерева из двумерного массива #16
Это программа перевода выражения в так называемую польскую запись. С такой формой можно строить код по вычислению выражения, но неудобно "рисовать" дерево выражения (особенно в текстовом режиме). Хотя с него можно и рисовать, только код получается более геморройный, чем с дерева
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 18:16     Построение бинарного дерева из двумерного массива #17
ну так если я введу выраженпие какоето, мне программа выдаст дерево?
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
30.05.2009, 18:26     Построение бинарного дерева из двумерного массива #18
нет. Если ты введёшь "(a+b)*(c-d)", то программа тебе выдаст "ab+cd-*" или что-то типа того. Чтобы выражение разрисовать в виде дерева в консоли, нужно мудохаться, потому как дерево за один проход нормально не распечатать.
Олесенечек)
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 18:47     Построение бинарного дерева из двумерного массива #19
так а можно эту программу както оттредактировать чтоб она дерево выдавала?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2009, 18:56     Построение бинарного дерева из двумерного массива
Еще ссылки по теме:

C++ Код Хаффмана реализованный через построение бинарного дерева
C++ Построение бинарного дерева. Где ошибка?
Написать шаблон бинарного дерева с функцией распечатки дерева C++
C++ Высота бинарного дерева
C++ Реализация бинарного дерева С++

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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт CАвтор FAQ
17266 / 5520 / 343
Регистрация: 30.03.2009
Сообщений: 15,031
Записей в блоге: 26
30.05.2009, 18:56     Построение бинарного дерева из двумерного массива #20
Можно. Но долго, муторно и геморно
Yandex
Объявления
30.05.2009, 18:56     Построение бинарного дерева из двумерного массива
Ответ Создать тему
Опции темы

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