in breadth-first traversal of binary tree, the nodes are visited in an order pre
ID: 3813876 • Letter: I
Question
in breadth-first traversal of binary tree, the nodes are visited in an order prescribed by their level. first vist the node at level 1, the root node. then visit the nodes at level 2, in left-to-right orderand so on. you can use a queue to implement a breadth-first traversal of a binary tree
Algorithm for Breadth-first Traversal of a binary tree
1. Insert the root node in queue
2. WHILE the queue in not empty
3. remove a node from the queue and visit it.
4. place references to its left and right subtrees in the queue
code this algorithm and test it on several binary trees.
Explanation / Answer
TREE TRAVERSAL:
Tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting (checking and/or updating) each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited.
Breadth-first search:
Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This search is referred to as breadth-first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.
Depth-first is not the only way to go through the elements of a tree. Another way is to go through them level-by-level.
For example, each element exists at a certain level (or depth) in the tree:
tree
----
j <-- level 0
/
f k <-- level 1
/
a h z <-- level 2
d <-- level 3
So, if we want to visit the elements level-by-level (and left-to-right, as usual), we would start at level 0 with j, then go to level 1 for f and k, then go to level 2 for a, h and z, and finally go to level 3 for d.
This level-by-level traversal is called a breadth-first traversal because we explore the breadth, i.e., full width of the tree at a given level, before going deeper.
Now, how might we traverse a tree breadth-first? We'll need some other mechanism than the ones we've already used since preorder, inorder and postorder traversals don't produce breadth-first order.
Using one data structure to implement another:
The organization of a program that uses a breadth-first traversal might look like:
main program tree.h tree.c
------------ ------ ------
call TreeBreadthFirst TreeBreadthFirst
TreeBreadthFirst prototype definition
In other words, the main program needs to call some function that performs a breadth-first traversal, like TreeBreadthFirst(). This means that the interface (tree.h) must provide a prototype for such a function. Also, the implementation (tree.c), which the main program has no direct access to, must define the function TreeBreadthFirst().
If we use a queue to help us implement the breadth-first traversal, then we must extend the picture...
... tree.c queue.h queue.c
------ ------- -------
... TreeBreadthFirst queue funcs. queue funcs.
definition (uses prototypes definitions
a queue)
The tree implementation will use types and functions from the queue interface. The queue implementation will provide definitions for those functions, but they are hidden from the user of the queue--here, the user of the queue is the tree implementation!
Finally, since the main program cannot see the implementation of the tree, it won't even know that a queue is involved and won't have any access to that queue.
Connecting the queue to the tree:
Previously, we've seen that the following organization of types can be used for a tree of characters:
tree.h tree.c
------ ------
#include "tree.h"
#include "queue.h"
typedef char treeElementT; typedef struct treeNodeTag {
treeElementT element;
struct treeNodeTag *left,
*right;
} treeNodeT;
typedef struct treeCDT typedef struct treeCDT {
*treeADT; treeNodeT *root;
} treeCDT;
The one adjustment needed is that the tree implementation will have to include queue.h, since it uses a queue.
Now, the types for a queue have similar organization:
queue.h queue.c
------- -------
#include "queue.h"
type-of-an-element
abstract-type-of-a-queue concrete-type-of-a-queue
C Program to Display the Nodes of a Tree using BFS Traversal.
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *left, *right;
};
typedef struct btnode node;
/* function declarations */
void insert(node *, node *);
void bfs_traverse(node *);
/*global declarations */
node *root = NULL;
int val, front = 0, rear = -1, i;
int queue[20];
void main()
{
node *new = NULL ;
int num = 1;
printf("Enter the elements of the tree(enter 0 to exit) ");
while (1)
{
scanf("%d", &num);
if (num == 0)
break;
new = malloc(sizeof(node));
new->left = new->right = NULL;
new->value = num;
if (root == NULL)
root = new;
else
{
insert(new, root);
}
}
printf("elements in a tree in inorder are ");
queue[++rear] = root->value;
bfs_traverse(root);
for (i = 0;i <= rear;i++)
printf("%d -> ", queue[i]);
printf("%d ", root->right->right->right->value);
}
/* inserting nodes of a tree */
void insert(node * new , node *root)
{
if (new->value>root->value)
{
if (root->right == NULL)
root->right = new;
else
insert (new, root->right);
}
if (new->value < root->value)
{
if (root->left == NULL)
root->left = new;
else
insert (new, root->left);
}
}
/* displaying elements using BFS traversal */
void bfs_traverse(node *root)
{
val = root->value;
if ((front <= rear)&&(root->value == queue[front]))
{
if (root->left != NULL)
queue[++rear] = root->left->value;
if (root->right != NULL || root->right == NULL)
queue[++rear] = root->right->value;
front++;
}
if (root->left != NULL)
{
bfs_traverse(root->left);
}
if (root->right != NULL)
{
bfs_traverse(root->right);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.