Binary Tree Deletion & Balance Methods

[sev51]

So i have to create the necessary methods for a binary tree (in essence a doubly linked list) and i have most of the methods completed but im stuck on delete and balance .. I know that for balance i will need to determine the middle value of the list and make it the root and then the middle of the first half of the list will be the left node, etc but how do i go about starting this .. here is what i have so far..

public class MyBinaryTree
{
private BinaryElement root;
int count = 0;

public MyBinaryTree ()
{

root = null;

}

public void add (BinaryElement newNode) //adds an element to the list
{
if (root == null) // if root is empty
{
root = newNode; //new node is root
}
else
{
addRecursive(root, newNode);//call recursive method
}
}

private void addRecursive (BinaryElement treeNode, BinaryElement newNode)
{
if (newNode.getKey().compareTo(treeNode.getKey()) < 0) //new node is less in value than the current node
{
if (treeNode.left == null) //left node is empty
{
treeNode.left = newNode; // make left node equal new node
}
else
{
addRecursive(treeNode.left, newNode); // recall method
}
}

else //new node is greater than/ equal to the current node
{
if (treeNode.right == null) //right node is empty
{
treeNode.right = newNode; // make right node equal new node
}
else
{
addRecursive (treeNode.right, newNode); //recall method
}
}
}


public void delete (String searchKey) // removes a specific node from the tree
{
BinaryElement deleteElement = searchRecursive (root, searchKey);
System.out.println(deleteElement.getKey());

if (deleteElement.left == null && deleteElement.right == null)//1. node to be deleted has no children
{
System.out.println("here");
deleteElement = null;
}
else if (deleteElement.left != null || deleteElement.right != null)//2. node has one child
{
if(deleteElement.left != null)
{
deleteElement = deleteElement.left;
}
else
{
deleteElement = deleteElement.right;
}
}
else//3. node to be deleted has 2 children
{
//3.1 Use the inorder successor of the node to be deleted

//3.2 Else if no right subtree exists replace the node to be deleted with the it's left child
}



}

public void rebalance()
{


}

public void displayGraphically()
{

}


public BinaryElement search (String searchKey)
{
BinaryElement foundElement = null;

if (root != null)
{
foundElement = searchRecursive(root, searchKey);
}


return foundElement;
}

public BinaryElement searchRecursive (BinaryElement treeNode, String searchKey)
{
BinaryElement foundElement = null;
int compareResult = searchKey.compareTo(treeNode.getKey());


if (compareResult == 0)
{
// found the element
foundElement = treeNode;
}
else if (compareResult < 0)
{
// search the left side
if (treeNode.left != null)
{
foundElement = searchRecursive(treeNode.left, searchKey);

}
}
else
{
// search the right side
if (treeNode.right != null)
{
foundElement = searchRecursive(treeNode.right, searchKey);

}
}
return foundElement;
}

public void display () //displays contents of the stack on console
{
System.out.println("Contents of the tree:");

if (root != null)
{
displayRecursive(root);
}
}

public void displayRecursive(BinaryElement element)
{
if (element.left != null)
{
displayRecursive(element.left);
}
System.out.println(element.getKey());

if (element.right != null)
{
displayRecursive(element.right);
}
}
}



and the BinaryElement used is here:
public class BinaryElement
{
public Object o;

public BinaryElement left;// link to the left
public BinaryElement right;// link to the right

public BinaryElement (Object o)
{
this.o = o;
left = null;
right = null;// not actually required
}

public String getKey ()
{
return o.toString ();
}



}

[Steve11235]

We mostly work on code issues; implementing algorithms is a bit outside what we typically do...