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

Бинарное дерево: обход дерева с ключами до искомого

11.09.2013, 18:40. Показов 5580. Ответов 11
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго вечера всем! Нужна помощь, так как сама не знаю как реализовать задание. А оно звучит так: Нужно написать программу бинарного дерева(в консоли, или форме, не важно). Вершины этого дерева - какие-то слова, которые считываются с текстового файла. И как нам объяснили - У каждого слова(вершины) есть свой номер - ключ. Пользователь должен ввести какое-то слово из данных, и выводится обход этого дерева с ключами до искомого. Как-то так. Спасибо!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.09.2013, 18:40
Ответы с готовыми решениями:

Преобразовать идеальное бинарное дерево в бинарное дерево поиска
Всем привет, я создал идельное бинарное дерево и написал к нему функции. Как мне теперь можно...

Бинарное дерево. Обход в ширину
Господа, добрый день. Прошу, помогите написать обход в ширину, с обходом в глубину разобрался, а...

Обход в ширину. Бинарное дерево
Прошу подсказать, как сделать обход в ширину, ибо порывшись на просторах форума, путного ничего не...

11
 Аватар для n1l
136 / 138 / 18
Регистрация: 26.07.2010
Сообщений: 911
11.09.2013, 19:18
Сформулируйте задачу четче.
Хотя я кажется понял, что от вас хотят, но все равно, если вы хотите решение, опишите задачу конкретнее.
0
25 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 94
11.09.2013, 19:36  [ТС]
Постараюсь, точнее.
Есть бинарное дерево, так. У этого дерева как-то словесно названы вершины. и эти слова считываются с текстового файла. У каждого слова есть ключ - цифра(номер). Пользователь вводит слово, например яблоко. И программа показывает путь по дереву до этого слова, например вот так 1-2-3-4-5. я поняла так.
0
 Аватар для n1l
136 / 138 / 18
Регистрация: 26.07.2010
Сообщений: 911
11.09.2013, 19:50
Ну, как мне кажется не совсем.
Прочтите определение дерева. Двоичное дерево, это дерево у каждого элемента которого есть только два подэлемента и родитель. В качестве аналогии можно рассматривать дерево из чисел, либо подэлемент больше родителя и он помещается в правую ветку(1) либо меньше и он помещается в левую.(0) Из этого следует, что если вы получаете ключ из файла в десятичном представлении, то вам сначала нужно перевести его в двоичное и это будет путь. Далее побитово прочесть число и пройти по пути.
Но это лишь мое понимание задачи, я не могу гарантировать то, что это и требуется. В конечном итоге я мог все усложнить.

Добавлено через 3 минуты
Можно конечно эти ключи просто хранить в дереве, тогда обход будет проще.
0
25 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 94
11.09.2013, 19:57  [ТС]
может, конечно, имеется ввиду то, что как бы пронумерованы вершины просто, а из файла мы считываем слова и вставляем в вершины.

