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.
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:-
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...
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 { 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 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 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 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 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):...
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 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 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...