BFS в двоичном дереве

Question

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

Вот мой код в C:

void breadthFirstSearch (btree *bt, queue **q) {
   if (bt != NULL) {

      //store the data to queue if there is

      if (bt->left != NULL) enqueue (q, bt->left->data);
      if (bt->right != NULL) enqueue (q, bt->right->data);

      //recursive

      if (bt->left != NULL) breadthFirstSearch (bt->left, q);
      if (bt->right != NULL) breadthFirstSearch (bt->right, q);
   }
}

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

Answer 1

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

void BFS(btree *start)
{
    std::deque<btree *> q;
    q.push_back(start);
    while (q.size() != 0)
    {
        btree *next = q.front();
        // you may want to print the current node here or do other processing
        q.pop_front();
        if (next->left)
            q.push_back(next->left);
        if (next->right)
            q.push_back(next->right);
    }
}

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

Обратите внимание, что я использую здесь деку C ++, но все, что позволяет вам размещать элементы сзади и получать их спереди, будет работать нормально.

Answer 2

void bfs_bintree (btree_t *head)
{
  queue_t *q;
  btree_t *temp;

  q = queue_allocate ();
  queue_insert (q, head);

  while (!queue_is_empty (q))
  {
    temp = queue_remove (q);

    if (temp->left)
      queue_insert (temp->left);

    if (temp->right)
      queue_insert (temp->right);
  }
  queue_free (q);
  return;
}

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

                                A
                               / \
                              /   \
                             B     C
                            / \     \
                           /   \     \
                          D     E     F
                         / \         / \
                        /   \       /   \
                       G     H     I     J


iteration  Vertex Selection Discovery Queue State
 initial                    :  A
    1            A          :  B C     {A is removed and its children inserted}
    2            B          :  C D E   {B is removed and its only child inserted}
    3            C          :  D E F   {C is removed and its children inserted}
    4            D          :  E F G H {D is removed and its children inserted}
    5            E          :  F G H   {E is removed and has not children}
    6            F          :  G H I J {F is removed and its children inserted}
    7            G          :  H I J   {G is removed has no children}
    8            H          :  I J     {H is removed has no children}
    9            I          :  J       {I is removed has no children}
    10           J          :  (empty) {J is removed has no children}

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

В вашем коде сначала вы ставите в очередь узлы в очереди, а затем рекурсивно перебираете эти дочерние элементы, что создает шаблон DFS. Если вам нужно выполнить рекурсию, вам нужно проверить, пуста ли очередь, как базовое условие. Также проверьте, как вы проходите очередь, я думаю, что это может быть неправильно. Я бы предложил итеративное решение.

Answer 3

Вы не делаете здесь первый проход в ширину. Вместо этого вы ставите в очередь левый и правый элемент внутри очереди и переходите к левому поддереву. Сначала вы исчерпываете левое поддерево, а затем переходите к правому поддереву.

Напишите процедуру для постановки в очередь узла.

void breadthFirstSearch (btree *bt, queue **q) {
 btree *tmpNode;
 enqueue(q,bt); //Assuming your root node has data

 while (!isempty(q)) //Assume isempty returns false when queue is not empty
 {
  tmpNode = dequeue(q);
  //Do whatever you want to do with tmpNode->data
  enqueue(tmpNode->left);
  enqueue(tmpNode->right);
  /* If this is a acyclic graph(tree) then this procedure should do, else you have to mark the nodes you have visited in-order not to end in a cycle */
 }

}

int main()
{
breadthFirstSearch(bt,q)
return 0
}