Java USES the merge and delete method to remove a node in a binary tree
- 2020-04-01 03:52:45
- OfStack
This article illustrates how Java USES merge and delete to remove nodes from a binary tree. Share with you for your reference. Specific analysis is as follows:
The idea is simple:
First: find the node to delete
Second: if the deleted node does not have a right child tree then the left child tree is linked to the parent node
Third: if the deleted node does not have a left child tree then the right child tree is linked to the parent node
Forth: if the deleted node has left or right children, then the subtree after the deleted node can be merged: there are two methods: one is the right-most node of the left subtree of the deleted node, pointing to the right subtree of the deleted node; the other is the left-most node of the deleted node, pointing to the left subtree of the deleted node.
The Java implementation is as follows:
public void deleteByMerging(int el)
{
IntBSTNode tmp,node,p=root,prev=null;
while(p!=null&&p.key!=el)
{
prev=p;
if(p.key<el)
p=p.right;
else p=p.left;
}
node=p;
if(p!=null&&p.key==el)
{
if(node.right==null)
//node has no right child then its left child (if any) is attached to
node=node.left;
//its parent
else if(node.left==null)
//node has no left child then its right child (if any) is attched to
node=node.right
//its parent
else{
tmp=node.left;
while(tmp.right!=null)
tmp=tmp.right;
//find the rightmost node of the left subtree
tem.right=node.right;
//establish the link between the rightmost node of the left subtree and the right subtree
node=node.left;
}
if(p==root)
{
root=node;
}
else if (prev.left==p)
{
prev.left=node;
}
else prev.right=node
}
else if(root!=null)
{
System.out.println("the node is not in the tree");
}
else System.out.println("The tree is empty");
}
I hope this article has been helpful to your Java programming.