I am working with a Java program to create a balanced and unbalanced binary sear

Question

I am working with a Java program to create a balanced and unbalanced binary search tree. I have created the unbalanced but I still need to create a balancing factor. I also am trying to add a feature to determine the height of the two trees as well as implement code that will not allow duplicate entries to be added to the tree.

Below is my existing code.

public class BSTNode
{
    int data;
    BSTNode parent;
    BSTNode left;
    BSTNode right;

    public BSTNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    public BSTNode()
    {
    }
}

------------------------------------------------------------

public class BSTFunctions
{
    BSTNode ROOT;
public BSTFunctions()
    {
        this.ROOT = null;
    }

    void insertNode(BSTNode node, int data)
    {
        if (node == null)
        {
            node = new BSTNode(data);
            ROOT = node;
        }
        else if (data < node.data && node.left == null)
        {
            node.left = new BSTNode(data);
            node.left.parent = node;
        }
        else if (data >= node.data && node.right == null)
        {
            node.right = new BSTNode(data);
            node.right.parent = node;
        }
        else
        {
            if (data < node.data)
            {
                insertNode(node.left, data);
            }
            else
            {
                insertNode(node.right, data);
            }
        }
    }

    public boolean search(BSTNode node, int data)
    {
        if (node == null)
        {
            return false;
        }
        else if (node.data == data)
        {
            return true;
        }
        else
        {
            if (data < node.data)
            {
                return search(node.left, data);
            }
            else
            {
                return search(node.right, data);
            }
        }
    }
   

    public void printInOrder(BSTNode node)
    {
        if (node != null)
        {
            printInOrder(node.left);
            System.out.print(node.data + " ");
            printInOrder(node.right);
        }
    }

    public void printPostOrder(BSTNode node)
    {
        if (node != null)
        {
            printPostOrder(node.left);
            printPostOrder(node.right);
            System.out.print(node.data + " ");
        }
    }

    public void printPreOrder(BSTNode node)
    {
        if (node != null)
        {
            System.out.print(node.data + " ");
            printPreOrder(node.left);
            printPreOrder(node.right);
        }
    }

    public static void main(String[] args)
    {
        BSTFunctions f = new BSTFunctions();

//      Insert

        f.insertNode(f.ROOT, 77);
//        f.insertNode(f.ROOT, 29);
//        f.insertNode(f.ROOT, 23);
        f.insertNode(f.ROOT, 19);
        f.insertNode(f.ROOT, 37);
        f.insertNode(f.ROOT, 43);
        f.insertNode(f.ROOT, 26);
        f.insertNode(f.ROOT, 55);
        f.insertNode(f.ROOT, 36);
        f.insertNode(f.ROOT, 16);
//       f.insertNode(f.ROOT, 21);
        f.insertNode(f.ROOT, 23);
        f.insertNode(f.ROOT, 24);
        f.insertNode(f.ROOT, 7);
        f.insertNode(f.ROOT, 51);
        f.insertNode(f.ROOT, 20);
        f.insertNode(f.ROOT, 9);
        f.insertNode(f.ROOT, 13);
        f.insertNode(f.ROOT, 87);
        f.insertNode(f.ROOT, 52);
        f.insertNode(f.ROOT, 86);
        f.insertNode(f.ROOT, 21);
        f.insertNode(f.ROOT, 15);
        f.insertNode(f.ROOT, 29);
        f.insertNode(f.ROOT, 6);
        f.insertNode(f.ROOT, 54);
//        f.insertNode(f.ROOT, 77);
        f.insertNode(f.ROOT, 88);
       

//      Print

  System.out.println("Preorder of Unbalanced: ");
        f.printPreOrder(f.ROOT);
        System.out.println("");
  System.out.println("Postorder of Unbalanced: ");
        f.printPostOrder(f.ROOT);
        System.out.println("");
  System.out.println("Inorder of Unbalanced: ");
        f.printInOrder(f.ROOT);
        System.out.println("");

    }
}

Explanation / Answer

Answer :

class BSTNode
{
int data;
BSTNode parent;
BSTNode left;
BSTNode right;
public BSTNode(int data)
{
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
public BSTNode()
{
}
}

public class BSTFunctions
{
BSTNode ROOT;
public BSTFunctions()
{
this.ROOT = null;
}
void insertNode(BSTNode node, int data)
{
if (node == null)
{
node = new BSTNode(data);
ROOT = node;
}
else if (data < node.data && node.left == null)
{
node.left = new BSTNode(data);
node.left.parent = node;
}
else if (data >= node.data && node.right == null)
{
node.right = new BSTNode(data);
node.right.parent = node;
}
else
{
if (data < node.data)
{
insertNode(node.left, data);
}
else
{
insertNode(node.right, data);
}
}
}
public boolean search(BSTNode node, int data)
{
if (node == null)
{
return false;
}
else if (node.data == data)
{
return true;
}
else
{
if (data < node.data)
{
return search(node.left, data);
}
else
{
return search(node.right, data);
}
}
}

public void printInOrder(BSTNode node)
{
if (node != null)
{
printInOrder(node.left);
System.out.print(node.data + " ");
printInOrder(node.right);
}
}
public void printPostOrder(BSTNode node)
{
if (node != null)
{
printPostOrder(node.left);
printPostOrder(node.right);
System.out.print(node.data + " ");
}
}
public void printPreOrder(BSTNode node)
{
if (node != null)
{
System.out.print(node.data + " ");
printPreOrder(node.left);
printPreOrder(node.right);
}
}
public static void main(String[] args)
{
BSTFunctions f = new BSTFunctions();
// Insert
f.insertNode(f.ROOT, 77);
// f.insertNode(f.ROOT, 29);
// f.insertNode(f.ROOT, 23);
f.insertNode(f.ROOT, 19);
f.insertNode(f.ROOT, 37);
f.insertNode(f.ROOT, 43);
f.insertNode(f.ROOT, 26);
f.insertNode(f.ROOT, 55);
f.insertNode(f.ROOT, 36);
f.insertNode(f.ROOT, 16);
// f.insertNode(f.ROOT, 21);
f.insertNode(f.ROOT, 23);
f.insertNode(f.ROOT, 24);
f.insertNode(f.ROOT, 7);
f.insertNode(f.ROOT, 51);
f.insertNode(f.ROOT, 20);
f.insertNode(f.ROOT, 9);
f.insertNode(f.ROOT, 13);
f.insertNode(f.ROOT, 87);
f.insertNode(f.ROOT, 52);
f.insertNode(f.ROOT, 86);
f.insertNode(f.ROOT, 21);
f.insertNode(f.ROOT, 15);
f.insertNode(f.ROOT, 29);
f.insertNode(f.ROOT, 6);
f.insertNode(f.ROOT, 54);
// f.insertNode(f.ROOT, 77);
f.insertNode(f.ROOT, 88);

// Print
System.out.println("Preorder of Unbalanced: ");
f.printPreOrder(f.ROOT);
System.out.println("");
System.out.println("Postorder of Unbalanced: ");
f.printPostOrder(f.ROOT);
System.out.println("");
System.out.println("Inorder of Unbalanced: ");
f.printInOrder(f.ROOT);
System.out.println("");
   displayBalanceFactor(BSTNode node);
}
  
   public int displayBalanceFactor(BinaryTree t)
{
if (t == null)
return 0;

if (t.left == null && t.right == null)
return 1;

int heightLeft = displayBalanceFactor(t.left);
int heightRight = displayBalanceFactor(t.right);

System.out.println("Balance factor of " + t + " is " + (heightLeft - heightRight));

return heightLeft + heightRight + 1;
}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.