Finding a Node
Finding a node with a specified key is the simplest of the major tree operations.
Code example:
public Node find(int key)
{
Node current =root;
while(current.iData!key)
{
if(key < current.iData)
current =current.leftChild;
else
current =current.rightChild;
if(current == null)
return null;
}
}
The Node to be Deleted has one Child :
Finding a node with a specified key is the simplest of the major tree operations.
Code example:
public Node find(int key)
{
Node current =root;
while(current.iData!key)
{
if(key < current.iData)
current =current.leftChild;
else
current =current.rightChild;
if(current == null)
return null;
}
}
- Can not find the node
- Found the node
Tree Efficiency:
The time required to find a node depends on how many levels down it is situated.
So it is O(log N) .
Inserting a Node:
To insert a node,we must first find the place to insert it.This is much the same process as trying to find that a node that turns out not to exist.
Sample Code:
public void insert(int id,int dd)
{
Node newNode=new Node();
newNode.iData=id;
newNode.dData=dd;
if(root == null)
root=newNode;
else
{
Node current=root;
Node parent;
while(true)
{
parent=current;
if(id< current.leftChild)
{
currentcurrent.leftChild;
if(current == null)
{
parent.leftChild=newNode;
return;
}
}
else
{
current= current.rightChild;
if(current ==null)
{
parent.rightChild=newNode;
return;
}
}
}
}
}
Traversing the Tree:
Traversing a tree means visiting each node in a specified order.There are three simple ways to traverse a tree.they are called preorder,inorder and postorder.
Inorder Traversal:
An inorder traversal of a binary search tree will cause all the nodes to be visited in ascending order,based in their key values.
- Call itself to traverse the nodes left sub-tree.
- visit the node.
- call itself to traverse the nodes right sub-tree.
Code example:
private void inOrder(Node localRoot)
{
if(localRoot !=null)
{
inOrder(localRoot.leftChild);
System.out.println(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
PreOrder Traversal:
- Visit the node
- Call itself to traverse the nodes left sub-tree.
- Call itself to traverse the nodes right sub-tree.
Post Order Traversal:
- Call itself to traverse the nodes left sub-tree;
- Call itself to traverse the nodes right sub-tree.
- Visit the node.
Finding Maximum and Minimum Values:
public Node minimum()
{
Node current,last;
current=root;
while(current!=null)
{
last=current;
current=current.leftChild;
}
return last;
}
if you want to find the maximum value in the tree then go right sucha as
current=current.rightChild;
Deleting a Node:
Deleting a node is bit complicated.you start by finding the node you want to delete ,using the same approach we saw in find() and insert() .When you found the node ,there are three cases to consider.
- The node to be deleted is a leaf(has no children).
- The node to be deleted has one child;
- The node to be deleted has two children.
Java code to Delete a Node with no children:
public boolean delete(int key)
{
Node current=root;
Node parent=root;
boolean isLeftChild=true;
while(current.iData ! =key)
{
parent=current;
if(key<current.iData)
{
isLeftChild=true;
current=current.leftChild;
}
else
{
isLeftChild=false;
current=cureent.rightChild;
}
if(current==null)
return false;
}
}
The Node to be Deleted has one Child :
// delete() continued....
// if no right child replace with left sub-tree
else if(current.rightChild==null)
if(current==root)
root=current.leftChild;
else if(isLeftChild)
parent.leftChild=current.leftChild;
else
parent.rightChild=current.leftChild;
else if(current.leftChild==null)
if(current==root)
root=current.rightChild;
else if(isLeftChild)
parent.leftChild=current.rightChild;
else
parent.rightChild=current.rightChild;
The Node to be Deleted has two children:
if the deleted node has two children ,you can not just replace it with one of these children,at least if the child has its own children.
Here,s the trick, To delete a node with two children,replace the node with its in-order successor.
Finding the Successor:
private Node getSuccessor(Node delNode)
{
Node successorParent=delNode;
Node successor =delNode;
Node current=delNode.rightChild;
while(current!=null)
{
successorParent=sucessor;
successor=current;
current=current.leftChild;
}
if(successor!=delNode.rightChild)
{
successorParent.leftChild=successor.rightChild;
successor.rightChild=delNode.rightChild;
}
return successor;
}
No comments:
Post a Comment