Удаление из дерева двоичного поиска, когда узел имеет два дочерних узла, проблема с правым поддеревом - PullRequest
Новая
       30

Удаление из дерева двоичного поиска, когда узел имеет два дочерних узла, проблема с правым поддеревом

0 голосов
/ 08 декабря 2018

Я пытаюсь удалить из узла из BST, когда у узла есть 2 дочерних элемента, и я сталкиваюсь с проблемой, которую не могу понять. 

void deleteNode(NODE ** ROOT, int data)
{
    printf("Root: %d\nData: %d\n", (*ROOT)->data, data);
    NODE * nodeToDelete = searchTree(ROOT, data);
    if(nodeToDelete == NULL)
    {
        printf("Node was not found and could not delete from tree.\n");
        return;
    }
    else {
        // There are three cases for deleting a Node.
        // 1. Node we're deleting has no Children.
        // 2. Node we're deleting has 1 child.
        // 3. Node we're deleting has 2 children.
        if(data == (*ROOT)->data)
        {
            if((*ROOT)->leftChild == NULL && (*ROOT)->rightChild == NULL) 
            {
                printf("Deleting %d\n", (*ROOT)->data);
                free(*ROOT);
                return;
            }
            else if((*ROOT)->leftChild != NULL && (*ROOT)->rightChild == NULL)
            {
                NODE * temp = (*ROOT)->leftChild;
                (*ROOT) = temp;
                free((*ROOT)->leftChild);
                return;
            }
            else if((*ROOT)->rightChild != NULL && (*ROOT)->leftChild == NULL)
            {
                NODE * temp = (*ROOT)->rightChild; // Create a pointer to the current Root's Right Child.
                (*ROOT) = temp; // Set the current root to it's right child.
                free((*ROOT)->rightChild); // Free the right child from memory.
                return;
            }
            else { // Case #3: Two Children.
                NODE * min = findMinimumNode(&(*ROOT)->rightChild);
                printf("Min: %d\n", min->data);
                int minValue = min->data;
                (*ROOT)->data = minValue;
                deleteNode(&(*ROOT)->rightChild, minValue);
            }
        }
        else if(data < (*ROOT)->data)
        {
            if((*ROOT)->leftChild != NULL)
                deleteNode(&(*ROOT)->leftChild, data);
            else
                return;
        }
        else if(data > (*ROOT)->data)
        {
            if((*ROOT)->rightChild != NULL)
                deleteNode(&(*ROOT)->rightChild, data);
            else
                return;
        }
    }
}

Первые два случая, когда нет детей, и когда есть только 1 ребенок, работает отлично.У меня также есть метод findMinimumNode, который возвращает минимальный узел поддерева.Мое текущее дерево: 3 10 15 17 27 35 37 45 67 71 82

Когда я пытаюсь удалить 45, 45 следует заменить на 67, так как 45 имеет двух дочерних элементов, а правое поддерево минимального значения 4567. Я пытаюсь заменить 45 на 67, затем пройти справа от нового 67, который равен 71, и удалить старый 67, который находится слева от 71.

Но он продолжает печатать этовыход: 3 10 15 17 27 35 37 67

...