0
Refer to the following code and example output below.
#include<iostream>
#include<time.h>
#include<queue>
#include<stack>
class tree
{
private:
struct node
{
static unsigned s_id; // static id
unsigned id; // instance id
unsigned data; // instance data
unsigned depth; // depth of node
node* left; // pointer to left node (may be NULL)
node* right; // pointer to right node (may be NULL)
node (unsigned num, unsigned depth): data (num), left (NULL), right (NULL), id (s_id++), depth (depth) {}
~node () { delete (left); delete (right); }
void insert (unsigned num)
{
if (num < data)
{
if (!left)
left = new node (num, depth+1);
else
left->insert (num);
}
else
{
if (!right)
right = new node (num, depth+1);
else
right->insert (num);
}
}
void print ()
{
std::cout<<"ID: "<<id<<" Depth: "<<depth<<" Data: "<<data<<std::endl;
}
void print_sorted ()
{
if (left)
left->print_sorted ();
print();
if (right)
right->print_sorted ();
}
};
node* m_root;
public:
tree (): m_root (NULL) {}
~tree (){ delete (m_root); }
void insert (unsigned num)
{
if (!m_root)
m_root = new node (num, 0);
else
m_root->insert (num);
}
void print_sorted ()
{
std::cout<<"Sorted-order traversal\n"<<std::endl;
if (m_root)
{
m_root->print_sorted ();
std::cout<<std::endl;
}
}
void print_breadth_first ()
{
std::cout<<"Breadth-first traversal\n"<<std::endl;
std::queue<node*> q;
if (m_root)
{
// enque the root
q.push (m_root);
// repeat while the queue is not empty
while (!q.empty ())
{
// dequeue the first node
node* n = q.front ();
q.pop ();
// report the node
n->print ();
// enqueue left and right nodes
if (n->left)
q.push (n->left);
if (n->right)
q.push (n->right);
}
std::cout<<std::endl;
}
else
std::cout<<"The tree is empty!\n"<<std::endl;
}
void print_depth_first ()
{
std::cout<<"Depth-first traversal\n"<<std::endl;
std::stack<node*> s;
if (m_root)
{
// stack the root
s.push (m_root);
// repeat while the stack is not empty
while (!s.empty())
{
// unstack the top node
node* n = s.top ();
s.pop ();
// report the node
n->print ();
// stack left and right nodes
if (n->right)
s.push (n->right);
if (n->left)
s.push (n->left);
}
std::cout<<std::endl;
}
else
std::cout<<"The tree is empty!\n"<<std::endl;
}
};
// initialise static data
unsigned tree::node::s_id = 0;
int main()
{
srand((unsigned) time(NULL));
// create tree with 10 random numbers
tree t;
for(unsigned i=0; i<10; ++i)
t.insert (rand ());
t.print_sorted ();
t.print_breadth_first ();
t.print_depth_first ();
}
Example output:
Sorted-order traversal
ID: 6 Depth: 2 Data: 334
ID: 4 Depth: 1 Data: 2335
ID: 0 Depth: 0 Data: 12490
ID: 5 Depth: 4 Data: 15590
ID: 9 Depth: 5 Data: 18484
ID: 3 Depth: 3 Data: 23160
ID: 2 Depth: 2 Data: 23786
ID: 8 Depth: 3 Data: 24171
ID: 1 Depth: 1 Data: 24598
ID: 7 Depth: 2 Data: 30731
Breadth-first traversal
ID: 0 Depth: 0 Data: 12490
ID: 4 Depth: 1 Data: 2335
ID: 1 Depth: 1 Data: 24598
ID: 6 Depth: 2 Data: 334
ID: 2 Depth: 2 Data: 23786
ID: 7 Depth: 2 Data: 30731
ID: 3 Depth: 3 Data: 23160
ID: 8 Depth: 3 Data: 24171
ID: 5 Depth: 4 Data: 15590
ID: 9 Depth: 5 Data: 18484
Depth-first traversal
ID: 0 Depth: 0 Data: 12490
ID: 4 Depth: 1 Data: 2335
ID: 6 Depth: 2 Data: 334
ID: 1 Depth: 1 Data: 24598
ID: 2 Depth: 2 Data: 23786
ID: 3 Depth: 3 Data: 23160
ID: 5 Depth: 4 Data: 15590
ID: 9 Depth: 5 Data: 18484
ID: 8 Depth: 3 Data: 24171
ID: 7 Depth: 2 Data: 30731
Each node reports its ID, depth and data. The ID tells us the sequence the nodes were created, where the node with ID 0 is always the root. The depth tells us the level within the tree where the node exists, such that the root is on level 0. With this information it is possible to draw a graph of the tree and thus better understand the order in which nodes are processed.
The first listing shows the nodes in ascending order by data. With binary search trees this is the normal method of traversal.
The second listing shows a breadth-first traversal, where each level is processed in turn, from left to right.
The final listing shows a depth-first traversal where we follow left nodes before right nodes.
You will notice that the implementation of breadth-first and depth-first are fairly similar, the only real difference being that breadth-first employs a queue while depth-first employs a stack. The nature of a stack also means we must push right nodes before left nodes to ensure left nodes are processed before right nodes.
At first glance there doesn't appear to be much merit in either breadth-first or depth-first traversal. However, the example merely serves to show the difference between all the methods of traversal. When considering more complex graphs or maps, it may be advantageous to search through all the vertices that form an edge with a particular vertex (breadth-first) or to examine all the edges between one vertex and another vertex, where several routes might be available (depth-first). Both depth-first and breadth-first have practical applications in network routing and satellite navigation, where maps and charts must be graphed and traversed in a more logical manner than would otherwise be possible with sorted-order traversal.
What else can I help you with?
Which of the following traversal is used for printing the keys of binary search tree in ascending order?
In order traversal is used.
In depth first traversal of a graph G with n vertices k edges are marked as tree edges the no of connected components in G is?
n-k-1
How do you print all data in a Binary Search Tree?
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
Explain non-recursive and recursive algorithm for postorder traversal on binary tree?
Step 1:- select first root node (t), start travelsing left contin
What is the advantages of depth first search?
advantages of depth first search?
Which of the following traversal is used for printing the keys of binary search tree in ascending order?
In order traversal is used.
In depth first traversal of a graph G with n vertices k edges are marked as tree edges the no of connected components in G is?
n-k-1
How do you print all data in a Binary Search Tree?
By using Depth First Search or Breadth First search Tree traversal algorithm we can print data in Binary search tree.
Explain non-recursive and recursive algorithm for postorder traversal on binary tree?
Step 1:- select first root node (t), start travelsing left contin
What is the process and significance of implementing breadth first search in a graph traversal algorithm?
Breadth-first search is a graph traversal algorithm that explores all the neighboring nodes at the current depth before moving on to nodes at the next depth. This process continues until all nodes have been visited. Implementing breadth-first search helps in finding the shortest path between two nodes in a graph. It is significant because it guarantees the shortest path and can be used in various applications such as network routing, social network analysis, and web crawling.
What is the difference between backtracking and depth-first search (DFS) in terms of their approach to problem-solving?
Backtracking is a general algorithmic technique that involves systematically trying all possible solutions to find the correct one, while depth-first search (DFS) is a specific graph traversal algorithm that explores as far as possible along each branch before backtracking. In essence, backtracking is a broader concept that can be used in various problem-solving scenarios, while DFS is a specific application of backtracking in graph traversal.
Where is iterative deepening search worse than depth-first?
Iterative deepening will preform much worse than depth first when the desired nodes show up early in pre-order traversal of the graph. This means that on most diagrams the desired nodes would be in the bottom left. Depth first will find these almost immediately however iterative deepening will be forced to expand all nodes above the desired level first, significantly slowing down the find time.
Explain the difference between depth first and breadth first traversing techniques of a graph?
In depth first traversing, the node that is below the current node is considered first. For breadth first traversing, the node to the rightmost of the current mode is considered.
What will be the root node of The preorder traversal is 5 3 66 30 77 70?
In preorder traversal, the root node is always visited first. The value of the root node in this case is 5.
What is the difference between BFS and DFS?
BFS: This can be throught of as being like Dijkstra's algorithm for shortest paths, but with every edge having the same length. However it is a lot simpler and doesn't need any data structures. We just keep a tree (the breadth first search tree), a list of nodes to be added to the tree, and markings (Boolean variables) on the vertices to tell whether they are in the tree or list. Depth first search is another way of traversing graphs, which is closely related to preorder traversal of a tree. Recall that preorder traversal simply visits each node before its children. It is most easy to program as a recursive routine:
What is the algorithm DFS and BFS in graph traversal?
DFS and BFS stands for Depth First Search and Breadth First Search respectively. In DFS algorithm every node is explored in depth; tracking back upon hitting an already visited node and starts visiting from a node which has any adjacent nodes unvisited. In BFS, the nodes are visited level wise. These algorithms are used to traverse the nodes on a connected digraph. Primal
What graph traversal algorithm uses a queue to keep track of vertices which need to be processed?
Breadth-first search
