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

Найти узел в дереве поиска, являющийся самым «молодым» общим предком двух заданных узлов, и вывести его значение

19.02.2020, 19:33. Показов 1049. Ответов 1

Студворк — интернет-сервис помощи студентам
Суть такая:
Построить дерево поиска с элементами — строками. Используя операции Addr, Father и Value, найти узел, являющийся самым «молодым» общим предком двух заданных узлов, и вывести его значение.
Как я понимаю, операция Addr должна возвращать адрес элемента, Father - родителя элемента, а Value - его значение.
То есть по факту при записи элемента в дерево надо сохранять очередь, каким он был закинут. Потом найти последний закинутый, который имеет 2 разветвления (влево и вправо). Это я так понял.
Есть несколько методов, добавления в дерево элементов, вывода дерева, а также поиска значения в узле и поиск узла.
Проблема с записью очереди и проверкой на наличие потомков у узла, если поможете с решением - буду благодарен)

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
public class MyBinaryTree
    {
 
        public enum BinSide
        {
            Left,
            Right
        }
        /// <summary>
        /// Бинарное дерево поиска.
        /// </summary>
        public class BinaryTree
        {
 
            public long? Data { get; private set; }
            public string Value { get; set; }
            public BinaryTree Left { get; private set; }
            public BinaryTree Right { get; set; }
            public BinaryTree Parent { get; set; }
 
            /// <summary>
            /// Вставляет целочисленное значение в дерево.
            /// </summary>
            /// <param name="data">
            /// Значение которое добавляется в дерево.
            /// </param>
            public void Insert(long data)
            {
                if (Data == null || Data == data)
                {
                    Data = data;
                    return;
                }
                if (Data > data)
                {
                    if (Left == null) Left = new BinaryTree();
                    Insert(data, Left, this);
                }
                else
                {
                    if (Right == null) Right = new BinaryTree();
                    Insert(data, Right, this);
                }
            }
/// <summary>
            /// Ищет узел с заданным значением.
            /// </summary>
            /// <param name="data">
            /// Значение для поиска.
            /// </param>
            /// <returns></returns>
            public BinaryTree Find(long data)
            {
                if (Data == data) return this;
                if (Data > data)
                {
                    return Find(data, Left);
                }
                return Find(data, Right);
            }
 
            // public BinaryTree Address()
            /// <summary>
            /// Ищет значение в определенном узле.
            /// </summary>
            /// <param name="data">
            /// Значение для поиска.
            /// </param>
            /// <param name="node">
            /// Узел для поиска.
            /// </param>
            /// <returns></returns>
            public BinaryTree Find(long data, BinaryTree node)
            {
                if (node == null) return null;
 
                if (node.Data == data) return node;
                if (node.Data > data)
                {
                    return Find(data, node.Left);
                }
                return Find(data, node.Right);
            }
}
 
 public class BinaryTreeExtensions
        {
 
            public void Print(BinaryTree node)
            {
                if (node != null)
                {
                    if (node.Parent == null)
                    {
                        Console.WriteLine("ROOT:{0}", node.Data);
                    }
                    else
                    {
                        if (node.Parent.Left == node)
                        {
                            Console.WriteLine("Left for {1} --> {0}", node.Data, node.Parent.Data);
                        }
                        if (node.Parent.Right == node)
                        {
                            Console.WriteLine("Right for {1} --> {0}", node.Data, node.Parent.Data);
                        }
                    }
                    if (node.Left != null)
                    {
                        Print(node.Left);
                    }
                    if (node.Right != null)
                    {
                        Print(node.Right);
                    }
                }
            }
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.02.2020, 19:33
Ответы с готовыми решениями:

Написать пргограмму, определяющую разницу в возрасте между самым молодым и самым старым сотрудником кафедры.
Профессор Петечкин вывел формулу, по которой можно определить возраст любого из n сотрудников кафедры &quot;Политология&quot; на основе его...

В дереве бинарного поиска найти для него количество четных значений узлов дерева
В файле input.txt хранится последовательность целых чисел. По входной последовательности построить дерево бинарного поиска и найти для...

Шаблонизировать получение синглтонов с общим предком
Здравствуйте! В своей программе я реализую переход между окнами через паттерн Состояние. Есть абстрактный класс WindowsState: class...

1
 Аватар для Enifan
1848 / 1190 / 501
Регистрация: 14.10.2018
Сообщений: 3,211
19.02.2020, 19:59
mc_fly, самый первый вопрос, который мне лезет в голову, почему нет разделения на 2 класса: само дерево и узел. Это самый распространенный и правильный подход.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
19.02.2020, 19:59
Помогаю со студенческими работами здесь

Сформировать массив С, являющийся объединением двух заданных
Дан массив А из К элементов и массив В из М элементов. Сформировать массив С, являющийся объединением двух заданных, т.е. включить в него...

Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?
Вот примерная рекурсивная функция, но я не знаю, как выйти из нее в нужный момент. void range(Node *root, int r) { if...

Как найти в двоичном дереве поиска минимальный элемент, превышающий некоторое заданное значение?
Вот примерная рекурсивная функция, но я не знаю, как выйти из нее в нужный момент. void range(Node *root, int r) { if...

Найти суммы последовательных узлов в бинарном дереве
Есть бинарное дерево поиска и какое-то заданное число S. Нужно найти все монотонные последовательности узлов дерева, сумма значения которых...

В дереве найти такой пусть, чтобы сумма узлов была равна заданному числу
Задача: В дереве найти такой пусть, чтобы сумма узлов была равна 50. В целом, понятно. У меня вышло найти тот узел, в котором эта...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru