VPF::Обход дерева. - Форум программистов

Mark4545

Дата 28.10.2009, 21:01 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 111
Регистрация: 6.11.2006

Репутация: нет
Всего: нет

Дано несколько элементов дерева имеющих структуру

Код


struct tree {
           char         name;             // имя узла дерева
           char         parentName; // Имя родителся
           int          level; // Уровень вложености
           struct tree *parent; //указатель на родителя
           int          nChilds; //кол-во детей
           struct tree *child[ 25 ]; //Указатели на детей.
           int size; //Виртуальный( вымышленый размер)
};

Допустим есть дерево в скобочках указан виртуальный размер

Код


            A(10)
                |
 X(6)-----C(2)------------------------L(3)
   |           |
 Y(8)       D(5)----E(15)

Как определить ветвь с максимальным размером т.е в данном случаее это будет A-C-E ( 10 + 2 + 15 ) =27

Это сообщение отредактировал(а) Mark4545 - 28.10.2009, 21:12

Mark4545

Дата 29.10.2009, 00:57 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 111
Регистрация: 6.11.2006

Репутация: нет
Всего: нет

Вопрос решен

Anikmar

Дата 29.10.2009, 08:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2513
Регистрация: 26.11.2006
Где: Санкт-Петербург

Репутация: 9
Всего: 59

Цитата(Mark4545 @ 29.10.2009, 00:57

)

Вопрос решен

Правила форума:

Если вопрос решен - надо сказать как и закрыть тему

Mark4545

Дата 29.10.2009, 13:36 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 111
Регистрация: 6.11.2006

Репутация: нет
Всего: нет

Код


struct vetka {
    char trace[ 255 ] ;
    int sum;
};

Код


vetka vetka1[ 255 ] = { 0 };
            tree *ptree = 0;
            int vetk = 0;
            int cVetk = 0;
            for ( int level = maxlevel ; level >=0 ; level--)
            {
                for ( int curElem = 0; curElem <= nElem ; curElem ++)
                {
                    if ( curTree[curElem].level == level )
                    {
                        if ( curTree[curElem].name != 0 )
                        {
                            if( curTree[curElem].used == false )
                            {
                                //printf("%d:%d\n",vetk,cVetk);
                                //getch();
                              vetka1[ vetk ].trace[cVetk] = curTree[curElem].name;
                              //printf("%c has %d level and size %d\n",curTree[curElem].name,level,curTree[curElem].size);
                              ptree = curTree[curElem].parent;
                              ptree->used = true;
                              vetka1[ vetk ].sum = vetka1[ vetk ].sum + curTree[curElem].size;
                             // printf("trace!:%s(%d)\n",vetka1[ vetk ].trace,vetka1[ vetk ].sum);
                             // getch();
                              while( ptree )
                              {
                                  cVetk++;
                                  vetka1[ vetk ].trace[cVetk] = ptree->name;
                                  vetka1[ vetk ].sum = vetka1[ vetk ].sum + ptree->size;
                                 // printf("trace:%s(%d)\n",vetka1[ vetk ].trace,vetka1[ vetk ].sum);
                                  if ( !(ptree->parent) )
                                  {
                                      vetk++;
                                      cVetk=0;
                                      break;
                                  }
                                  ptree = ptree->parent;
                                  ptree->used= true;
                              }
                            }
                        }
                    }
                }
            }
            printf("Total vetok:%d\n",vetk);

В структуру дерева добавлен элемент used. при обходе элемента ставиться в значение true

azesmcar

Дата 29.10.2009, 13:42 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Цитата(Mark4545 @ 29.10.2009, 13:36

)

В структуру дерева добавлен элемент used. при обходе элемента ставиться в значение true

а почему не рекурсией? зачем так извращаться?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »