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

@Акелла · Регистрация: 10.05.2009

Студворк — интернет-сервис помощи студентам

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);
}

получается так?

@FunDuck · 10.06.2009, 22:49

Теоретически так.... только не надо сотню раз выводить информацию в текущем узле... а вообще все от организации дерева зависит.

@Акелла · 10.06.2009, 22:50 **[ТС]**

FunDuck, то есть от организации? просто у меня фантаззии представить как это обойти 100 арное деревце не хватает=(

@FunDuck · 10.06.2009, 22:53

Ну например, каждый элемент имеет ссылку не на всех потомков, а только на одного, который имеет ссылку на одного брата...в свою очередь брат имеет ссылку на другого брата.. и т.д. т.е. обход уже будет выполняться не в глубину, а в ширину.

Evg · 10.06.2009, 22:53

Недвоичные деревья обычно представляют не так. В каждом узле хранится ссылка на левого сына и на правого брата. Ну и для быстрого обхода и для удобства - ссылка на родителя и левого брата

@Акелла · 10.06.2009, 22:55 **[ТС]**

FunDuck, не, если с братьями - это же ДБ дерево...
хотя блин.... ну то есть если допустим дерево обычное, т.е. каждый узел может иметь только потмоков а не братьев, то функция верна?

в принципе по заданию сказанно что обход можно вести в любом порядке, я просто симетричный выбрал

@FunDuck · 10.06.2009, 22:59

Сообщение от Акелла

FunDuck, не, если с братьями - это же ДБ дерево...
хотя блин.... ну то есть если допустим дерево обычное, т.е. каждый узел может иметь только потмоков а не братьев, то функция верна?

В принципе, да.

Evg · 10.06.2009, 23:22

> т.е. каждый узел может иметь только потмоков а не братьев

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

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

@Neutrino2 · 14.04.2021, 18:07

Алгоритм решения поставленной задачи на псевдокоде (javascript):

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/** узел дерева */
class Node {
    id;
    info;
    parent = null;
    children = [];
}
 
/** прямой обход произвольного дерева */
    preOrderGo(node) {
        if (node) {
            console.log(node.info);
            for (let i = 0; i < node.children.length; ++i) {
                preOrderGo(node.children[i]);
            }
        }
    }
 
}
 
// ...
preOrderGo(root);

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@FunDuck 692 / 383 / 51 Регистрация: 22.01.2009 Сообщений: 1,135
	10.06.2009, 22:49
	Теоретически так.... только не надо сотню раз выводить информацию в текущем узле... а вообще все от организации дерева зависит. 0

@Акелла Сонный металюга 46 / 46 / 13 Регистрация: 10.05.2009 Сообщений: 295
	10.06.2009, 22:50 [ТС]
	FunDuck, то есть от организации? просто у меня фантаззии представить как это обойти 100 арное деревце не хватает=( 0

@FunDuck 692 / 383 / 51 Регистрация: 22.01.2009 Сообщений: 1,135
	10.06.2009, 22:53
	Ну например, каждый элемент имеет ссылку не на всех потомков, а только на одного, который имеет ссылку на одного брата...в свою очередь брат имеет ссылку на другого брата.. и т.д. т.е. обход уже будет выполняться не в глубину, а в ширину. 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	10.06.2009, 22:53
	Недвоичные деревья обычно представляют не так. В каждом узле хранится ссылка на левого сына и на правого брата. Ну и для быстрого обхода и для удобства - ссылка на родителя и левого брата 0

@Акелла Сонный металюга 46 / 46 / 13 Регистрация: 10.05.2009 Сообщений: 295
	10.06.2009, 22:55 [ТС]
	FunDuck, не, если с братьями - это же ДБ дерево... хотя блин.... ну то есть если допустим дерево обычное, т.е. каждый узел может иметь только потмоков а не братьев, то функция верна? в принципе по заданию сказанно что обход можно вести в любом порядке, я просто симетричный выбрал 0

Evg 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	10.06.2009, 23:22
	> т.е. каждый узел может иметь только потмоков а не братьев Товарищи, по-моему вы путаете писюн с гусиной шеей. Какждый узел действительно имеет только потомков. Но для удобства обхода реализуют это дело так, что хранят в узле не список потомков (которох может быть 100), а одну ссылку на левого сына, а к следующему сыну обращаются не напрямую, а как к брату левого сына. Техничеси такая структура проще поддерживается, чем хранение динамического списка сыновей. 0