从数组创建一个未排序的二叉树(这将像一个堆，即按顺序存储但未排序)

Question

我想创建一个以先到先得的顺序存储整数的树。第一个元素存储在 root 中，然后是 root 左侧的下一个元素，然后是右侧，依此类推。为了存储整数，我尝试给它一个整数数组作为输入。

我不知道如何做到这一点。我尝试连续插入节点，但无法继续。我创建了一个临时节点并在根的左侧插入了一个元素，然后在右侧插入了一个。现在临时节点变成了左边的节点，但是我不能在右边插入节点。

我尝试用不同的方法来做，但我想我会卡住，所以我尝试了不同的方法。

实际上，我得到了一项任务，要在一棵未排序的树中找到两个这样的节点的加法，该节点等于 k。我找到了解决方案，但问题是如何创建未排序的树。

void insert1( tree * root,int arr[],int n) {
    if (n!=0)
        root->data=arr[0];
    tree * temp;

    temp=root;

    for(i=1;i!=n;i++) {
        if(i<n) {
            temp->l->data=arr[i];
            i++;        
        }
        if(i<n) {
            temp->r->data=arr[i];
            i++;            
        }                                       
        temp=temp->l;
    }

Answer 1

如果要按索引顺序插入整数，则需要将索引转换为从根到插入位置的路径，

0 -> ""
1 -> "L"
2 -> "R"
3 -> "LL"
4 -> "LR"
5 -> "RL"
...

然后从根节点开始寻找插入的地方。将索引转换为路径很容易，一旦您知道了路径，也很容易，但在我看来，更容易的是以不同的顺序插入整数，递归地首先填充左子树，然后填充右子树。

// get us a new pointer to a properly NULL-initialised tree
tree *newEmptyTree(void) {
    tree *new = malloc(sizeof *new);
    if (!new) {
        fputs(stderr, "Allocation of tree* failed.");
        exit(EXIT_FAILURE);
    }
    new->data = NULL;
    new->l = NULL;
    new->r = NULL;
    return new;
}

// make a heap from part of an array
tree *heap_from_array(int arr[], int index, int elements) {
    // when we're past the end of the array, there's nothing to do anymore
    if (index >= elements) return NULL;

    // Otherwise, get us a new tree
    tree *this = newEmptyTree();
    // store current element
    this->data = arr[index];
    // fill left subtree
    this->l = heap_from_array(arr, 2*index + 1, elements);
    // fill right
    this-> r = heap_from_array(arr, 2*index + 2, elements);
    // done, return the thing
    return this;
}

并将其用于

void insert1( tree * root,int arr[],int n) {
    // check whether root is not NULL
    if (!root) {
        fputs(stderr, "Got a NULL root, can't insert.");
        exit(1);
    }
    // now let's hope that root is a valid pointer
    // first check whether the array does contain elements
    if (n < 0) {
        fputs(stderr, "Got no array elements, can't insert.");
        exit(EXIT_FAILURE);
    }
    // okiedokie, get going
    root->data = arr[0];
    root->l = heap_from_array(arr, 1, n);
    root->r = heap_from_array(arr, 2, n);
    // done :D
}