Results 1 to 2 of 2
- 01-27-2009, 12:39 AM #1
Member
- Join Date
- Jan 2009
- Posts
- 7
- Rep Power
- 0
Binary Tree Deletion & Balance Methods
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 ();
}
}
- 01-27-2009, 05:26 PM #2
Similar Threads
-
Level order binary tree traversal
By H3rtaherta in forum New To JavaReplies: 1Last Post: 04-20-2009, 08:34 AM -
Help loading a Binary Tree from file
By ExplosiveWeasel in forum Java 2DReplies: 16Last Post: 12-17-2008, 02:34 AM -
Binary Search Tree
By michael_mke in forum New To JavaReplies: 3Last Post: 12-04-2008, 03:03 AM -
Binary Search Tree Traversal
By dch414 in forum New To JavaReplies: 2Last Post: 11-07-2008, 01:01 AM -
Binary Tree Implementation in Java
By Java Tip in forum java.langReplies: 0Last Post: 04-16-2008, 11:35 PM
Bookmarks