Как указать предварительный порядок связующего дерева с помощью алгоритма BFS

Question

Я делаю реализацию алгоритма BFS в C ++, чтобы найти связующее дерево, вывод для связующего дерева должен быть показан в предзаказе, но у меня есть сомнения в реализации, как я могу построить дерево, если нетточно знать, сколько детей у каждого узла?Учитывая рекурсивную древовидную структуру. Структура данных дерева может быть записана в виде:

typedef struct node 
{
        int val;
        struct node *left, *right;
}*tree; //tree has been typedefed as a node pointer.

Но не думайте, что эта реализация работает, как упоминалось ранее.

Это моя функция для возвратаДерево в предварительном порядке:

void preorder(tree t) 
{
        if(t == NULL)
                return;
        printf("%d ", t->val);
        preorder(t->left);
        preorder(t->right);
}

Мне также интересно, есть ли способ сделать предварительный порядок узлов без использования древовидной структуры.

Answer 1

Я видел два конкретных вопроса в посте:

1. Возможно ли иметь структуру данных, использующую более двух дочерних элементов в дереве? Конечно, это возможно. Интересно, что это возможно даже при размещенной вами структуре узлов! Просто считайте указатель left указателем на первый дочерний элемент, а указатель right - указателем на следующего родного брата. Так как поиск в графе в ширину неявно создает остовное дерево, вы можете пройти по этому дереву в предзаказе, если вы действительно представляете его каким-либо образом.
2. Можете ли вы пройти предварительный заказ, не используя древовидную структуру? Да, это тоже возможно. По сути, DFS и BFS концептуально не отличаются для этого: у вас просто есть структура данных, поддерживающая следующие узлы, которые будут посещаться. Для DFS это стек, для BFS это очередь. Вы получаете предварительный обход дерева (то есть вы посещаете все дочерние узлы после родительского), если вы выделяете номер узла, когда вставляете его в структуру данных, поддерживая посещаемые узлы.

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

Если вы этого не понимаете, вытащите лист бумаги и нарисуйте график и очередь:

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

Теперь выберите узел, который станет начальным узлом поиска, который совпадает с корневым узлом вашего дерева. Запишите его номер в первую пустую позицию в очереди и пометьте, т.е. заполните узел. Теперь приступим к поиску:

• посмотрите на узел, указанный в начале очереди, и найдите соседний узел, который не заполнен:
  • добавить узел в конец очереди (т.е. сразу за последним узлом в прямоугольнике)
  • отметка (т.е. заполнение) узла
  • сделать линию, соединяющую два узла толще: теперь это край дерева
• если больше нет неотмеченных соседних узлов, отметьте передний узел в очереди выключенным (т.е. удалите его из очереди) и переходите к следующему узлу, пока не останется больше узлов

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

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

Просто комментарий к коду: всякий раз, когда вы читаете любой ввод, убедитесь, что вы успешно прочитали данные.Кстати, ваш код явно только на C, а не на C ++: массивы переменной длины недоступны в C ++.В C ++ вы бы использовали std::vector<int> followOrder(vertexNumber) вместо int followOrder[vertexNumber].Интересно, что код тоже не C, потому что он использует, например, std::queue<int>.