0

我正在尝试使用 Visual Studio 2008 v9.0.30729.1 SP 在 VC++ 中构建最大堆。

在树中，每个节点如下所示：

typedef struct node{
    struct data_t *data;
    struct node_t *left;
    struct node_t *right;
}node_t;

单个节点创建逻辑如下所示：

node_t* createNode(int id, int pID, float probability)
{
    node_t *temp = (node_t *)malloc(sizeof(node_t));
    data_t *data = (data_t *)malloc(sizeof(data_t));

    data->id = id;
    data->pID = pID;
    data->probability = probability;

    temp->data = data;
    temp->left = 0;
    temp->right = 0;

    return temp;
}

我已经设法在树中创建和插入元素（插入逻辑工作正常）。我坚持从这棵树中删除一个节点（准确地说是一片叶子）的逻辑。

我已经尝试了四种不同的方法：

node_t* deleteLeaf(node_t* heap)
{
    node_t* leaf;


    if((heap->left==0) && (heap->right==0))
    {
        //heap = 0;     //APROACH 1
        //heap->data = 0;   //APROACH 2

        return heap;
    }
    else if((heap->left!=0) && (heap->right==0))
    {
        leaf = deleteLeaf(heap->left);

    }
    else 
    {
        leaf = deleteLeaf(heap->right);

    }

    //leaf = 0;         //APROACH 3
    //free(leaf);           //APROACH 4 

    return leaf;

}

（取消注释 APPROACH 1/2/3/4 以获得所需的效果）。

这些似乎都不起作用。我需要为前一个节点的左/右指针分配一个零/空值。

如何使这项工作？请帮忙。

4

3 回答 3

2

与其编写 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;
}
于 2014-09-04T05:41:04.980 回答
2

要删除树中的节点，您需要

  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);
于 2014-09-04T06:00:44.263 回答
1

尝试对您的方法进行此修改：

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）。很难理解你想要做什么（我们没有描述功能，预期结果的例子等等）。所以，我怀疑，上面的代码不是解决方案。但这可能是理解问题的第一步。

于 2014-09-04T05:23:28.520 回答