0

我有这个作业，我必须转换以数组表示的最小堆：

DEFINE #SIZE

typedef int Heap[SIZE]

并像这样在树中实现它：

typedef struct node{
   int val;
   struct no *left, *right;
} Node, *Tree;

提醒一下，最小堆数组的索引如下：

#DEFINE PARENT(i) (i-1)/2
#DEFINE LEFT(i) 2*i + 1
#DEFINE RIGHT(i) 2*i + 2

那么，我该怎么做呢？

我开始这样的事情：

Tree heapToTree(int * heap){
   Tree *t = malloc(sizeof(struct node));
   t->val = heap[0];
   Tree *aux = t; //save initial tree position
   for(i=0;i<SIZE;i++){
      aux->left=malloc(sizeof(struct Node));
      aux->left->val=heap[i*2 +1];
      aux->right=malloc(sizeof(struct Node));
      aux->right->val=heap[i*2 +2];
}

我在正确的道路上吗？我认为这应该递归地完成，但是如何呢？

提前致谢

4

1 回答 1

2

您缺少的一件事是 - 不将新创建的节点的链接 (left和right) 链接到NULL最初。无论如何，任何类型的树实现都非常有用 - 有助于遍历，找到一个元素（这又是一个遍历）等。

同样在循环中，您没有更改aux（或至少您没有显示）的值 - 结果您正在覆盖旧值并发生内存泄漏。

除了不检查返回值之外malloc还有一点。malloc您应该检查- if的返回值，NULL那么您应该从通常的代码流中清楚地处理（错误处理）。

考虑到堆是在数组（0-index）中实现的，您可以这样做将其转换为树。

struct node *convIntoTree(int pos,int sz, int *heap){
    if(pos >= sz ) return NULL;
    struct node* root = malloc(sizeof *root);
    if( root == NULL ){
       perror("Malloc failed");
       exit(EXIT_FAILURE);
    }
    root->data = heap[pos];
    root->left = convIntoTree(pos*2+1,sz);
    root->right = convIntoTree(pos*2+2,sz);
    return root;  
}

像这样称呼它

   struct node *root = convToTree(0,heapsize,heap);

解决方案是简单地应用一种蛮力方法遍历堆的每个节点，然后为它分配内存并递归地填充它的左右子节点。

于 2017-12-28T11:07:50.777 回答