I am a beginner on Data Structures
Here is my code, I seem not to be able to figure out how to delete a little node.
Someone help me out please :D
Here all the methods needed to delete a node.
public void eraseTree()
{
root = null;
}
public boolean isThere(String element)
{
if(isEmpty() == true)
{
return false;
}
//checks if the element is in the root
else if(element.compareTo(root.getData()) == 0)
{
return true;
}
else
{
//starts going thru the overloaded method
return isThere(root, element);
}
}
public boolean isThere(Node module, String element)
{
//checks if the module is null
if (module == null)
{
return false;
}
//checks if the element is equal to current module's data
else if(element.compareTo(module.getData()) == 0)
{
return true;
}
//checks if the element is less than the current module's data
else if(element.compareTo(module.getData()) < 0)
{
return isThere(module.getLeft(), element);
}
//checks if the element is greater than the current module's data
else if (element.compareTo(module.getData()) > 0)
{
return isThere(module.getRight(), element);
}
else
{
//if all else fails
//return false.
return false;
}
}
public boolean isThere(Node module, String element)
{
//checks if the module is null
if (module == null)
{
return false;
}
//checks if the element is equal to current module's data
else if(element.compareTo(module.getData()) == 0)
{
return true;
}
//checks if the element is less than the current module's data
else if(element.compareTo(module.getData()) < 0)
{
return isThere(module.getLeft(), element);
}
//checks if the element is greater than the current module's data
else if (element.compareTo(module.getData()) > 0)
{
return isThere(module.getRight(), element);
}
else
{
//if all else fails
//return false.
return false;
}
}
public Node getLeftmost(Node module)
{
//checks if the next node on the
//left side is null
if(module.getLeft() == null)
{
return module;
}
else
{
//recurrsion part
return getLeftmost(module.getLeft());
}
}
public Node getRightmost(Node module)
{
//checks if the next node on the
//right side is null
if(module.getRight() == null)
{
return module;
}
else
{
//recurrsion part
return getRightmost(module.getRight());
}
}
public Node findParent(Node module, String element)
{
//checks if the current element is smaller than
//the current data stored in the module
if (element.compareTo(module.getData()) < 0)
{
//if the data is equal to the current module's
//left module's data then it returns as parent.
if (element.compareTo(module.getLeft().getData()) == 0)
{
return module;
}
//else it will move to the left module with recurrsion
else
{
return findParent(module.getLeft(), element);
}
}
//checks if the current element is larger than
//the current data stored in the module
if(element.compareTo(module.getData()) > 0)
{
//if the data is equal to the current module's
//right module's data then it returns as parent.
if(element.compareTo(module.getRight().getData()) == 0)
{
return module;
}
//else it will move to the right module with recurrsion
else
{
return findParent(module.getRight(), element);
}
}
//if all else fails
//returns the module
return module;
}
public boolean isLeaf(Node module)
{
if(module.getLeft() == null && module.getRight() == null)
{
return true;
}
else
{
return false;
}
}
public Node findNode(Node module, String element)
{
//checks if the element is equal to current module's data
if(element.compareTo(module.getData()) == 0)
{
return module;
}
//checks if the element is less than the current module's data
else if(element.compareTo(module.getData()) < 0)
{
return findNode(module.getLeft(), element);
}
//checks if the element is greater than the current module's data
else if (element.compareTo(module.getData()) > 0)
{
return findNode(module.getRight(), element);
}
else
{
//if all else fails
//return false.
return module;
}
}
public boolean removeNode(String element)
{
//check if the tree is empty
if (isEmpty() == true)
{
System.out.println("The tree is empty.");
return false;
}
else if(isThere(element) == true)
{
//this is for the root removal
if(element.compareTo(root.getData()) == 0)
{
removeRoot();
return true;
}
else
{
removeItem(element);
return true;
}
}
else
{
System.out.println("Item not in the tree.");
return false;
}
}
private void removeRoot()
{
if(isLeaf(root))
{
eraseTree();
}
else if(root.getLeft() != null)
{
Node replaceNode = getRightmost(root.getLeft());
Node parentNode = findParent(replaceNode, replaceNode.getData());
parentNode.setRight(replaceNode.getLeft());
replaceNode.setLeft(root.getLeft());
replaceNode.setRight(root.getRight());
root = replaceNode;
}
else
{
Node replaceNode = getLeftmost(root.getRight());
Node parentNode = findParent(replaceNode, replaceNode.getData());
parentNode.setLeft(replaceNode.getRight());
replaceNode.setLeft(root.getLeft());
replaceNode.setRight(root.getRight());
root = replaceNode;
}
}
private void removeItem(String element)
{
Node deleteNode = findNode(root, element);
if (isLeaf(deleteNode) == true)
{
Node parentDelete = findParent(root, element);
if(deleteNode.getData().compareTo(parentDelete.getRight().getData()) == 0)
{
parentDelete.setRight(null);
}
else
{
parentDelete.setLeft(null);
}
}
else
{
if(deleteNode.getLeft() != null)
{
Node replaceNode = getRightmost(deleteNode.getLeft());
Node parentReplaceNode = findParent(replaceNode, replaceNode.getData());
parentReplaceNode.setRight(replaceNode.getLeft());
replaceNode.setLeft(deleteNode.getLeft());
replaceNode.setRight(deleteNode.getRight());
deleteNode = replaceNode;
}
else
{
Node replaceNode = getLeftmost(deleteNode.getLeft());
Node parentReplaceNode = findParent(replaceNode, replaceNode.getData());
parentReplaceNode.setRight(replaceNode.getLeft());
replaceNode.setLeft(deleteNode.getLeft());
replaceNode.setRight(deleteNode.getRight());
deleteNode = replaceNode;
}
}
}Here is the node information
public class Node
{
//private variables
private String element; //holds the name of the person
private Node left; //links the node to the left side of the tree
private Node right; //links the node to the right side fo the tree
/*Constructor
*Initiates all the variables
*which the user passes values.
*@param: String n is the person's name
* Node l is the left node
* Node r is the right node
*/
public Node(String element, Node left, Node right)
{
this.element = element;
this.left = left;
this.right = right;
}
/*
*Constructor
*Empty Set
*Initiates all the variable
*with no passing of values
*/
public Node()
{
this.element = null;
this.left = null;
this.right = null;
}
/*Constructor
*Initiates all the variable
*which the user passes only
*the data and not the nodes.
*@param: String n is the person's name
*/
public Node(String element)
{
this.element = element;
this.left = null;
this.right = null;
}
/*setRight Method
*sets the private right node to the right
*node on the list.
*@param: Node r
*/
public void setRight(Node right)
{
this.right = right;
}
/*getRight Method
*returns the right Node on the list
*@param: None
*@return: Node right
*/
public Node getRight()
{
return this.right;
}
/*setLeft Method
*sets the private left node to the left
*node on the list.
*@param: Node l
*/
public void setLeft(Node left)
{
this.left = left;
}
/*getLeft Method
*returns the left Node on the list
*@param: None
*@return: Node left
*/
public Node getLeft()
{
return this.left;
}
/*setData Method
*sets the private data to the node
*@param: String n is the data
* being passed to the
* method.
*/
public void setData(String element)
{
this.element = element;
}
/*getData Method
*returns the name stored in the node
*@param: None
*@return: String name
*/
public String getData()
{
return this.element;
}I just need to walk away for a bit to think about it. Please ask if more information is needed.