4

Пишу работу по деревьям в теории графов и немного запутался в понятиях. Мне нужно написать, какие существуют виды деревьев или классификацию деревьев. Я нашел что существует: ориентированное/неориентированное дерево, остовное, лес, бинарное, n-мерное, упорядоченное дерево. Но это всё больше похоже на свойства деревьев нежели на виды (кроме бинарного и n-мерного).

Что из этого (если я правильно нашел и ничего не пропустил) действительно будет являться отдельным видом дерева? Также, есть например частный случай бинарного дерева - дерево поиска. Будет ли такое дерево относиться к теории графов или это больше структура данных в программировании? Тот же вопрос с деревом синтаксического анализа. И последний вопрос: относится ли обход дерева к операциям с деревьями как графами или это алгоритм для структуры данных - дерево?

1 ответ 1

5

Раз вы пишите какую-то работу на тему деревьев, то лучше как можно более полно изложить материал.

Часть того, что вы перечислили - общие понятия для графов, часть - понятия для деревьев.

Я бы на вашем месте сделал классификацию по признакам:

По направленности - ориентированное (однонаправленное, двунаправленное), неориентированное

По степени вершины (бинарное, n-арное, и т.п.)

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

Поскольку дерево является графом, то к нему применимы классические алгоритмы обхода любого графа, но помимо этого существуют специфичные алгоритмы именно для деревьев.

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

1
  • Спасибо вам большое! Вы ответили мне на все возникшие вопросы.
    – JohnS
    21 мар 2016 в 9:18

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.