Question

Here is a picture of a Binary Search Tree. First, construct the Binary Search Tree using...

Here is a picture of a Binary Search Tree.



First, construct the Binary Search Tree using the following BinaryNode as we discussed in class.

public class BinaryNode {
        private int value;
        private BinaryNode leftChild;
        private BinaryNode rightChild;

        public BinaryNode(int value) {
                this.value = value;
                leftChild = null;
                rightChild = null;
        }

        public BinaryNode(int value, BinaryNode leftChild, BinaryNode rightChild)
        {
                this.value = value;
                this.leftChild = leftChild;
                this.rightChild = rightChild;
        }

        public int getValue() {
                return value;
        }

        public void setValue(int value) {
                this.value = value;
        }

        public BinaryNode getLeftChild() {
                return leftChild;
        }

        public void setLeftChild(BinaryNode leftChild) {
                this.leftChild = leftChild;
        }

        public BinaryNode getRightChild() {
                return rightChild;
        }

        public void setRightChild(BinaryNode rightChild) {
                this.rightChild = rightChild;
        }

        @Override
        public String toString() {
                return "BinaryNode: " +
                                "value=" + value;
        }
}

Second, print the nodes in level order, that is, the root node first, then the children of the root node, then the grand-children, etc. It is recommended that you accomplish this by using a queue to store the nodes, printing the first nodes that have been added to the queue.

Your program should print the following when it runs.

42 27 50 21 38 60 33 41 72

Submit the file LevelOrder.java when done.

Homework Answers

Answer #1

//BinaryNode.java

public class BinaryNode {
        private int value;
        private BinaryNode leftChild;
        private BinaryNode rightChild;

        public BinaryNode(int value) {
                this.value = value;
                leftChild = null;
                rightChild = null;
        }

        public BinaryNode(int value, BinaryNode leftChild, BinaryNode rightChild)
        {
                this.value = value;
                this.leftChild = leftChild;
                this.rightChild = rightChild;
        }

        public int getValue() {
                return value;
        }

        public void setValue(int value) {
                this.value = value;
        }

        public BinaryNode getLeftChild() {
                return leftChild;
        }

        public void setLeftChild(BinaryNode leftChild) {
                this.leftChild = leftChild;
        }

        public BinaryNode getRightChild() {
                return rightChild;
        }

        public void setRightChild(BinaryNode rightChild) {
                this.rightChild = rightChild;
        }

        @Override
        public String toString() {
                return "BinaryNode: " +
                                "value=" + value;
        }
}

//BinarySearchTree.java

public class BinarySearchTree{
   private BinaryNode root;
  
   public BinarySearchTree() {
       root = null;
   }
  
   private BinaryNode insert(BinaryNode root,int data) {
       if(root==null)return new BinaryNode(data,null,null);
       if(root.getValue()>data)
           root.setLeftChild(insert(root.getLeftChild(),data));
      
       if(root.getValue() < data)
           root.setRightChild(insert(root.getRightChild(),data));
       return root;
   }
  
   public void insert(int data) {
       root = insert(root , data);
   }
  
   public void levelOrder() {
        if (root == null)
          return;
  
        Queue<BinaryNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);
        while (!queue.isEmpty()) {
  
          BinaryNode curr = queue.poll();
          if (curr == null) {
            if (!queue.isEmpty()) {
              queue.add(null);
            }
          } else {
            if (curr.getLeftChild() != null)
              queue.add(curr.getLeftChild());
  
            if (curr.getRightChild() != null)
              queue.add(curr.getRightChild());
  
            System.out.print(curr.getValue() + " ");
          }
        }
      }
}

//LevelOrder.java

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

public class LevelOrder {
   public static void main(String arg[]) {
       //42 27 50 21 38 60 33 41 72
       BinarySearchTree bst = new BinarySearchTree();
       bst.insert(42);
       bst.insert(27);
       bst.insert(50);
       bst.insert(21);
       bst.insert(38);
       bst.insert(60);
       bst.insert(33);
       bst.insert(41);
       bst.insert(72);
      
       bst.levelOrder();
   }
}

Know the answer?
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
Similar Questions
You are given a reference to the root node of a binary search tree, that implements...
You are given a reference to the root node of a binary search tree, that implements a dictionary data structure. Please print all the elements in depths 500 through 510, all in sorted order. A node in a binary search tree is at depth x, if it takes x hops to get from the root. So the root is at depth 0, the children of the root are at depth 1, and so on. The class TreeNode defines a single...
In this lab, you will write a program that creates a binary search tree based on...
In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code** Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab. bst.h: #ifndef BST_H #define BST_H typedef struct BSTNode { int value; struct BSTNode* left; struct BSTNode* right; } BSTNode; BSTNode*...
Use Java: Also: Please include screenshots if possible. Create a class called AbstractStackTest. Write an abstract...
Use Java: Also: Please include screenshots if possible. Create a class called AbstractStackTest. Write an abstract method called makeStack that returns a Stack of Strings. Use the Stack interface as the return type, not a specific implementation! Write a class named NodeStackTest that extends your AbstractStackTest class. Implement the makeStack method to return a NodeStack. Repeat parts 1 and 2 for the Queue interface and the NodeQueue implementation. Write a new stack implementation, ArrayStack. It should be generic and use...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
You will be traversing through an integer tree to print the data. Given main(), write the...
You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 - 85 -...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
Java Program: You will be traversing through an integer tree to print the data. Given main(),...
Java Program: You will be traversing through an integer tree to print the data. Given main(), write the methods in the 'IntegerBinaryTree' class specified by the // TODO: sections. There are 6 methods in all to write. Ex: If the input is: 70 86 60 90 49 62 81 85 38 -1 the output should be: Enter whole numbers to insert into the tree, -1 to stop Inorder: 38 - 49 - 60 - 62 - 70 - 81 -...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
For this question, consider the following class which will be used to construct binary trees. Use...
For this question, consider the following class which will be used to construct binary trees. Use the convention that there is no "empty tree"; each node points to the nodes containing it's two children; and if a node has no left or right child, then the corresponding pointer will be set to null public class TreeNode { public double root; public TreeNode left; public TreeNode right; } Draw a diagram for what a tree of this model would look like...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the in-order traversal as the default.             This means, in Tester the following code should work for an instance of this class             called bst that is storing Student objects for the data:                 BinarySearchTree_Lab08<String> bst = new BinarySearchTree_Lab08<String>();                 bst.add("Man");       bst.add("Soda");   bst.add("Flag");                 bst.add("Home");   bst.add("Today");   bst.add("Jack");                ...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT