Question

Data Structures(2nd Edition Using JAVA Chapter Review, Problem 6PP does not provide an answer: "The Problem...

Data Structures(2nd Edition Using JAVA Chapter Review, Problem 6PP does not provide an answer: "The Problem Statement is as follows": In a breadth-first traversal of a binary tree, the nodes are visited in an order prescribed by their level. First visit the node at level 1, the root node. Then visit the nodes at level 2, in left-to-right order, and so on. You can use a queue to implement a breadth-first traversal of a binary tree". Algorithm for Breath-First Traversal of a Binary Tree: 1. Insert the root node in the queue. 2. While the queue is 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. The answer needs to be written in JAVA since the text book is for "Using JAVA". Since this problem is in Chapter 6 it needs to use "Trees" The answer should not only provide the Driver and Main class, but a BinaryTree and a BinarySearchTree class and any SearchTrees classes needed.

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Hello, I have done the question and it is working perfectly fine. I have tried to name the variables in a proper manner to give you a better understanding for the code. I am also attaching the sample input/output file as well. It took me a lot of time to answer this. I have properly commented the code too. Please give me an upvote.

Please note that you have not mentioned anything about the binarySearchTree class so I am leaving that for now.

import java.util.Queue;
import java.util.LinkedList;

class TreeNode {
   int data;
   TreeNode left, right;

   public TreeNode(int item) {
       data = item;
       left = null;
       right = null;
   }
}

class BinaryTree {

   TreeNode rootNode;
  
   void breadthFirstTraversal()
   {
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
      
       //First added the rootNode to the queue
       queue.add(rootNode);
       while (!queue.isEmpty()) //till the queue is empty dequeue it
       {
           TreeNode tempNode = queue.poll(); //dequeue the element of queue
          
           System.out.print(tempNode.data + " "); //print the data of that node

//Put the left and right child of that node into the queue
           if (tempNode.left != null) {
               queue.add(tempNode.left);
           }
          
           if (tempNode.right != null) {
               queue.add(tempNode.right);
           }
       }
   }

   public static void main(String args[])
   {
       BinaryTree bt = new BinaryTree(); //declaring a BinaryTree
      
       //adding nodes to the BinaryTree
       bt.rootNode = new TreeNode(1);
       bt.rootNode.left = new TreeNode(2);
       bt.rootNode.left.left = new TreeNode(3);
      

       System.out.println("Breadth first traversal of BinaryTree -- ");
       bt.breadthFirstTraversal();
   }
}

Sample input/output files:-

A normal tree:-

A skew tree with only left child:-

Add a comment
Know the answer?
Add Answer to:
Data Structures(2nd Edition Using JAVA Chapter Review, Problem 6PP does not provide an answer: "The Problem...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • Data Structures(2nd Edition Using JAVA Chapter Review, Problem 6PP does not provide an answer: "T...

    Data Structures(2nd Edition Using JAVA Chapter Review, Problem 6PP does not provide an answer: "The Problem Statement is as follows": In a breadth-first traversal of a binary tree, the nodes are visited in an order prescribed by their level. First visit the node at level 1, the root node. Then visit the nodes at level 2, in left-to-right order, and so on. You can use a queue to implement a breadth-first traversal of a binary tree". Algorithm for Breath-First Traversal...

  • using java to write,show me the output. please write some common. You CAN NOT use inbuild...

    using java to write,show me the output. please write some common. You CAN NOT use inbuild functions for Tree ADT operations. using code below to finsih public class Main {    public static void main(String[] args) {        BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(2); tree.root.right = new Node(3); tree.root.left.left = new Node(4); tree.root.left.right = new Node(5); tree.root.right.left = new Node(6); tree.root.right.right = new Node(7); tree.root.left.left.left = new Node(8); tree.root.left.left .right= new Node(9);...

  • In Java. How would this method look? LinkedBinaryTree.java import java.util.Iterator; public class LinkedBinaryTree implements BinaryTreeADT {...

    In Java. How would this method look? LinkedBinaryTree.java import java.util.Iterator; public class LinkedBinaryTree implements BinaryTreeADT {    private BinaryTreeNode root;    /**    * Creates an empty binary tree.    */    public LinkedBinaryTree() {        root = null;    }    /**    * Creates a binary tree from an existing root.    */    public LinkedBinaryTree(BinaryTreeNode root) {        this.root = root;    }    /**    * Creates a binary tree with the specified element...

  • QUESTION 8   In the _____ traversal, the root is processed first, before its subtrees. breadth first...

    QUESTION 8   In the _____ traversal, the root is processed first, before its subtrees. breadth first preorder postorder inorder 0.10000 points    QUESTION 9 What kind of traversal does the following algorithm (in pseudo-code) describe? Algorithm traversal (root) if (root is not null)      traversal (leftSubTree)      process (root)      traversal (rightSubTree) end if end traversal breadth first preorder inorder postorder 0.10000 points    QUESTION 10 What kind of traversal does the following algorithm (in pseudo-code)  describe? Algorithm traversal (root) if...

  • Would appreciate the answer in the Java coding language please and thank you! 10d 10h left...

    Would appreciate the answer in the Java coding language please and thank you! 10d 10h left Java 7 1. Check the Structure Autocomplete Ready 1 > import java.io.*;... 10 ALL A binary tree uses a multi-node data structure where each node may have 0 to 2 child nodes, and has one stored value, its node number in this case. A tree may either be: 11 class Result { * Complete the 'isValid' function below. • An empty tree, the root...

  • Scenario Implement an algorithm that searches the binary tree one level at a time, left to...

    Scenario Implement an algorithm that searches the binary tree one level at a time, left to right. The traversal starts from the root node and finishes at the leaf node. Aim Apply BFS traversal in Java. Steps for Completion Implement the psuedocode algorithm from Snippet 3.14 (shown below) in a public method called printBfs()in SimpleBinaryTree. The return value should be void and it should print each node on a newline. breadthFirstSearch(root) if (root != null) queue = createQueue() enqueue(queue, root)...

  • Previous code: class BinarySearchTree: def __init__(self, data): self.data = data self.left = None self.right = None de...

    Previous code: class BinarySearchTree: def __init__(self, data): self.data = data self.left = None self.right = None def search(self, find_data): if self.data == find_data: return self elif find_data < self.data and self.left != None: return self.left.search(find_data) elif find_data > self.data and self.right != None: return self.right.search(find_data) else: return None    def get_left(self): return self.left def get_right(self): return self.right def set_left(self, tree): self.left = tree def set_right(self, tree): self.right = tree def set_data(self, data): self.data = data def get_data(self): return self.data def traverse(root,order):...

  • 1. Given the two binary trees below: 14 16 Write a method called swapSubtrees, which swaps all of...

    in java ..write all complete program from a- e 1. Given the two binary trees below: 14 16 Write a method called swapSubtrees, which swaps all of the left and right subtrees in the above binary trees. Add this method to the class BinaryTree and create a program to test this method for these 2 trees. Show the original trees and the resulting trees. Note: To test your algorithm, first create a binary search tree. Write a method called singleParent,...

  • please do this lab in Java in given instructions by tomorrow morning. TkA CHRI - TREE...

    please do this lab in Java in given instructions by tomorrow morning. TkA CHRI - TREE UTH A HEAPOF PRESDNS CENETH CSC 236-Lab 6 (2 programs) trees 1. Given the two binary trees below: 14 18 16) Write a method called swapSubtrees, which swaps all of the left and right subtrees in the above binary trees. Add this method to the class BinaryTree and create a program to test this method for these 2 trees. Show the original trees and...

  • java data structures and algorithms    binary trees part thank you very much Dagger Given a binary...

    java data structures and algorithms    binary trees part thank you very much Dagger Given a binary tree and a sum, the method has PathSum determines if the tree has a squareroot-to-leaf path such that adding up all the key values along the path equals the given sum. It uses an auxiliary method which takes the squareroot of the given tree to do its job as follows: public boolean hasPathSum(int sum){ return hasPathSum(root, sum); } Given the following tree where the...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT