Застрял при удалении узла из дерева

Чтобы удалить узел в дереве, вам необходимо:

1. освободите память и выполните очистку узла
2. исправьте указатель, который вы использовали для достижения узла, сделав его NULL

Часть 2 можно решить двумя способами:

A) родитель выполняет исправление. B) процедура удаления получает адрес адреса узла (дополнительный уровень косвенного обращения).

Для решения A код просто

void deleteNodeA(Node *p) {
    if (p) {
        // Here we don't really need part 2 because
        // we're going to destroy the whole node containing
        // the pointers anyway.
        deleteNodeA(p->left);  // add p->left = NULL if you like
        deleteNodeA(p->right); // add p->right = NULL if you like
        free(p->data);
        free(p);
    }
}

но вызывающей стороне необходимо исправить указатель, используемый для достижения узла. Например как

Node *p = root, *parent = NULL;
while (p && (p->left || p->right)) {
    // Not a leaf... go left if possible o right otherwise
    parent = p;
    p = p->left ? p->left : p->right;
}

// 2: Fix the pointer in parent
if (parent) {
    if (p == parent->left) {
        parent->left = NULL;
    } else {
        parent->right = NULL;
    }
} else {
    // No parent... this was the root of the tree
    root = NULL;
}

deleteNodeA(p);

Решение B выглядит так:

void deleteNodeB(Node **p) { // Note the double pointer
    if (*p) {
        deleteNode(&((*p)->left));  // Note the &
        deleteNode(&((*p)->right)); // Note the &
        free((*p)->data);
        free(*p);
        *p = NULL; // (2): fixing the pointer
    }
}

и, например, код, удаляющий лист дерева,

Node **p = &root;
while ((*p) && ((*p)->left || (*p)->right)) {
    // Not a leaf... go left if possible o right otherwise
    p = ((*p)->left) ? &((*p)->left) : &((*p)->right));
}
deleteNodeB(p);

Вместо того, чтобы писать 4 случайные строки кода и называть их «подходами», попробуйте на самом деле указать функцию, которая делает что-то значимое. Функция, которая принимает кучу в качестве аргумента, должна называться DeleteHeap, а не DeleteLeaf. Поскольку он удаляет кучу, ему нечего возвращать. Итак, как удалить кучу? Что ж, если куча является листом (у нее нет левого или правого поддерева), удалите это, иначе удалите поддеревья, рекурсивно вызывая DeleteHeap. Кодируйте это, и все готово.

Изменить: вы оставили комментарий:

deleteLeaf должен удалить последний элемент дерева на последнем уровне. Возвращаемое значение должно быть данными, содержащимися в удаленном листе.

Что ж, это новости. Мы не читатели мыслей. В вашем вопросе этого не было, и имя функции и подпись также не подходят для этого.

Начнем с названия - DeleteRightmostLeaf. И тип возврата ... data_t*. Даже тип аргумента неверен ... он должен быть heap_t**, потому что мы должны сохранить NULL в указателе.

Итак, DeleteRightmostLeaf принимает указатель на указатель на кучу. Если эта куча является листовым узлом, сохраните NULL в указателе на нее, извлеките указатель данных, освободите узел (в этом порядке ... в противном случае вы получите доступ к удаленной памяти, что недопустимо) и верните данные указатель.

Если куча не является листовым узлом, то вызовите DeleteRightmostLeaf рекурсивно по указателю на его крайнее правое поддерево - правое поддерево, если оно не NULL, иначе левое поддерево. Вуаля, готово.

Обратите внимание, что в обоих случаях очень легко придумать ответ, если просто четко подумать о том, что им нужно делать.

В качестве бонуса вот итеративное решение. Я не тестировал и даже не компилировал это.

data_t* DeleteRightmostLeaf(node_t** pheap)
{
    node_t* pnode = *pheap;

    if (!pnode)
        return NULL; // empty heap

    while (pnode->left || pnode->right)
    {
        pheap = pnode->right ? &pnode->right : &pnode->left;
        pnode = *pheap;
    }

    *pheap = NULL;
    data_t* pdata = pnode->data;
    free(pnode);
    return pdata;
}

Попробуйте эту модификацию вашего метода:

node_t* deleteLeaf(node_t* heap)
{
  if (!heap)
    return 0;

  if (heap->left!=0)
    deleteLeaf(heap->left);
  if (heap->right!=0)
    deleteLeaf(heap->right);

  if (heap->data)
    free(heap->data); // free data
  free(heap); // free leaf
  heap = 0;
  return heap;
}

Один вопрос: какое значение должна возвращать эта функция? (теперь он всегда возвращает 0). Трудно понять, что вы пытаетесь сделать (у нас нет описания функции, примеров ожидаемых результатов и т. Д.). Итак, я подозреваю, что приведенный выше код не является решением. Но это может быть первым шагом к пониманию проблемы.