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

Обход произвольного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.71
Акелла
Сонный металюга
 Аватар для Акелла
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
10.06.2009, 22:43     Обход произвольного дерева #1
C++
1
2
3
4
5
struct tree {
  char info;
  struct tree *left;
  struct tree *right;
};
так, вопрос глупый -меня просто сомнения берут. вот смотрите, если обход бинарного дерева в симметричном порядке у нас функция процедура такая делает:
C++
1
2
3
4
5
6
7
8
void inorder(struct tree *root)
{
  if(!root) return;
 
  inorder(root->left);
  if(root->info) printf("%c ", root->info);
  inorder(root->right);
}
а если дерево не бинарное,а 100-арное (т.е. у каждого элемента кроме листа не 2 а 100 потомков), то функция становиться такая??
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void inorder(struct tree *root)
{
  if(!root) return;
 
  inorder(root->el_1);
  if(root->info) printf("%c ", root->info);
  inorder(root->el_2);
  if(root->info) printf("%c ", root->info);
  inorder(root->el_3);
 
 
 //и так до...
 
  if(root->info) printf("%c ", root->info);
  inorder(root->el_100);
}
получается так?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.06.2009, 22:43     Обход произвольного дерева
Посмотрите здесь:

Обход дерева C++
C++ Нерекурсивный обход дерева
C++ Обход бинарного дерева
Обход дерева) C++
C++ Обход n-арного дерева
Обход дерева C++
обход дерева C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
FunDuck
688 / 379 / 4
Регистрация: 22.01.2009
Сообщений: 1,135
10.06.2009, 22:49     Обход произвольного дерева #2
Теоретически так.... только не надо сотню раз выводить информацию в текущем узле... а вообще все от организации дерева зависит.
Акелла
Сонный металюга
 Аватар для Акелла
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
10.06.2009, 22:50  [ТС]     Обход произвольного дерева #3
FunDuck, то есть от организации? просто у меня фантаззии представить как это обойти 100 арное деревце не хватает=(
FunDuck
688 / 379 / 4
Регистрация: 22.01.2009
Сообщений: 1,135
10.06.2009, 22:53     Обход произвольного дерева #4
Ну например, каждый элемент имеет ссылку не на всех потомков, а только на одного, который имеет ссылку на одного брата...в свою очередь брат имеет ссылку на другого брата.. и т.д. т.е. обход уже будет выполняться не в глубину, а в ширину.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16937 / 5342 / 328
Регистрация: 30.03.2009
Сообщений: 14,363
Записей в блоге: 26
10.06.2009, 22:53     Обход произвольного дерева #5
Недвоичные деревья обычно представляют не так. В каждом узле хранится ссылка на левого сына и на правого брата. Ну и для быстрого обхода и для удобства - ссылка на родителя и левого брата
Акелла
Сонный металюга
 Аватар для Акелла
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
10.06.2009, 22:55  [ТС]     Обход произвольного дерева #6
FunDuck, не, если с братьями - это же ДБ дерево...
хотя блин.... ну то есть если допустим дерево обычное, т.е. каждый узел может иметь только потмоков а не братьев, то функция верна?

в принципе по заданию сказанно что обход можно вести в любом порядке, я просто симетричный выбрал
FunDuck
688 / 379 / 4
Регистрация: 22.01.2009
Сообщений: 1,135
10.06.2009, 22:59     Обход произвольного дерева #7
Цитата Сообщение от Акелла Посмотреть сообщение
FunDuck, не, если с братьями - это же ДБ дерево...
хотя блин.... ну то есть если допустим дерево обычное, т.е. каждый узел может иметь только потмоков а не братьев, то функция верна?
В принципе, да.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2009, 23:22     Обход произвольного дерева
Еще ссылки по теме:

C++ Обход дерева Хаффмана
C++ Обход дерева в ширину
C++ обход дерева
C++ Ускорить обход дерева
C++ Обход Бинарного дерева

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

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16937 / 5342 / 328
Регистрация: 30.03.2009
Сообщений: 14,363
Записей в блоге: 26
10.06.2009, 23:22     Обход произвольного дерева #8
> т.е. каждый узел может иметь только потмоков а не братьев

Товарищи, по-моему вы путаете писюн с гусиной шеей.

Какждый узел действительно имеет только потомков. Но для удобства обхода реализуют это дело так, что хранят в узле не список потомков (которох может быть 100), а одну ссылку на левого сына, а к следующему сыну обращаются не напрямую, а как к брату левого сына. Техничеси такая структура проще поддерживается, чем хранение динамического списка сыновей.
Yandex
Объявления
10.06.2009, 23:22     Обход произвольного дерева
Ответ Создать тему
Опции темы

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