java 병합 삭제법으로 두 갈래 트리의 노드를 삭제하는 방법

본고는 자바가 병합 삭제법을 사용하여 두 갈래 트리의 노드를 삭제하는 방법을 실례로 기술하였다.여러분에게 참고할 수 있도록 나누어 드리겠습니다.구체적인 분석은 다음과 같다.
실현된 사상은 매우 간단하다.
first: 삭제할 노드 찾기
second: 삭제된 노드가 오른쪽 트리가 없으면 왼쪽 트리가 부모 노드로 연결됩니다.
third: 삭제된 노드가 왼쪽 트리가 없으면 오른쪽 트리가 부모 노드로 연결됩니다.
forth: 삭제된 노드가 아이를 좌우한다면 노드 후의 하위 트리를 병합해서 삭제할 수 있습니다. 방법은 두 가지가 있는데 하나는 노드를 삭제한 왼쪽 트리의 가장 오른쪽 노드로 노드를 삭제한 오른쪽 트리를 가리키는 것이고, 다른 하나는 노드를 삭제한 글자수의 가장 왼쪽 노드로 노드를 삭제한 왼쪽 트리를 가리키는 것입니다.
Java는 다음과 같습니다.

public void deleteByMerging(int el)
{
IntBSTNode tmp,node,p=root,prev=null;
/*find the node to be deleted*/
while(p!=null&&p.key!=el)
{
prev=p;
if(p.key<el)
p=p.right;
else p=p.left;
}
/*find end*/
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");
}
본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다.

좋은 웹페이지 즐겨찾기