Results 1 to 2 of 2
  1. #1
    sev51 is offline Member
    Join Date
    Jan 2009
    Posts
    7
    Rep Power
    0

    Default 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 ();
    }



    }

  2. #2
    Steve11235's Avatar
    Steve11235 is offline Senior Member
    Join Date
    Dec 2008
    Posts
    1,046
    Rep Power
    8

    Default

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

Similar Threads

  1. Level order binary tree traversal
    By H3rtaherta in forum New To Java
    Replies: 1
    Last Post: 04-20-2009, 08:34 AM
  2. Help loading a Binary Tree from file
    By ExplosiveWeasel in forum Java 2D
    Replies: 16
    Last Post: 12-17-2008, 02:34 AM
  3. Binary Search Tree
    By michael_mke in forum New To Java
    Replies: 3
    Last Post: 12-04-2008, 03:03 AM
  4. Binary Search Tree Traversal
    By dch414 in forum New To Java
    Replies: 2
    Last Post: 11-07-2008, 01:01 AM
  5. Binary Tree Implementation in Java
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 11:35 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •