将数组中实现的堆转换为树

Question

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

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];
}

我走的路对吗？我认为这应该递归地完成，但是如何做呢？

提前致谢

Answer 1

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

同样在循环中，您没有更改 aux 的值(或者至少您没有显示)——因此您正在覆盖旧值并发生内存泄漏。

除此之外，不检查 malloc 的返回值是另一点。您应该检查 malloc 的返回值 - 如果 NULL 那么您应该从通常的代码流中区别对待(错误处理)。

考虑到堆是在数组(0 索引)中实现的，您可以这样做以将其转换为树。

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);

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