Удалить узел в бинарном дереве поиска

Question

Я реализовал следующие методы удаления узла в BST, следуя примеру, который размещен здесь :

class NodeT

public class NodeT {
    int elem;
    NodeT left;
    NodeT right;
    public NodeT(int elem){
        this.elem=elem;
    }
}

class BinaryTree

public class BinaryTree {
    NodoT root;
    public void insertElem(int n){
        root=addRec(root,n);
    }
    public NodoT addRec(NodeT n, int elem){
        if (n==null){
            n=new NodeT(elem);
        }
        else{
            if (elem<n.elem){
                n.left=addRec(n.left,elem);
            }
            else{
                n.right=addRec(n.right,elem);
            }
        }
        return n;
    }
    public void inorder(NodeT n){
        if (n!=null){
            inorder(n.left);
            System.out.println(n.elem);
            inorden(n.right);
        }
    }

    public NodeT search(NodeT root, int n){
        if (root.elem==n) return root;
        else{
            if (n<root.elem){
                if (root.left!=null){
                    return search(root.left,n);
                }
                else return null;
            }
            else{
                if (root.right!=null){
                    return search(root.right,n);
                }
                else return null;
            }
        }
    }

    public void delete(int n){
       root=deleteNode(root,n);
    }


    public NodeT deleteNode(NodeT curr, int n){
        NodoT answ;
        answ=search(curr,n);
        if (answ==null){
            System.out.println("not found");
            return curr;
        }
        else{

            if (curr.left==null)return curr.right; 
            else if (curr.right==null) return curr.left;
            curr.elem=minValue(curr.right);
            curr.right=deleteNode(curr.right,curr.elem);
        }
        return curr;
    }


    int minValue(NodoT curr){

        int min=curr.elem;
        while (curr.left!=null){
            menor=curr.left.elem;
            curr=curr.left;
        }
        return min;
    }


//main program


BinaryTree bt=new BinaryTree();        
   int data[]={50,30,70,20,40,60,80};

    for (int i=0;i<data.length;i++){
        bt.insertElem(data[i]);
    }
    bt.inorder(bt.root);

    bt.delete(20);
    bt.inorder(bt.root);


    bt.delete(30);
    bt.inorder(bt.root);


    bt.delete(50);
    bt.inorder(bt.root);

Тем не менее, когда я проверял, в строке bt.delete(50); выводится сообщение «not found», что я делаю неправильно?

Answer 1

В коде много ошибок, я думаю, что вы перевели из вашего языка и пропустили некоторые имена переменных. Однако я исправил имена и протестировал код.

Проблема: В вашем deleteNode() вы не повторяете вниз по дереву, т.е. проверяете, является ли элемент меньше или больше значения curr. Вам нужно добавить еще несколько IF проверок.

Решение: Заменить deleteNode() на эту.

public NodeT deleteNode(NodeT curr, int n){
    NodeT answ;
    answ=search(curr,n);
    if (answ==null){
        System.out.println("not found");
        return curr;
    }
    // need to check whether value is small or greater 
    if (n < curr.elem) 
        curr.left = deleteNode(curr.left, n); 
    else if (n > curr.elem) 
        curr.right = deleteNode(curr.right, n); 


    // if value is same, means this is the node to be deleted
    else{

        if (curr.left==null)
            return curr.right; 
        else if (curr.right==null) 
            return curr.left;
        curr.elem=minValue(curr.right);
        curr.right=deleteNode(curr.right,curr.elem);
    }
    return curr;
}

Answer 2

insertElem

public void insertElem(int n){
    root=addRec(root,n);
}

Вы переопределяете root каждый раз, когда добавляете некоторые значения, поэтому при второй вставке вы забываете о его родительском элементе и т. Д., И в итоге вы знаете только о 80, так как это последний элемент, который вы вставляете, и последнее значение, которое вы переопределяете root. root следует инициализировать, только если это null, например

if (root == null) root=addRec(root,n);

addRe c

public NodoT addRec(NodeT n, int elem){
    if (n==null){
        n=new NodeT(elem);
    }
    else{
        if (elem<n.elem){
            n.left=addRec(n.left,elem);
        }
        else{
            n.right=addRec(n.right,elem);
        }
    }
    return n;
}

Вы всегда устанавливаете n.left или n.right на значение, возвращаемое addRec, который разрушает вашу структуру. Вы можете правильно позвонить addRec, но ему следует присвоить n.left или n.right, только если соответствующее значение равно null.

inorder

. наша текущая точка зрения.

search

выглядит хорошо.

delete

выглядит хорошо.

deleteNode

public NodeT deleteNode(NodeT curr, int n){
    NodoT answ;
    answ=search(curr,n);
    if (answ==null){
        System.out.println("not found");
        return curr;
    }
    else{

        if (curr.left==null)return curr.right; 
        else if (curr.right==null) return curr.left;
        curr.elem=minValue(curr.right);
        curr.right=deleteNode(curr.right,curr.elem);
    }
    return curr;
}

Вы не сравниваете фактические цифры. Идея должна состоять в том, что удаляемый элемент будет искать в правой ветви, если значение выше, чем значение текущего узла, и в левой ветви в противном случае. Если ветвь, в которой вам нужно искать, достигает null, то элемент не существует в дереве. Смотрите реализацию Зейна Аршада. Я бы сделал нечто подобное, но так как он уже реализовал это, я обращаюсь к этому и поддерживаю это,