Тестирование круглости дерева?

Question

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

Я уже несколько часов пытаюсь найти рекурсивную функцию, ноЯ просто не могу этого понять.У меня не так много работы, чтобы показать это тоже.Может кто-нибудь дать мне несколько идей о том, как я могу это сделать?Язык, который мы используем: C.

Спасибо.

Answer 1

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

Если вы когда-нибудь пойдете по указателю и достигнете узла, который вы уже пометили как посещенный, то у вас есть цикл.

Как насчет того, чтобы сделать это рекурсивно:

struct node {
    struct node *left;
    struct node *right;
    bool visited;
};

bool check_tree(struct node *cur)
{
    if (cur == NULL)
        return true;

    if (cur->visited)
        return false; // uh oh. We've been here...
    cur->visited = true;
    return check_tree(cur->left)
           && check_tree(cur->right);
 }

 if (check_tree(&root))
     printf("No self-references here.\n");

(предупреждение: код может содержать ошибки)

Answer 2

Алгоритм Флойда «Черепаха и заяц» должен решить эту проблему очень элегантно. Пожалуйста, смотрите здесь: http://en.wikipedia.org/wiki/Cycle_detection

Он идеально подходит для списков, но также может быть адаптирован для обхода дерева, как графики.

Answer 3

Вы захотите проверить алгоритм Topological Sort .

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

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    **output error message (graph has at least one cycle)**
else 
    output message (proposed topologically sorted order: L)

РЕДАКТИРОВАТЬ:

Этот ответ был опубликован до того, как автор указал, что он в основном имеет структуру двойного связанного списка. Я разместил его не потому, что думаю, что это будет самый эффективный ответ во всех случаях, а потому что, учитывая наше отсутствие информации о его графике (кроме описания его в виде «дерева»), этот ответ должен обрабатывать большинство случаев.