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

Question

我有这个功课，我必须转换数组中表示的最小堆：

DEFINE #SIZE

typedef int Heap[SIZE]

并在如下的树中实现它：

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

并提醒一下min-heaps数组的索引如下：

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

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