Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.70/30: Рейтинг темы: голосов - 30, средняя оценка - 4.70
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80

Заполнение бинарного дерева в ширину без очереди

08.09.2018, 22:21. Показов 6641. Ответов 60

Студворк — интернет-сервис помощи студентам
Подскажите алгоритм заполнения бинарного дерева и поиск по нему, все в ширину.

Дерево имеет такую структуру.

C#
1
2
3
4
5
6
7
8
public class MyTree
    {
        public long? Data { get; private set; }
        public MyTree Left { get; set; }
        public MyTree Right { get; set; }
        public MyTree Parent { get; set; }
        public long Count { get; private set; }
    }
Хотелось бы реализовать рекурсией без очередей и реализации базовых интерфейсов.
Такое возможно?
Заранее спасибо!
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
08.09.2018, 22:21
Ответы с готовыми решениями:

Заполнение бинарного дерева по уровням (в ширину)
Добрый день, необходимо реализовать на php заполнение бинарного дерева в ширину (первый элемент добавляется на первый уровень, второй и...

Обход бинарного дерева в ширину
Честное слово, облазил весь интернет и не нашел не одной реально рабочей программы. Сама задача вот: программа, выполняющая обход дерева...

Реализация заполнения бинарного дерева в ширину
Добрый день, есть такая задача Алгоритм нашел: Попытался написать код, но не пойму как в итоге получить само результирующее дерево?...

60
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 22:26
В "ШИРИНУ" это как?
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 22:31  [ТС]
Элд Хасп,
1

/ \

2 3

/ \ / \

4 5 6 7

Добавлено через 3 минуты
и Count я инкрементную на Count родителя + 1, чтобы знать уровень элемента в дереве.
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 22:44
Давно это было...
Добавление что-то в таком духе.
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
        public class MyTree
        {
            /// <summary>Данные</summary>
            public long? Data { get; private set; }
            /// <summary>Элемент меньше</summary>
            public MyTree Left { get; private set; }
            /// <summary>Элемент больше или равно</summary>
            public MyTree Right { get; private set; }
            /// <summary>Родительский элемент </summary>
            public MyTree Parent { get; private set; }
            /// <summary>Это что? Количество чего?</summary>
            public long Count { get; private set; }
 
 
            /// <summary>Конструктор без параметров</summary>
            public MyTree() { }
 
            /// <summary>Конструктор</summary>
            /// <param name="Data">Данные</param>
            public MyTree(long? Data) => this.Data = Data;
 
            /// <summary>Добавление нового элемента в дерево</summary>
            /// <param name="NewMyTree">Новый элемент</param>
            public void Add(MyTree NewMyTree)
            {
                if (NewMyTree.Data < Data)
                {
                    if (Left == null)
                    {
                        NewMyTree.Parent = this;
                        Left = NewMyTree;
                    }
                    else Left.Add(NewMyTree);
                }
                else
                {
                    if (Right == null)
                    {
                        NewMyTree.Parent = this;
                        Right = NewMyTree;
                    }
                    else Right.Add(NewMyTree);
                }
            }
        }
0
Модератор
 Аватар для Curry
5158 / 3484 / 536
Регистрация: 01.06.2013
Сообщений: 7,557
Записей в блоге: 9
08.09.2018, 22:44
-----
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 22:48  [ТС]
Curry, null, это и будет отличать его от детей и детей детей
Т.е. при добавление элемента должно быть что-то топи того
C#
1
2
3
4
5
6
7
 if (node.Data == null)
            {
                node.Data = data;
                node.Parent = parent;
                node.Count = node.Parent.Count + 1;
                return;
            }
Я просто не могу додуматься как добавлять в ширь.
Удалось реализовать только сортированное бинарное дерево.
1
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 22:49
Цитата Сообщение от fivebits_ Посмотреть сообщение
и Count я инкрементную на Count родителя + 1, чтобы знать уровень элемента в дереве
Т.е уровень в дереве? Там по серьёзному если делать, надо считать элементы влево и вправо, чтобы если есть перекос, можно было его определить и откорректировать. Возникает, например, если элементы приходят в порядке возрастания/убывания. Тогда они все "садятся" на одну сторону.
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 22:52  [ТС]
Элд Хасп, тогда лучше назвать глубиной.
Элементы не должны сортироваться.

повторюсь

C#
1
node.Count = node.Parent.Count + 1;
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 22:55
Ещё нужно делать ветку для равных элементов, т.к. бывают случаи когда их много и это тоже искажает дерево. Как вариант можно запретить равные элементы.

Добавлено через 1 минуту
Цитата Сообщение от fivebits_ Посмотреть сообщение
Элементы не должны сортироваться.
Тогда вообще не понял. А для чего дерево? Какие функции у него?

Добавлено через 1 минуту
Цитата Сообщение от fivebits_ Посмотреть сообщение
повторюсь
Я пишу вопрос- отправляю. А потом вижу, что Вы ответ уже дали.
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 22:56  [ТС]
Элд Хасп,
Одинаковые значения можно добавлять.
Мне просто надо их сложить в определенном порядке.
Слева на право, пока в этом уровне всех детей не заполню и перехожу к уровню этих детей.
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 22:57
Цитата Сообщение от fivebits_ Посмотреть сообщение
Элементы не должны сортироваться.
Просто произвольное заполнение? Или как? По какому алгоритму заполнять?
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 22:57  [ТС]
Элд Хасп,

на вход идут элементы 6 3 5 7 8 1 3
Мне их надо сложить в дерево вот так


6

/ \

3 5

/ \ / \

7 8 1 3
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 23:01
Т.е. ? Допустим, на первых числах Вы получили
1
/ \
2 3

Пришли 4, 5 куда их добавлять? Учитывайте ещё, что у вершины нет сведений сколько в каждой ветке у него элементов и как они заполнены.

Добавлено через 53 секунды
А поиск по такому дереве превратится в дикий ужас!

Добавлено через 25 секунд
Лучше тогда линейно их хранить - больше толку.
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 23:02  [ТС]
Элд Хасп,
1
/ \
2 3
/ \
4 5
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 23:02
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Пришли 4, 5 куда их добавлять?
Уточняю. В какую ветку где 2 или 3? Как определить где меньше элементов?
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 23:03  [ТС]
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Лучше тогда линейно их хранить - больше толку.
Я с Вами полностью согласен.
Но надо вот так заполнять.
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 23:04
Цитата Сообщение от fivebits_ Посмотреть сообщение
1
/ \
2 3
/ \
4 5
Может тогда ввести счётчики для каждой ветки, и добавлять в ветку где счётчик меньше?
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 23:04  [ТС]
Цитата Сообщение от Элд Хасп Посмотреть сообщение
Уточняю. В какую ветку где 2 или 3? Как определить где меньше элементов?
в детей 2 пойдут, т.к. у нее свободно, а след уже детей 3 пойдут если будут.
0
Модератор
Эксперт .NET
 Аватар для Элд Хасп
16139 / 11263 / 2888
Регистрация: 21.04.2018
Сообщений: 33,105
Записей в блоге: 2
08.09.2018, 23:05
Какой-то алгоритм нужен. Он же самой задачей определяется.
0
1 / 1 / 0
Регистрация: 25.11.2014
Сообщений: 80
08.09.2018, 23:05  [ТС]
Элд Хасп, заполнить дерево(обход в ширину)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
08.09.2018, 23:05
Помогаю со студенческими работами здесь

Реализовать обход бинарного дерева в ширину
необходимо реализовать обход вот этого бинарного дерева в ширину using System; using System.Collections.Generic; using System.Linq; ...

Печать на консоль бинарного дерева, обход в ширину
Добрый вечер! Сразу скажу, топик не для слабонерных. Выручайте уважаемые программисты. Встала задача передо мной написать печать на КОНСОЛЬ...

Реализация обхода в ширину и глубину бинарного дерева
Как реализовать обход дерева (глубины три, т.е. трех уровневое) в глубину и ширину и что под этим подразумевается?

Печать на консоль бинарного дерева, обход в ширину
Добрый вечер! Сразу скажу, топик не для слабонерных. Выручайте уважаемые программисты. Встала задача передо мной написать печать на КОНСОЛЬ...

Заполнение особого бинарного дерева
Собственно класс бинарного дерева я прописал (хоть и криво, не в этом дело). Но метод вставки не подходит к поставленной задачи. А именно:...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии
Hrethgir 01.03.2026
Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru