-1
원하는 노드를 삭제할 수없는 이유는 무엇입니까? 예를 들어, 1,2,3,4,5 순으로 항목이있는 트리를 만들고 내 delete 메소드를 사용하여 3을 삭제하면 3 이하를 포함하는 노드가 3 대신 삭제되고 4,5가됩니다. 선주문으로 모든 노드를 다시 인쇄하면 도움이됩니다.Java의 이진 검색 트리에서 삭제
import java.util.Scanner;
클래스 TNODE {
protected int data;
protected tnode left,right;
public tnode(){
data=0;
right=left=null;
}
public tnode(int v){
data=v;
right=left=null;
}
public int getdata(){
return data;
}
public tnode getleft(){
return left;
}
public tnode getright(){
return right;
}
} 클래스 BTREE {
protected tnode root;
public btree(){
root=null;
}
public boolean isEmpty(){
return root==null;
}
public void insert(int val){
root=insert(root,val);
}
private tnode insert(tnode r,int val){
if(r==null){
r=new tnode(val);
}
else{
if(val>r.getdata()){
r.right=insert(r.right,val);
}
else{
r.left=insert(r.left,val);
}
}
return r;
}
public void preorder(){
preorder(root);
}
private void preorder(tnode r){
if(r!=null){
System.out.print(r.getdata()+" ");
preorder(r.getleft());
preorder(r.getright());
}
}
public int min(){
return min(root);
}
public int min(tnode r){
if(r.left==null){
return r.getdata();
}
else{
return min(r.left);
}
}
public void delete(int val){
root=delete(root,val);
}
private tnode delete(tnode r,int val){
if(r==null){
return null;
}
else if(val>r.getdata()){
r=delete(r.right,val);
}
else if(val<r.getdata()){
r=delete(r.left,val);
}
else{// when r.data=value
//if node has both children
if(r.left!=null && r.right!=null){
tnode temp=r;
//get the minimum value in right sub tree
int min_right=min(temp.right);
//replace this with the node to be deleted
r.data=min_right;
//delete this node
r=delete(r.right,min_right);
}
//if has left child
else if(r.left!=null){
r=r.left;
}
//if has right child
else if(r.right!=null){
r=r.right;
}
else{
//if has no child
r=null;
}
}
return r;
}
}