Я написала как объяснили. =(
0
Неадекват
 Аватар для freeba
1501 / 1237 / 248
Регистрация: 02.04.2010
Сообщений: 2,807
11.09.2013, 20:07
Как то так. Проект прилагается.
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
using System;
using System.IO;
 
namespace SearchTree
{
    public class Program
    {
        static void Main(string[] args)
        {
            Tree tree = new Tree();
 
            var stream = new StreamReader("in.txt");
            var text = stream.ReadToEnd().ToLower().Replace(",", "").Replace(".", "");
 
            foreach (var item in text.Split(' '))
            {
                if (item.Trim().Length > 0)
                {
                    tree.Add(item.Trim(), tree.Root);
                    tree.ID++;
                }
            }
 
            Console.Write("{0}\n\nВведите искомое слово:", text);
            var find = Console.ReadLine();
 
            string result = tree.Get(find, tree.Root) ? "Искомое слово найдено." : "Искомое слово не найдено";
 
            Console.WriteLine(result);
            Console.ReadKey();
        }
    }
 
    public class Node
    {
        public string Value { get; set; }
        public int ID { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
    }
 
    public class Tree
    {
        public Node Root = null;
        public int ID = 0;
 
        public bool Add(string value, Node node = null)
        {
            if (Root == null)
            {
                Root = new Node();
                Root.Value = value;
                return true;
            }
 
            if (node == null) return true;
 
            if (node.Value.CompareTo(value) == -1)
            {
                if (node.Left == null)
                    node.Left = new Node() { Value = value, ID = ID };
                else
                    return Add(value, node.Left);
            }
 
            if (node.Value.CompareTo(value) == 1)
            {
                if (node.Right == null)
                    node.Right = new Node() { Value = value, ID = ID };
                else
                    return Add(value, node.Right);
            }
 
            return true;
        }
 
        public bool Get(string value, Node node = null)
        {
            if (node == null) return false;
 
            if (node.Value.CompareTo(value) == -1)
            {
                Console.WriteLine(node.ID);
                return Get(value, node.Left);
            }
 
            if (node.Value.CompareTo(value) == 1)
            {
                Console.WriteLine(node.ID);
                return Get(value, node.Right);
            }
 
            if (node.Value.CompareTo(value) == 0)
            {
                Console.WriteLine(node.ID);
                return true;
            }
 
            return false;
        }
    }
}
Вложения
Тип файла: 7z SearchTree.7z (24.3 Кб, 100 просмотров)
1
25 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 94
11.09.2013, 20:38  [ТС]
Спасибо! буду разбираться
0
 Аватар для n1l
136 / 138 / 18
Регистрация: 26.07.2010
Сообщений: 911
11.09.2013, 20:49
Так как вы файл не предоставили, пришлось вот так вот сделать.
В общем логика проста, есть массив ключей и значений, в простонародье словарь, мы его загоняем в наше простое дерево, далее просим у пользователя ключ и ищем значение по ключу.
Возможны ошибки, так как в 12 часов ночи я не очень-то продуктивен.

Кликните здесь для просмотра всего текста

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
class Program
    {
        static void Main(string[] args)
        {
            Dictionary<int, string> dic =
                new Dictionary<int, string>
                    {
                        {7, "Яблоко"},
                        {2, "Слон"},
                        {5, "Бог"},
                        {4, "Вселенная"},
                        {1, "Университет"},
                        {6, "Дерево"},
                        {3, "Программирование"},
                        {10, "Москва"},
                        {9, "Море"},
                        {8, "Рыба"},
                        {11, "Сок"}
                    };
 
            Tree tree = new Tree();
 
            foreach (var item in dic)
            {
                tree.Add(new Node(item.Key, item.Value));
            }
 
            int inputKey = 0;
            int.TryParse(Console.ReadLine(), out inputKey);
 
            string result = tree.Find(inputKey);
 
            Console.WriteLine(result);
            Console.ReadLine();
 
 
 
        }
    }
 
    class Tree
    {
        private Node _root;
 
 
        public void Add(Node next)
        {
            Node current = _root;
            Node previous = null;
 
            while (current != null)
            {
                previous = current;
 
                if (next.Key > current.Key) 
                    current = current.Right;
                else current = current.Left;
 
            } 
            if (previous.Key > next.Key)
                previous.Left = next;
            else
                previous.Right = next;
            next.Parent = previous;
 
        }
 
        public string Find(int key)
        {
            Node current = _root;
 
            while (current != null)
            {
                if (current.Key == key)
                    return current.Value;
                if (current.Key > key)
                    current = current.Left;
                if (current.Key < key)
                    current = current.Right;
            }
            return "Элемент не найден";
        }
 
        public Tree()
        {
            _root = new Node(0,"");
        }
 
    }
 
    class Node
    {
        public int Key { get; private set; }
        public string Value { get; private set; }
 
        public Node Parent { get; set; }
        public Node Right { get; set; }
        public Node Left { get; set; }
 
 
        public Node(int key, string value)
        {
            Key = key;
            Value = value;
        }
    }
0
25 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 94
11.09.2013, 20:53  [ТС]
так какая из программ верная? первая или вторая? =)
А если вам не сложно, можете добавит пояснения - комментарии. Спасибо вам)
0
 Аватар для n1l
136 / 138 / 18
Регистрация: 26.07.2010
Сообщений: 911
12.09.2013, 06:16
Цитата Сообщение от Nady_Beauty Посмотреть сообщение
так какая из программ верная? первая или вторая? =)
А если вам не сложно, можете добавит пояснения - комментарии. Спасибо вам)
Да берите обе.
В моей реализации, класс node - это элемент дерева.
Класс tree само дерево.
Метод find осуществляет обход дерева и ищет ключ.
Метод add добавляет в дерево элемент.

В программе, сначала создаем исходные данные в словаре dic,
Потом каждый элемент словаря добавляем в дерево.
далее ждем от пользователя ключ.
И ищем этот ключ.
0
25 / 0 / 0
Регистрация: 02.04.2012
Сообщений: 94
12.09.2013, 19:13  [ТС]
а какой обход? префиксный или инфиксный?
0
 Аватар для n1l
136 / 138 / 18
Регистрация: 26.07.2010
Сообщений: 911
12.09.2013, 19:42
префиксный
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
12.09.2013, 19:42
Помогаю со студенческими работами здесь

Бинарное дерево не получается добавить значения дерева в список , как мне это исправить
Почему не получается добавить значение из бинарного дерева в список . Я трассирую в список...

Бинарное дерево с итератором, обходящим узлы дерева в "глубину" в обратном направлении
Написать класс реализующий структуру данных &quot;бинарное дерево&quot;. Реализовать в классе итератор,...

Бинарное дерево: как происходит добавления элемента в дерево с двумя параметрами
Здравствуйте! Прошу помощи у опытных программистов...)))) Есть класс дерево: class class1 ...

Опросник. Создание дерева зависимостей в treeView, сохранение дерева в XML, построение дерева в treeView из XML
Всем доброго времени суток. Тема является продолжением вот этой темы. Создаю 2ю, так как там...

Узнать, есть ли в Dictionary искомый ключ, если есть, то вернуть ссылку на экземпляр ключа
Здравствуйте, у меня есть Dictionary: Dictionary&lt;Keys, List&lt;string&gt;&gt; Mass = new Dictionary&lt;Keys,...


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
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, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru