The accepted answer can make a Perfect tree (which is also a Complete tree). Although it cannot make a Complete tree without being Perfect. It was the closest answer to my request though. To make a compete the without being Perfect too, you could remove the rightmost leaves of the tree.
1. Problem:
Trying to make a Binary Search Tree into a Complete Binary Search Tree. I can find lots of code examples for a Complete Binary Tree, but no Complete Binary Search Tree. The insert is working as a Binary Search Tree should. But this way of inserting is not a Complete Tree. If I add a bunch of random numbers, it will not be a Complete tree. How can I make the code insert to the tree but at the same time be a complete binary search tree?
I would greatly appreciate a code example. I don't find it hard to understand it in theory at all, but very hard to implement it in code.
2. What I tried:
- To add the nodes in a level order way.
- While loop "Insert as long as the height is not 6 and all nodes are full nodes except leaves".
- "Add only to the right child if the value is greater than the parent and if the left child is not null".
ArraysandLinkedListsto add from.
3. How I insert:
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return new BinaryNode<>( 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;
}
- The
AnyTypeis the value to be inserted, theBinaryNodeis the current node.
4. What the program is able to do:
- Insert and remove.
- Find Height, minimum, maximum or specific node.
- Preorder, Postorder, Levelorder, and Inorder searches.
- Get the number of full nodes, number of all nodes, and number of leaves.
5. Full program:
import java.nio.BufferUnderflowException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
/**
* Implements an unbalanced binary search tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class ExerciseBinarySearchTree03<AnyType extends Comparable<? super AnyType>>
{
/**
* Construct the tree.
*/
public ExerciseBinarySearchTree03( )
{
root = null;
}
public void preOrder(){
System.out.println("\nPre Order ");
preOrder(root);
}
public void postOrder(){
System.out.println("\nPost Order ");
postOrder(root);
}
public void inOrder(){
System.out.println("\nIn Order ");
inOrder(root);
}
public void levelOrder(){
System.out.println("\nLevel Order ");
levelOrder(root);
}
public int numberOfNodes(){
return numberOfNodes(root);
}
public int numberOfFullNodes(){
return numberOfFullNodes(root);
}
public int numberOfLeaves(){
return numberOfLeaves(root);
}
/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}
/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
root = remove( x, root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new BufferUnderflowException( );
return findMin( root ).element;
}
/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
if( isEmpty( ) )
throw new BufferUnderflowException( );
return findMax( root ).element;
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if not found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}
/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
{
if( t == null )
return new BinaryNode<>( 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;
}
/* Given a binary tree, return true if the tree is complete
else false */
static boolean isCompleteBT(BinaryNode root)
{
// Base Case: An empty tree is complete Binary Tree
if(root == null)
return true;
// Create an empty queue
Queue<BinaryNode> queue =new LinkedList<>();
// Create a flag variable which will be set true
// when a non full node is seen
boolean flag = false;
// Do level order traversal using queue.
queue.add(root);
while(!queue.isEmpty())
{
BinaryNode temp_node = queue.remove();
/* Check if left child is present*/
if(temp_node.left != null)
{
// If we have seen a non full node, and we see a node
// with non-empty left child, then the given tree is not
// a complete Binary Tree
if(flag == true)
return false;
// Enqueue Left Child
queue.add(temp_node.left);
}
// If this a non-full node, set the flag as true
else
flag = true;
/* Check if right child is present*/
if(temp_node.right != null)
{
// If we have seen a non full node, and we see a node
// with non-empty right child, then the given tree is not
// a complete Binary Tree
if(flag == true)
return false;
// Enqueue Right Child
queue.add(temp_node.right);
}
// If this a non-full node, set the flag as true
else
flag = true;
}
// If we reach here, then the tree is complete Bianry Tree
return true;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
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;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the smallest item.
*/
private BinaryNode<AnyType> findMin( BinaryNode<AnyType> t )
{
if( t == null )
return null;
else if( t.left == null )
return t;
return findMin( t.left );
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the subtree.
* @return node containing the largest item.
*/
private BinaryNode<AnyType> findMax( BinaryNode<AnyType> t )
{
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the subtree.
* @return node containing the matched item.
*/
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
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the subtree.
*/
private void printTree( BinaryNode<AnyType> t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
/**
* Internal method to compute height of a subtree.
* @param t the node that roots the subtree.
*/
private int height( BinaryNode<AnyType> t )
{
if( t == null )
return -1;
else
return 1 + Math.max( height( t.left ), height( t.right ) );
}
public int height(){
return height(root);
}
private void preOrder(BinaryNode t )
{
if (t == null) {
return;
}
System.out.println(t.element + " ");
preOrder(t.left);
preOrder(t.right);
}
private void postOrder(BinaryNode t){
if (t == null) {
return;
}
postOrder(t.left);
postOrder(t.right);
System.out.println(t.element + " ");
}
private void inOrder(BinaryNode t)
{
if (t == null) {
return;
}
inOrder(t.left);
System.out.println(t.element + " ");
inOrder(t.right);
}
private void levelOrder(BinaryNode root) {
if (root == null) {
return;
}
Queue<BinaryNode> q = new LinkedList<>();
// Pushing root node into the queue.
q.add(root);
// Executing loop till queue becomes
// empty
while (!q.isEmpty()) {
BinaryNode curr = q.poll();
System.out.print(curr.element + " ");
// Pushing left child current node
if (curr.left != null) {
q.add(curr.left);
}
// Pushing right child current node
if (curr.right != null) {
q.add(curr.right);
}
}
}
//O(n) for the below three methods.
private int numberOfNodes(BinaryNode<AnyType> root){
if ( root == null ) {
return 0;
}
return 1 + numberOfNodes( root.left ) + numberOfNodes( root.right );
}
private int numberOfLeaves(BinaryNode<AnyType> t){
if( t == null ) {
return 0;
}
if( t.left == null && t.right == null ) {
return 1;
}
return numberOfLeaves(t.left) + numberOfLeaves(t.right);
}
private int numberOfFullNodes(BinaryNode<AnyType> root){
if(root==null) {
return 0;
}
if(root.left!=null && root.right!=null) {
return 1 + numberOfFullNodes(root.left) + numberOfFullNodes(root.right);
}
return numberOfFullNodes(root.left) + numberOfFullNodes(root.right);
}
// Basic node stored in unbalanced binary search trees
private static class BinaryNode<AnyType>
{
// Constructors
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
}
/** The tree root. */
private BinaryNode<AnyType> root;
AnyType[] arr = (AnyType[]) new Integer[7];
// Test program
public static void main( String [ ] args ) {
ExerciseBinarySearchTree03<Integer> bst = new ExerciseBinarySearchTree03<>( );
final int NUMS = 20;
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
bst.insert(10);
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) {
if(i != 10) {
bst.insert(i);
}
}
for( int i = 1; i < NUMS; i+= 2 )
bst.remove( i );
if( NUMS <= 40 )
bst.printTree( );
if( bst.findMin( ) != 2 || bst.findMax( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );
for( int i = 2; i < NUMS; i+=2 )
if( !bst.contains( i ) )
System.out.println( "Find error1!" );
for( int i = 1; i < NUMS; i+=2 )
{
if( bst.contains( i ) )
System.out.println( "Find error2!" );
}
bst.inOrder();
}
}
