Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.71
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
#1

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

10.06.2009, 22:43. Просмотров 5380. Ответов 7
Метки нет (Все метки)

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);
}
получается так?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.06.2009, 22:43
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обход произвольного дерева (C++):

обход дерева - C++
Здравствуйте! У меня вопрос: Есть класс: class D { vector <A*> count; }; ...

обход дерева - C++
struct SAcson { int l,c; // строка, столбец float x; // заряд bool e; // возбуждающий или тормозящий }; struct SSinapc { ...

Обход дерева - C++
Всем доброе время суток. Не могу нормально обойти дерево и просмотреть введённое, по всей видимости, возможно я неправильно поставил...

Обход дерева - C++
Вот начал читать про деревья и способы их обхода (PreOrder, InOrder и PostOrder). С алгоритмами проблем нет, но видно, как бы это сказать...

Обход дерева) - C++
Прога работает) но сказали, что нужно сделать отдельную функцию обхода дерева) можете помочь) или пример)) #include <iostream.h> ...

Ускорить обход дерева - C++
Во входном файле ancestor.in в первой строке содержится количество узлов дерева, во второй строке массив чисел i-ое из которых определяет...

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

в принципе по заданию сказанно что обход можно вести в любом порядке, я просто симетричный выбрал
0
FunDuck
688 / 379 / 4
Регистрация: 22.01.2009
Сообщений: 1,135
10.06.2009, 22:59 #7
Цитата Сообщение от Акелла Посмотреть сообщение
FunDuck, не, если с братьями - это же ДБ дерево...
хотя блин.... ну то есть если допустим дерево обычное, т.е. каждый узел может иметь только потмоков а не братьев, то функция верна?
В принципе, да.
1
Evg
Эксперт CАвтор FAQ
18248 / 6373 / 438
Регистрация: 30.03.2009
Сообщений: 17,640
Записей в блоге: 28
10.06.2009, 23:22 #8
> т.е. каждый узел может иметь только потмоков а не братьев

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

Какждый узел действительно имеет только потомков. Но для удобства обхода реализуют это дело так, что хранят в узле не список потомков (которох может быть 100), а одну ссылку на левого сына, а к следующему сыну обращаются не напрямую, а как к брату левого сына. Техничеси такая структура проще поддерживается, чем хранение динамического списка сыновей.
0
10.06.2009, 23:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.06.2009, 23:22
Привет! Вот еще темы с ответами:

Обход дерева Хаффмана - C++
Добрый вечер. Имеем кодовое дерево Хаффмана.(в изображении) До каждого узла данного дерева есть путь из 0 и 1 . Для узла 12 ,...

Обход бинарного дерева - C++
может есть у кого такой пример или похожий??или часть какая нибудь?

Обход дерева в ширину - C++
Кто нибудь может скинуть мне программу обхода дерева в ширину?

Обход дерева по образцу - C++
Помогите осуществить обход дерева по образцу.


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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