uestion: Define a SC ure, named (bTS 1)wn traverses a binary tree in BFS Order and produces a list of the values of the nodes of the tree in the order in which the nodes were "visited." 5. Another traversal order visits a nodes children before visiting their children (i.e. the node's children's children). This traversal ordering is referred to as Breadth-First Search (BFS) order and is shown in Figure 3. Again, since we are working explicitly with binary trees, there are no cycles in our "graph" and we can safely neglect to record which nodes have been visited already by our algorithm.

Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
icon
Related questions
Question
Needs to be answered using Dr. Racket (R5RS) language. Only Dr. Racket language (R5RS) scheme. No
Java or C++.
Question: Define a SCHEME procedure, named (bfs T)which traverses a binary tree in BFS order and
produces a list of the values of the nodes of the tree in the order in which the nodes were "visited."
5. Another traversal order visits a nodes children before visiting their children (i.e. the node's
children's children). This traversal ordering is referred to as Breadth-First Search (BFS)
order and is shown in Figure 3. Again, since we are working explicitly with binary trees,
there are no cycles in our "graph" and we can safely neglect to record which nodes have
been visited already by our algorithm.
8.
Figure 3: A binary tree showing the order in which nodes are visited in a BFS traversal as the
value at each node.
To implement a function showing BFS traversal of a tree, we use a Queue ADT. In this
case, the root node is enqueued into the Queue ADT. Next, a node is dequeued, that node's
children are enqueued into the queue ADT, and finally the value at the dequeued node is
added to the front of the list obtained by visiting the rest of the nodes in the queue. See
Algorithm 3. Define a SCHEME procedure, named (bfs T) which traverses a binary tree
in BFS order and produces a list of the values of the nodes of the tree in the order in which
the nodes were "visited."
Algorithm 3 BFS Traversal of a Tree
Require: A queue ADT containing the root of the tree to traverse
repeat
dequeue tree node from the queue
if left child of node is not null then
enqueue left child onto queue
end if
if right child of node is not null then
enqueue right child onto queue
end if
"visit" node
until the queue is empty
Transcribed Image Text:Needs to be answered using Dr. Racket (R5RS) language. Only Dr. Racket language (R5RS) scheme. No Java or C++. Question: Define a SCHEME procedure, named (bfs T)which traverses a binary tree in BFS order and produces a list of the values of the nodes of the tree in the order in which the nodes were "visited." 5. Another traversal order visits a nodes children before visiting their children (i.e. the node's children's children). This traversal ordering is referred to as Breadth-First Search (BFS) order and is shown in Figure 3. Again, since we are working explicitly with binary trees, there are no cycles in our "graph" and we can safely neglect to record which nodes have been visited already by our algorithm. 8. Figure 3: A binary tree showing the order in which nodes are visited in a BFS traversal as the value at each node. To implement a function showing BFS traversal of a tree, we use a Queue ADT. In this case, the root node is enqueued into the Queue ADT. Next, a node is dequeued, that node's children are enqueued into the queue ADT, and finally the value at the dequeued node is added to the front of the list obtained by visiting the rest of the nodes in the queue. See Algorithm 3. Define a SCHEME procedure, named (bfs T) which traverses a binary tree in BFS order and produces a list of the values of the nodes of the tree in the order in which the nodes were "visited." Algorithm 3 BFS Traversal of a Tree Require: A queue ADT containing the root of the tree to traverse repeat dequeue tree node from the queue if left child of node is not null then enqueue left child onto queue end if if right child of node is not null then enqueue right child onto queue end if "visit" node until the queue is empty
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 2 steps

Blurred answer
Knowledge Booster
Types of trees
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education