Двоичное дерево поиска находит максимальный узел и удаляет его (общие классы) - PullRequest
Новая
       11

Двоичное дерево поиска находит максимальный узел и удаляет его (общие классы)

0 голосов
/ 02 ноября 2018

Как видно из заголовка, я сейчас пытаюсь найти максимальный узел BST и хочу удалить его. У меня есть методы для поиска узла Max и удаления готового узла из моей книги по алгоритмам, но я не могу понять, как их использовать в основном методе. У меня есть метод, который может вставить узлы, введя число, например, 8, который будет печатать дерево в упорядоченном уровне: 4, 2, 6, 1, 3, 5, 7 где 4 - корень Я хочу иметь возможность найти последний узел и удалить его. До сих пор у меня есть эти методы: 

public BinaryNode remove(AnyType x, BinaryNode<AnyType> t)
{
    if(t == null)
        return t;

    int compareResult = x.compareTo(t.element);

    if(compareResult < 0 )
        t.left = remove(x, t.left);
    else if(compareResult > 0)
        t.right = remove(x, t.right);
    else if(t.left != null && t.right != null)
    {
        t.element = (AnyType) findMax(t.right).element;
        t.right = remove(t.element, t.right);
    }
    else
        t = (t.left != null) ? t.left : t.right;
    return t;
}

public BinaryNode<AnyType> remove(AnyType x)
{
    return root = remove(x, root);
}

public BinaryNode<AnyType> findMax(BinaryNode<AnyType> t)
{
    if(t != null)
        while(t.right != null)
            t = t.right;
    return t;
}

Мой основной метод выглядит так: 

public static void main(String[] args)
{
    CompleteBinarySearchTree<Integer> bst = new CompleteBinarySearchTree<>();
    BinaryNode<Integer> tree = bst.createBinarySearchTree(bst.insertNodes(8));
    bst.printLevelOrderedBST(tree);
}

Я хочу иметь возможность свободно вставлять любые узлы, и дерево должно иметь возможность удалять узел max. Я не могу понять, как вызвать метод remove () для findMax (). Я, конечно, могу вызвать remove (7, tree), и он удалит 7, но это не то, что я хочу. Любая помощь очень ценится.

1 Ответ

0 голосов
/ 03 ноября 2018

Ключом к удалению узла max является то, что вы должны следить за его родителем, чтобы вы могли обновить указатель right родителя (установите его на null). Вы также должны обработать случай, когда у проходящего узла нет правого потомка, в котором сам узел является самым большим узлом.

Код ниже показывает основную идею. Не проверено, но должно быть близко. 

// removes the largest node in the binary tree with root at t.
// returns the new root.
public BinaryNode<AnyType> removeMax(BinaryNode<AnyType> t)
{
    if (t == null) return null;
    if (t.right == null) {
        // the node passed in is the largest.
        return t.left;
    }

    // traverse the right branch to the last node,
    // keeping track of the previous node so you can correctly set its
    // right pointer to null.
    BinaryNode<AnyType> parent = t;
    BinaryNode<AnyType> child = parent.right;
    while (child.right != null) {
        parent = child;
        child = child.right;
    }
    parent.right = null;
    return t;
}
...