Preliminaries First, download the driver Description Traverse a binary search tr
ID: 664947 • Letter: P
Question
Preliminaries
First, download the driver
Description
Traverse a binary search tree level by level.
Objective
Write a class BinarySearchTree. You may also use your class from Lab 9.
Your goal is to list the nodes within the tree according to their depth. The following animation is an illustration of how you should list the nodes in the tree.
Start by creating a method printByLevel. This method should take no parameters, and the result of calling it should be to list the elements of the tree in the order shown above.
Hints
One possible algorithm to traverse the tree in this order is the following:
Input: A root node of the tree to begin the traversal
Initialize a queue of nodes;
queue.enqueue(root);
while queue is not empty:
node queue.dequeue();
print(node);
foreach child of node:
queue.enqueue(child);
Driver:
}
Lab 9(already done):
public class BinarySearchTree<E extends Comparable<E>> { private class Node<E> { private E data; private Node<E> left; private Node<E> right; public Node(E data) { this.data = data; this.left = null; this.right = null; } } private Node<E> root; public BinarySearchTree() { root = null; } /** * Inserts an element into the tree. * * @param elem * The new element to be inserted into the tree. */ public void insert(E elem) { Node<E> newNode = new Node<E>(elem); if (root == null) root = newNode; else { Node<E> current = root; Node<E> parent; while (true) { parent = current; if (((Comparable<E>) elem).compareTo(current.data) < 0) { current = current.left; if (current == null) { parent.left = newNode; return; } } else { current = current.right; if (current == null) { parent.right = newNode; return; } } } } } /** * Prints the values stored in the tree in ascending order. */ public void printInorder() { printInInorder(root); } private void printInInorder(Node<E> root) { if (root != null) { printInInorder(root.left); System.out.print(root.data + " "); printInInorder(root.right); } } /** * Finds the depth of a node within the tree. Depth is defined as the number * of edges from the root to the node. * * @param elem * The element to find the depth of * @return The depth of the element within the tree. If the value is not * found, -1 is returned. */ public int getDepth(E elem) { Node<E> temp = get(elem); return getDepth(temp); } public Node<E> get(E elem) { if (root == null) { return null; } Node<E> runner = root; while (true) { if (((Comparable<E>) runner.data).compareTo(elem) > 0) { if (runner.left == null) { return null; } runner = runner.left; } else if (((Comparable<E>) runner.data).compareTo(elem) < 0) { if (runner.right == null) { return null; } runner = runner.right; } else { return runner; } } } public int getDepth(Node<E> node) { if (node == null) return 0; else { int lheight = getDepth(node.left); int rheight = getDepth(node.right); if (lheight > rheight) return (lheight + 1); else return (rheight + 1); } } /* Do not modify below this line! */ /* -------------------------------------------------------------- */ /** * Checks whether the nth bit within an integer is set. * * @param number * The number to check * @param index * The index of the bit to find * @return True if the nth bit is set. For example, (5, 1) is true since 5 = * b101, and the ones place is set. Similarly, (5, 2) is false. */ private static boolean nthBitSet(int number, int index) { int constant = 1 << (index - 1); return (number & constant) != 0; } /** * Prints an ascii representation of the tree. * * @param root * The current node to print * @param depth * The level of the tree in which the current node lies. Levels * are counted with the root starting at 0. * @param isLeft * Whether the current node is a left child. * @param parBits * A bitstring (integer) representing the parents in the path * above this node. Used to 'fill in the gaps' in the drawing. * @param buffered * Whether this was called to specifically include additional * whitespace on the left */ public void printAscii(Node<E> root, int depth, boolean isLeft, int parBits, boolean buffered) { if (root == null) { return; } for (int i = 0; i < (depth - 1) * 3; i++) { if (i % 3 == 1 && nthBitSet(parBits, depth - (i / 3))) { System.out.print("|"); } else { System.out.print(" "); } } if (isLeft && depth != 0 && !buffered) { System.out.print(" `- "); } else if (depth != 0 && !buffered) { System.out.print(" |- "); } if (buffered) { for (int i = 0; i < depth * 3; i++) { System.out.print(" "); } } System.out.println(root.data); boolean hasRight = root.right != null; boolean hasLeft = root.left != null; int newParBits = parBits << 1; if (hasLeft) { newParBits++; } printAscii(root.right, depth + 1, !hasLeft, newParBits, false); printAscii(root.left, depth + 1, true, --newParBits, false); } /** * Prints an ascii representation of the tree. */ public void printAscii() { printAscii(root, 0, false, 0, false); } }
Example Dialog
Explanation / Answer
Here is how you can write the binary search tree(BST) class which can take any tree/node as input and display the correct order and searched node :
import java.util.Scanner;
/* Class BSTNode */
class BSTNode
{
BSTNode left, right;
int data;
/* Constructor */
public BSTNode()
{
left = null;
right = null;
data = 0;
}
/* Constructor */
public BSTNode(int n)
{
left = null;
right = null;
data = n;
}
/* Function to set left node */
public void setLeft(BSTNode n)
{
left = n;
}
/* Function to set right node */
public void setRight(BSTNode n)
{
right = n;
}
/* Function to get left node */
public BSTNode getLeft()
{
return left;
}
/* Function to get right node */
public BSTNode getRight()
{
return right;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class BST */
class BST
{
private BSTNode root;
/* Constructor */
public BST()
{
root = null;
}
/* Function to check if tree is empty */
public boolean isEmpty()
{
return root == null;
}
/* Functions to insert data */
public void insert(int data)
{
root = insert(root, data);
}
/* Function to insert data recursively */
private BSTNode insert(BSTNode node, int data)
{
if (node == null)
node = new BSTNode(data);
else
{
if (data <= node.getData())
node.left = insert(node.left, data);
else
node.right = insert(node.right, data);
}
return node;
}
/* Functions to delete data */
public void delete(int k)
{
if (isEmpty())
System.out.println("Tree Empty");
else if (search(k) == false)
System.out.println("Sorry "+ k +" is not present");
else
{
root = delete(root, k);
System.out.println(k+ " deleted from the tree");
}
}
private BSTNode delete(BSTNode root, int k)
{
BSTNode p, p2, n;
if (root.getData() == k)
{
BSTNode lt, rt;
lt = root.getLeft();
rt = root.getRight();
if (lt == null && rt == null)
return null;
else if (lt == null)
{
p = rt;
return p;
}
else if (rt == null)
{
p = lt;
return p;
}
else
{
p2 = rt;
p = rt;
while (p.getLeft() != null)
p = p.getLeft();
p.setLeft(lt);
return p2;
}
}
if (k < root.getData())
{
n = delete(root.getLeft(), k);
root.setLeft(n);
}
else
{
n = delete(root.getRight(), k);
root.setRight(n);
}
return root;
}
/* Functions to count number of nodes */
public int countNodes()
{
return countNodes(root);
}
/* Function to count number of nodes recursively */
private int countNodes(BSTNode r)
{
if (r == null)
return 0;
else
{
int l = 1;
l += countNodes(r.getLeft());
l += countNodes(r.getRight());
return l;
}
}
/* Functions to search for an element */
public boolean search(int val)
{
return search(root, val);
}
/* Function to search for an element recursively */
private boolean search(BSTNode r, int val)
{
boolean found = false;
while ((r != null) && !found)
{
int rval = r.getData();
if (val < rval)
r = r.getLeft();
else if (val > rval)
r = r.getRight();
else
{
found = true;
break;
}
found = search(r, val);
}
return found;
}
/* Function for inorder traversal */
public void inorder()
{
inorder(root);
}
private void inorder(BSTNode r)
{
if (r != null)
{
inorder(r.getLeft());
System.out.print(r.getData() +" ");
inorder(r.getRight());
}
}
/* Function for preorder traversal */
public void preorder()
{
preorder(root);
}
private void preorder(BSTNode r)
{
if (r != null)
{
System.out.print(r.getData() +" ");
preorder(r.getLeft());
preorder(r.getRight());
}
}
/* Function for postorder traversal */
public void postorder()
{
postorder(root);
}
private void postorder(BSTNode r)
{
if (r != null)
{
postorder(r.getLeft());
postorder(r.getRight());
System.out.print(r.getData() +" ");
}
}
}
/* Class BinarySearchTree */
public class BinarySearchTree
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of BST */
BST bst = new BST();
System.out.println("Binary Search Tree Test ");
char ch;
/* Perform tree operations */
do
{
System.out.println(" Binary Search Tree Operations ");
System.out.println("1. insert ");
System.out.println("2. delete");
System.out.println("3. search");
System.out.println("4. count nodes");
System.out.println("5. check empty");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to insert");
bst.insert( scan.nextInt() );
break;
case 2 :
System.out.println("Enter integer element to delete");
bst.delete( scan.nextInt() );
break;
case 3 :
System.out.println("Enter integer element to search");
System.out.println("Search result : "+ bst.search( scan.nextInt() ));
break;
case 4 :
System.out.println("Nodes = "+ bst.countNodes());
break;
case 5 :
System.out.println("Empty status = "+ bst.isEmpty());
break;
default :
System.out.println("Wrong Entry ");
break;
}
/* Display tree */
System.out.print(" Post order : ");
bst.postorder();
System.out.print(" Pre order : ");
bst.preorder();
System.out.print(" In order : ");
bst.inorder();
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');
}
}