C++ Now implement the binary heap as a binary tree with nodes that include links
ID: 654476 • Letter: C
Question
C++
Now implement the binary heap as a binary tree with nodes that include links to 1 parent and two children (as we did in a binary search tree). Implement the insert and the delete, and make sure both can be done in log n time. Use the Printio function to print the tree out in order, after reading in the numbers from the file. After reading in the file, your results should be the following: 27, 78, 58, 87, 5, 51, 12, 95, 2, 69, 38, 93, 85, Note: you may have to modify my ReadHeapNumsFromFile() function slightly so that it inserts the values into your Binary Heap as a linked tree if you named the insert function something different in the linked tree and your Heap Tree class is something other than BH. Hints for this one: There?s more than one way to do this. One way is to be aware that you can figure out where to insert and delete using the knowledge that at every level in the tree, we can have 2 height nodes. So, for instance, when the height of the tree is 0, we have 2 degree nodes, and at height of 1, we have 2^1 nodes, at height 2, we add 2^2 nodes, etc. So if we know how many nodes, and we know the tree is complete, we can know how many levels down we need to go and even which path to travel down at each level to get to the next empty node at that bottom level. After each delete, the Printio should result in the following: 27,78, 58,87,5, 51,12,93, 2,68,85,38 27,58,2,78, 5,51,12,87,69,85,38 27, 58,2,78, 5,51,85,12,69,38Explanation / Answer
program :
//PUBLIC OPERATIONS
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// boolean contains( x ) --> Return true if x is present
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>>
{
public BinarySearchTree( )
{
root = null;
}
public void insert( AnyType x )
{
root = insert( x, root );
}
public void remove( AnyType x )
{
root = remove( x, root );
}
public boolean contains( AnyType x )
{
return contains( x, root );
}
public void makeEmpty( )
{
root = null;
}
public boolean isEmpty( )
{
return root == null;
}
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return new BinaryNode<AnyType>( x, null, null );
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = insert( x, t.left );
else if( compareResult > 0 )
t.right = insert( x, t.right );
else
; // Duplicate; do nothing
return t;
}
private BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return t; // Item not found; do nothing
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
t.left = remove( x, t.left );
else if( compareResult > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = remove( t.element, t.right );
}
else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
private boolean contains( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return false;
int compareResult = x.compareTo( t.element );
if( compareResult < 0 )
return contains( x, t.left );
else if( compareResult > 0 )
return contains( x, t.right );
else
return true; // Match
}
private void printTree( BinaryNode<AnyType> t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
private int height( BinaryNode<AnyType> t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}
private static class BinaryNode<AnyType>
{
BinaryNode( AnyType theElement )
{
this( theElement, null, null );
}
BinaryNode( AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt )
{
element = theElement;
left = lt;
right = rt;
}
AnyType element; // The data in the node
BinaryNode<AnyType> left; // Left child
BinaryNode<AnyType> right; // Right child
}
private BinaryNode<AnyType> root;
public static void main( String [ ] args )
{
BinarySearchTree<Integer> t = new BinarySearchTree<Integer>( );
final int NUMS = 4000;
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( i );
for( int i = 1; i < NUMS; i+= 2 )
t.remove( i );
if( NUMS < 40 )
t.printTree( );
if( t.findMin( ) != 2 || t.findMax( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );
for( int i = 2; i < NUMS; i+=2 )
if( !t.contains( i ) )
System.out.println( "Find error1!" );
for( int i = 1; i < NUMS; i+=2 )
{
if( t.contains( i ) )
System.out.println( "Find error2!" );
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.