Реализация дерева с нуля

Question

Я пытаюсь узнать о деревьях, реализуя одно из них с нуля.В этом случае я бы хотел сделать это на C # Java или C ++.(без использования встроенных методов)

Таким образом, каждый узел будет хранить символ, и на каждый узел будет приходиться максимум 26 узлов.

Какую структуру данных я бы использовал для хранения указателей на каждый из узлов?

По сути, я пытаюсь реализовать исходное дерево с нуля.

Спасибо,

Answer 1

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

То, что вы описываете, звучит более ограниченным алфавитом...каждый узел может быть a-z, за ним может следовать другая буква, a-z и т.д.Это различие имеет решающее значение для структуры данных, которую вы выбираете для хранения указателей на следующий узел.

В описанном вами дереве самой простой структурой для использования может быть простой массив указателей...все, что вам нужно сделать, это преобразовать символ (например'A') к его значению ascii ('65') и вычтите начальное смещение (65), чтобы определить, какой "следующий узел" вы хотите.Занимает больше места, но очень быстрая вставка и перемещение.

В истинном исходном дереве у вас может быть 3, 4, 78 или 0 дочерних узлов, и ваш список "следующий узел" будет иметь накладные расходы на сортировку, вставку и удаление.Намного медленнее.

Я не могу говорить на Java, но если бы я реализовывал пользовательское исходное дерево на C #, я бы использовал одно из встроенных .СЕТЕВЫЕ коллекции.Написание собственного отсортированного списка на самом деле не помогает вам изучить концепции дерева и встроенную оптимизацию .СЕТЕВЫЕ коллекции трудно превзойти.Тогда ваш код будет простым:Найдите свой следующий узел;если существует, хватай его и уходи;если нет, добавьте его в коллекцию next-node.

Какую коллекцию вы используете, зависит от того, что именно вы реализуете через дерево...каждый тип дерева включает в себя компромиссы между временем вставки, временем поиска и т.д.Выбор, который вы делаете, зависит от того, что наиболее важно для приложения, а не от дерева.

Есть смысл?

Answer 2

Какую структуру данных я бы использовал для хранения указателей на каждый из узлов?

Узел.Каждый узел должен иметь ссылки на (до) 26 других Узлов в Дереве.Внутри узла вы можете хранить их в array, LinkedList, ArrayList или практически в любой другой коллекции, о которой вы можете подумать.

Answer 3

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

Использование списка / массива будет означать выполнение некоторого учета индексов для обхода дерева, поэтому, возможно, проще всего просто сохранить ссылки на дочерние элементы в родительском элементе.

Answer 4

Вот один из них, который я недавно нашел, который является неплохим API для деревьев - хотя мне нужны были графики, было удобно посмотреть, как он был настроен для разделения структуры данных для данных, которые он содержал, чтобы у вас мог быть древовидный эквивалент итератора для навигации по дереву и так далее.

https://jsfcompounds.dev.java.net/treeutils/site/apidocs/com/truchsess/util/package-summary.html

Answer 5

Если вас на самом деле больше интересует скорость, чем пространство, и если каждый узел представляет ровно одну букву (подразумевается ваше максимальное значение 26), то я бы просто использовал простой массив из 26 слотов, каждый из которых ссылается на "Узел" (узел - это объект, содержащий ваш массив).

Самое приятное в массиве фиксированного размера то, что ваш поиск будет намного быстрее.Если бы вы искали символ "c", который уже гарантированно был бы строчной буквой, поиск был бы таким же простым, как:

nextNode=nodes[c-'a'];

Рекурсивный поиск строки был бы тривиальным.

Answer 6

Спасибо за быстрые ответы.

Да, сногфиш сказал, что это правильно.По сути, это дерево с 26 узлами (A-Z) + bool isTerminator.

Каждый узел имеет эти значения, и они связаны друг с другом.

Я еще не изучил указатели подробно, поэтому мои сегодняшние попытки реализовать это с нуля, используя небезопасный код на C #, где это бесполезно.

Поэтому я был бы признателен, если бы кто-нибудь мог предоставить мне код для начала работы на C # с использованием внутреннего класса tree.Как только я смогу это запустить, я смогу перенести алгоритмы на другие языки и просто изменить их, чтобы использовать указатели.

Большое спасибо, Майкл

Answer 7

Ознакомьтесь с этим блогом Симеона Пилигрима, "Обзор головоломки Code Camp".Одно из решений использует радиус в C #, и вы можете загрузить решение.