BFS in binary tree

Question

I am trying to write width search codes in a binary tree. I saved all the data in the queue, but I can’t figure out how to navigate all the nodes and consume all of their children.

Here is my code in 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); } } 

I already installed the root data, but it still does not work. Can anyone point out my mistake?

Answer 1

BFS can be easily written without recursion. Just use the queue to order your extensions:

 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); } } 

The key is that you do not need to traverse the tree recursively; you just let your data structure handle the order in which you visit the nodes.

Please note that I am using C ++ deque here, but anything that allows you to put elements on the back and get them in front will work fine.

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; } 

First, the head node is inserted into the queue. The loop will repeat until the queue is empty. Starting with the head of a node, at each iteration one node is deleted and non-zero children are placed in the queue. At each iteration, a node is selected, and its non-bubble children are discarded. At the next iteration, the next old found vertex, which is now in the front of the queue, is taken out (in the order they were found), and then processed to check their child.

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

Above the iteration, it stops when we get that there is no more open vertex in the queue waiting to be selected, therefore all vertices found in the binary tree (the component associated with the graph) are selected.

I first pass your code to the queue of the nodes in the queue, and then recursively traverse these children, which creates a DFS template. If you need to do a recursion, you need to check if there is a queue as a basic condition. Also check how you go through the queue, I think this might be wrong. I would suggest an iterative solution.

Answer 3

Here you do not make the first pass. Instead, you insert the left and right elements inside the queue and move to the left subtree. First, you exhaust the left subtree, and then move on to the correct subtree.

Write a procedure to host the node.

 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 }