To add and implement the following new functions at the bottom of the code: i) getBalFactor( )
Question:
To add and implement the following new functions at the bottom of the code:
i) getBalFactor( ) needs to calculate the balance factor of the Binary tree and return the value calculated.
ii) computeBigO( ) that needs to calculate the Big O of the Binary Search tree.
For these functions you can add whatever you need in the argument list, or any supporting function if needed.
Show me how to complete the main that adds nodes to a tree and finds the balance factor of the tree and the associated Big O. Just the implementation of the functions in the given code and the main and it should compile.
import java.io.*;
import java.util.*;
class Node{
public int iData;
public Node leftChild;
public Node rightChild;
public void display(){
System.out.print('{');
System.out.print(iData);
System.out.print(" , ");
System.out.print('}');
}
}
public class BST {
private Node root;
public BST(){
root = null;
}
public Node find( int key ){
Node current = root;
while(current.iData != key)
{
if(key < current.iData)
current = current.leftChild;
else
current = current.rightChild;
if(current == null)
return null;
}
return current;
}
public void insert( int id ){
Node newNode = new Node();
newNode.iData = id;
if(root == null)
root = newNode;
else
{
Node current = root;
Node parent;
while( true )
{
parent = current;
if(id < current.iData)
{
current = current.leftChild;
if( current == null )
{
parent.leftChild = newNode;
return;
}
}
else
{
current = current.rightChild;
if( current == null )
{
parent.rightChild = newNode;
return;
}
}
}
}
}
public boolean delete( int key){
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while( current.iData != key)
{
parent = current;
if(key < current.iData )
{
isLeftChild = true;
current = current.leftChild;
}
else
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null)
return false;
}
//if no children simply delete it
if(current.leftChild == null &&
current.rightChild == null)
{
if(current == root)
root = null;
else if(isLeftChild)
parent.leftChild = null;
else
parent.rightChild = null;
}
//if no right child replace with left sub tree
else if(current.rightChild == null)
{
if( current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
}
else if(current.leftChild == null)
{
if( current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
}
else //two children so replace with inorder successor
{
//get successor of node to delete
Node successor = getSuccessor(current);
if( current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
successor.leftChild = current.leftChild;
}
return true;
}
private Node getSuccessor(Node delNode){
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild;
while( current != null )
{
successorParent = successor;
successor = current;
current = current.leftChild;
}
if( successor != delNode.rightChild)
{
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
public void traverse( int traverseType)
{
switch(traverseType)
{
case 1: System.out.print("nPreorder traversal: ");
preOrder(root);
break;
case 2: System.out.print("nInorder traversal: ");
inOrder(root);
break;
case 3: System.out.print("nPostorder traversal: ");
postOrder(root);
break;
}
System.out.println();
}
private void preOrder( Node localRoot){
if(localRoot != null)
{
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
private void inOrder( Node localRoot){
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
private void postOrder( Node localRoot){
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
public void displayTree(){
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"-------------------------------------");
while(isRowEmpty == false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for (int j = 0; jSystem.out.print(' ');
while(globalStack.isEmpty() == false)
{
Node temp = (Node) globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
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 < nBlanks*2 - 2; j++ )
System.out.print(" ");
}
System.out.println();
nBlanks /=2;
while(localStack.isEmpty() == false )
globalStack.push( localStack.pop());
}
System.out.println(
"------------------------------------");
}
}
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser