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

What data structure would I use to contain the pointers to each of the nodes?

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

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

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

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

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

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

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

nextNode=nodes[c-'a'];

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

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

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

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

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

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

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

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

Есть смысл?

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

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

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

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

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

Огромное спасибо, Майкл