Implement binary search tree (BST) with insertion and preorder, postorder and in
ID: 3766870 • Letter: I
Question
Implement binary search tree (BST) with insertion and preorder, postorder and inorder traversal operations. Java program must read a list of strings from an input file and insert them into the binary search tree. Then it must traverse the tree in preorder, inorder and postorder manner and print the data in the tree on the screen.
Input file: The program has one input file called “data.txt” that contains a string on each line. There is no repetitive string in the file. Below is a sample input file: NewYork Cairo Toronto Barcelona London Paris Rome Athens Venice
Output: Your program must read each string from the input file and insert it into a binary search tree, then it has to print the contents of the tree in three ways: preorder, inorder and postorder.
Explanation / Answer
Binary Search Tree(BST):
import java.io.*;
import java.util.*;
class Node
{
public int item;
public Node leftChild;
public Node rightChild;
public void displayNode()
{
System.out.print("[");
System.out.print(item);
System.out.print("]");
}
}
class StackNode
{
public Node item;
public StackNode next;
public StackNode(Node val)
{
item = val;
}
}
class LinkedListStack
{
private StackNode first;
public LinkedListStack()
{
first = null;
}
public boolean isEmpty()
{
return (first==null);
}
public void insert(Node key)//inserts at beginning of list
{
StackNode newLLNode = new StackNode(key);
newLLNode.next = first;
first = newLLNode;
}
public Node delete()//deletes at beginning of list
{
StackNode temp = first;
first = first.next;
return temp.item;
}
}
class Stack
{
private LinkedListStack listObj;
public Stack()
{
listObj = new LinkedListStack();
}
public void push(Node num)
{
listObj.insert(num);
}
public Node pop()
{
return listObj.delete();
}
public boolean isEmpty()
{
return listObj.isEmpty();
}
}
class Tree
{
public Node root;
public Tree()
{ root = null; }
public Node returnRoot()
{
return root;
}
public void insert(int id)
{
Node newNode = new Node();
newNode.item = id;
if(root==null)
root = newNode;
else
{
Node current = root;
Node parent;
while(true)
{
parent = current;
if(id < current.item)
{
current = current.leftChild;
if(current == null)
{
parent.leftChild = newNode;
return;
}
}
else
{
current = current.rightChild;
if(current == null)
{
parent.rightChild = newNode;
return;
}
}
}
}
}
public void preOrder(Node Root)
{
if(Root != null)
{
System.out.print(Root.item + " ");
preOrder(Root.leftChild);
preOrder(Root.rightChild);
}
}
public void inOrder(Node Root)
{
if(Root != null)
{
inOrder(Root.leftChild);
System.out.print(Root.item + " ");
inOrder(Root.rightChild);
}
}
public void postOrder(Node Root)
{
if(Root != null)
{
postOrder(Root.leftChild);
postOrder(Root.rightChild);
System.out.print(Root.item + " ");
}
}
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int emptyLeaf = 32;
boolean isRowEmpty = false;
System.out.println("****......................................................****");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<emptyLeaf; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = globalStack.pop();
if(temp != null)
{
System.out.print(temp.item);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<emptyLeaf*2-2; j++)
System.out.print(' ');
}
System.out.println();
emptyLeaf /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
}
System.out.println("****......................................................****");
}
}
class TreeTraversal
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();
theTree.insert(42);
theTree.insert(25);
theTree.insert(65);
theTree.insert(12);
theTree.insert(37);
theTree.insert(13);
theTree.insert(30);
theTree.insert(43);
theTree.insert(87);
theTree.insert(99);
theTree.insert(9);
System.out.println("Displaying the tree");
theTree.displayTree();
System.out.println("Inorder traversal");
theTree.inOrder(theTree.returnRoot());
System.out.println(" ");
System.out.println("Preorder traversal");
theTree.preOrder(theTree.returnRoot());
System.out.println(" ");
System.out.println("Postorder traversal");
theTree.postOrder(theTree.returnRoot());
System.out.println(" ");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.