Что означает «дерево» в поисках по ширине и глубине?

Question

Мне нужны некоторые рабочие фрагменты кода C ++, касающиеся поиска в ширину / глубину.Кроме того, в ссылках ниже, когда используется термин «дерево», относится ли он к двоичному дереву или, более конкретно, к красно-черному дереву?Или это более абстрактное дерево?У кого-нибудь есть ссылка на рабочий код для этих поисков ... наряду с построением дерева?

Дерево, кажется, ссылается на какую-то конструкцию с "графом"?Я считаю, что это какая-то математика, которую я еще не изучал.

поиск в ширину или глубину 1

поиск в ширину или глубину 2

Answer 1

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

Дерево - это тип графа.График представляет собой серию узлов (которые предположительно представляют некоторые данные) со связями между определенными узлами.Дерево - это граф, в котором связи между узлами образуют иерархию.Для любого данного узла в графе у него есть ровно один «родитель», который указывает на него, и он указывает на ноль или более дочерних узлов.И узлы не могут образовывать круги;родитель не может указывать на ребенка, который указывает на этого родителя.

В основном, как ветви на дереве.

Answer 2

Дерево - это особый случай направленного ациклического графа (по сути, это группа «узлов» со стрелками («ребрами»), указывающими друг на друга, так что не может быть петли стрелок) в котором выполняются следующие два условия:

• Ни один узел не имеет более одного входящего фронта
• Существует один выделенный узел («корень»), из которого достижимы все остальные узлы.

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

Поиск в ширину и в глубину применяется к родовым деревьям (действительно, они применяются ко всем группам DAG). Однако есть несколько более специфических типов:

• Бинарные деревья - это деревья, в которых ни один узел не имеет более двух исходящих ребер; исходящие ребра помечены, как правило, «левым» и «правым»
• Деревья поиска - это двоичные деревья, в которых каждый узел имеет ключ; кроме того, ключ в некотором узле N больше, чем дочерний элемент на его левом краю (если есть), и меньше, чем дочерний элемент на его правом краю (если таковой имеется). Это позволяет очень быстро искать конкретный ключ.
• Красно-черные деревья - это особый вид дерева поиска, в котором умеренно сложный алгоритм используется для того, чтобы все ключи находились примерно на одинаковом расстоянии от корня.

Answer 3

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

«Дерево» - это структура данных, в которой есть родительские узлы и дочерние узлы, и у каждого дочернего элемента есть один родительский элемент, а у одного «корневого» узла нет родителя.

Если узел в вашем дереве имеет несколько родителей, он называется «граф».