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

Question

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

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

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

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

Спасибо

Answer 1

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

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

Answer 2

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

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

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

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

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

Большое спасибо, Michael

Answer 3

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

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

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

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

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

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

Имеет смысл?

Answer 4

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

Приятной особенностью массива фиксированного размера является то, что ваш поиск будет намного быстрее. Если бы вы искали символ «с», который уже гарантированно был буквой в нижнем регистре, поиск был бы так же прост:

nextNode=nodes[c-'a'];

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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