I am having a confusion in this Binary Tree Coding. I know the concept of binary tree and I know how those work and all, but in this source code i am confused with "Find" operation. I cannot understand how it works and all. Please help me, I am so interested in this area.
package binarytree_task4;
class Node
{
private static class Equivalent {
public Equivalent() {
}
}
public Equivalent data;
public Node right;
public Node left;
public Node(Equivalent data)
{
this(data, null, null);
}
public Node(Equivalent data, Node left, Node right)
{
this.data = data;
this.left = left;
this.right = right;
}
}
class binarytree {
public static void main(String[] args) {
}
private static class Equivalent {
public Equivalent() {
}
}
private static class present {
public present() {
}
}
private Node root;
private int size;
public binarytree()
{
size = 0;
root = null;
}
public void printTree()
{
if(size == 0)
System.out.println("Empty");
else {
System.out.println("Tree contents:");
inorder(root);
}
}
public void inorder(Node present)
{
if(present != null)
{
inorder(present.left);
System.out.println(present.data);
inorder(present.right);
}
}
public void Insert(Equivalent data)
{
root = Insert(data, root);
}
private Node Insert(Equivalent data, Node present)
{
if( present == null)
{
size++;
present = new Node(data, null, null);
}
else if(data.compareTo(present.data)<0)
{
present.left = Insert(data,present.left);
}
else if(data.compareTo(present.data)>0)
{
present.right = Insert(data, present.right);
}
return present;
}
public boolean Find(Equivalent data)
{
return Find(data, root);
}
private boolean Find(Equivalent data, Node present)
{
if(present == null )
{
return false;
}
else if(present.data == data)
{
return true;
}
else if(data.compareTo(present.data)<0)
{
return Find(data, present.left);
}
else
{
return Find(data, present.right);
}
}
public boolean Delete(Equivalent key){
if (Find(key)){
Delete(key);
return true;
}
else{
return false;
}
}
public void delete(Equivalent key)
{
Node present = root;
Node parent = root;
boolean isLeftChild = true;
while(present.data.compareTo(key) != 0)
{
parent = present;
if(present.data.compareTo(key) > 0)
{
isLeftChild = true;
present = present.left;
}
else
{
isLeftChild = false;
present = present.right;
}
if(present == null)
return ;
}
if(present.left == null && present.right == null)
{
if(present == root)
root = null;
else if(isLeftChild)
parent.left = null;
else
parent.right = null;
}
else if(present.right == null)
if(present == root)
root = present.left;
else if(isLeftChild)
parent.left = present.left;
else
parent.right = present.left;
else if(present.left == null)
if(present == root)
root = present.right;
else if(isLeftChild)
parent.left = present.right;
else
parent.right = present.right;
else
{
Node successor = getSuccessor(present);
if(present == root)
root = successor;
else if(isLeftChild)
parent.left= successor;
else
parent.right = successor;
successor.left = present.left;
}
}
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node present = delNode.right;
while(present != null)
{
successorParent = successor;
successor = present;
present = present.left;
}
if(successor != delNode.right)
{
successorParent.left = successor.right;
successor.right = delNode.right;
}
return successor;
}
}
Best Answer
Find works recursively, meaning it can call itself. However, it doesn't just call itself with the same arguments, each time it calls itself it is going deeper into the tree. If there were no checks, this could go on forever. However, this recursion has a couple of checks to terminate the search if it is given a null node (meaning, it didn't find what it was looking for), or the node it is given is the one being looked for (meaning it did find the one it was looking for). Eventually one of these conditions must be true.
It works like this:
First it looks at the node it was given. If the node is null, it didn't find what it was looking for and there are no children to search, so it returns false. This is the first termination check, and means "we didn't find it".
If the node is not null, then it checks to see if the node has the requested data. This is the second termination check. If it does, it returns true meaning "we found it".
If it doesn't find the requested data, then it must look either to the left or the right depending on whether the requested data is larger or smaller than the current data.
How does it do this last step? By taking either the left or right node, and starting the whole process over by calling itself with the left or right node of the current node and then returning the result. If the node it is currently on is a leaf node (ie: no left or right branches to follow), then a null node will be sent when it calls itself, and as you can see from earlier in the process, if Find is given a null node it will return false.
So, essentially Find says "am I the node we are looking for?" If the answer is no, it then asks itself "is my left node the one we are looking for?" or "is my right node the one I am looking for?" and it keeps asking itself that question as it goes deeper and deeper into the tree.
Notice that in all cases, Find either returns true, false, or the result of the next call to Find. This means that eventually, some version of Find will return true or false when it gets to the end of the tree, and that true or false will work its way back up the chain -- true (or false) will return to the caller, which returns that value to it's caller, which returns that value to it's caller, ... until you are back to where Find was first called.