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

Question

Я понимаю алгоритмы, но я не уверен, как поместить это в реальные коды. Пожалуйста помоги! А также, пожалуйста, объясните подробно. Я действительно хочу понять это помимо того, что просто копирую ответ.;)

Вот мои коды:

 public boolean getLeftChild(){
    Node insertNode = root;
    while(insertNode!=null){
        insertNode = insertNode.left;
    }
    return true;
}
public Boolean removeMin(){
    Node insertNode = root;
    Node parentNode =root;

        if (insertNode.left ==null){
            insertNode.right = parentNode;
            insertNode = null;

        }else if (getLeftChild() ==true && insertNode.right != null){
            insertNode.left = null;
        }else{
            parentNode.left = insertNode.right;

    }
        return true;
}

Answer 1

Перво-наперво: для деревьев я настоятельно рекомендую рекурсию.

Всего один пример:

getSmallestNode(Node node){
     if(node.left != null){
         return getSmallestNode(node.left)
     }

     return node;
}

Для удаления может быть два случая, если вы хотите удалить наименьшее (и, следовательно, "самый левый дочерний" дочерний элемент) двоичного дерева.

Случай 1: у листа нет дочерних узлов, в этом случае просто установите соответствующую запись в родительском элементе на ноль (mostLeftChild.getParent().left = null)

Случай 2: у листа есть правый дочерний узел (не может быть левого дочернего узла, потому что это означает, что будет меньший узел, а выбранный в данный момент узел не самый маленький), в этом случае вы заменяете текущий левый узел на самый маленький узел правого поддерева mostLeftChild.getParent().left = getSmallestFromSubtree(mostLeftChild.right)

Так что теперь, чтобы превратить это в код, это может выглядеть примерно так (нет гарантии, что это действительно работает)

public Node deleteSmallest(Node node){
    // haven't reached leaf yet
    if(node.left != null{
        return deleteSmallest(node.left)
    }

    // case 1, no child nodes
    if(node.right == null){
        node.getParent().left = null;
    } else { // case 2, right child node
        node.getParent().left = deleteSmallest(node.right)
    }

    return node;
}

И вы бы назвали это с deleteSmallest(root)