Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.93/67: Рейтинг темы: голосов - 67, средняя оценка - 4.93
26 / 26 / 9
Регистрация: 25.05.2009
Сообщений: 98
1

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

26.05.2009, 17:02. Показов 12286. Ответов 25
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Стыдно, если честно, об этом просить, но "возник стопор" и путных идей не приходит.
Суть задачи:
Есть массив 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) путей из которых потом надо выбрать наименьший. Я планировал сделать это через бинарное дерево, однако пока не выходит ни одного нормального алгоритма.
Буду благодарен, если кто-нибудь сможет подсказать, каким образом можно решить эту задачу.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.05.2009, 17:02
Ответы с готовыми решениями:

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

Построение бинарного дерева
Доброй ночи! Пятые сутки не могу разобрать реализацию алгоритма на С++ Console Wizzard! Что такое...

Построение бинарного дерева
Написать программу построения бинарного дерева с помощью связных структур и поиска в дереве при...

Построение бинарного дерева из строки
Доброго времени суток, уважаемые. Хотел бы спросить у вас спросить совета относительно...

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

Либо жди, вдруг объявится добрая душа, которая по твоему описанию напишет программу. Но, подозреваю, что у людей будет проблема, чтобы понять твой алгоритм. Я, например, при беглом прочтении не понял. Уровень задачи и тот факт, что способ её решения в теории ты понимешь, подсказывает мне то, что в жизни ты всё-таки собираешься заниматься программированием, а потому всё-таки порекомендовал бы тебе разобраться самому. Ну и если будут конкретные вопросы, то чем сможем поможем
0
26 / 26 / 9
Регистрация: 25.05.2009
Сообщений: 98
27.05.2009, 18:52  [ТС] 5
Ну, на самом деле основной вопрос был: стоит ли заморачиваться с бинарными деревьями для такой задачи. Суть задачи проста - отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город.
В качестве алгоритма решения преподавателем был задан следующий:
Пункты обхода последовательно включаются в маршрут, причем, каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута.
Однако, поскольку реализация такого алгоритма слишком проста, то было задано выбирать не один, а два города, путь в которые наиболее выгоден. Соответственно получается не 1 а 2^(n-1) маршрутов, среди которых надо потом выбрать минимальный.
Принцип построения бинарного дерева я понял (все оказалось проще, чем я думал), однако, как адаптировать его под запоминание таких маршрутов, я пока представить не могу. Возможно, есть более оптимальный путь решения, чем через бинарное дерево. Если у вас есть идеи по поводу того, как можно было бы решить эту задачу, прошу изложить их здесь.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
27.05.2009, 19:34 6
Ну это уже скорее вопрос по алгоритмам, а с математикой у меня совсем плохо
Попробуй в этом разделе спросить https://www.cyberforum.ru/algorithms
1
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 секунд
блин, дерево не получается нормалньо нариосвать ну вобщем смысл понятен я надеюсь, пожалуйста, очень прошу, помогите!!
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
29.05.2009, 11:04 8
Представление выражения в двоичном дереве
Посты #3 и #5
0
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
29.05.2009, 23:44 9
C++ Builder на этом языке желаетльно..(
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
30.05.2009, 11:51 10
Цитата Сообщение от Олесенечек) Посмотреть сообщение
C++ Builder на этом языке желаетльно..(
https://www.cyberforum.ru/cpp-... 37065.html
Скажем так. Тебе выдали программу, которая уже делает все самые сложные действия, а так же умеет печатать дерево (пусть и не так карасиво, как требует того задание). Причём программу выдали тебе совершенно бесплатно. Вот хватай её и ищи того, кто заденьги тебе доработает её напильником. Поискать можешь, например, здесь https://www.cyberforum.ru/order-program

При этом не забудь указать свою версию builder'а, чтобы в дальнейшем не возникло конфуза
0
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 16:23 11
а вы можете ща деньги??
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
30.05.2009, 16:26 12
Цитата Сообщение от Олесенечек) Посмотреть сообщение
а вы можете ща деньги??
На семнадцатой итерации чтения вопроса у меня переполнился стек. Но тем не менее буду как наш депутат, заявивший "я книгу не читал, но с автором не солгласен", и отвечу "нет"
0
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 16:26 13
вы можете за деньги?
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
30.05.2009, 16:28 14
нет
0
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;
  }
}
эта программа подойдет?
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
30.05.2009, 18:07 16
Это программа перевода выражения в так называемую польскую запись. С такой формой можно строить код по вычислению выражения, но неудобно "рисовать" дерево выражения (особенно в текстовом режиме). Хотя с него можно и рисовать, только код получается более геморройный, чем с дерева
0
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 18:16 17
ну так если я введу выраженпие какоето, мне программа выдаст дерево?
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
30.05.2009, 18:26 18
нет. Если ты введёшь "(a+b)*(c-d)", то программа тебе выдаст "ab+cd-*" или что-то типа того. Чтобы выражение разрисовать в виде дерева в консоли, нужно мудохаться, потому как дерево за один проход нормально не распечатать.
0
4 / 4 / 0
Регистрация: 28.05.2009
Сообщений: 14
30.05.2009, 18:47 19
так а можно эту программу както оттредактировать чтоб она дерево выдавала?
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
30.05.2009, 18:56 20
Можно. Но долго, муторно и геморно
0
30.05.2009, 18:56
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.05.2009, 18:56
Помогаю со студенческими работами здесь

Построение бинарного дерева. Где ошибка?
Насколько понял, tree-&gt;left, tree-&gt;right указывает на NULL. Почему, не могу разобратся. #include...

Код Хаффмана реализованный через построение бинарного дерева
Здравствуйте, есть код Хаффмана реализованный через построение бинарного дерева, узлами которого...

Построение иерархического дерева из двумерного массива
Дано: Файл с содержимым: // Folder Kiev, Zhulyanu, POS12345 Kiev, Zhulyanu, POS333223 Kiev,...

Построение бинарного дерева. Обход дерева
Построить дерево поиска с элементами – числами. С использованием операций Locate и DeleteLeft найти...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru