1

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

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

我尝试以不同的方式做到这一点，但我认为我会卡住，所以我尝试了不同的方法。

实际上，我得到了一项任务，即在等于 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;
    }
4

1 回答 1

2

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

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
}
于 2013-05-01T12:24:05.860 回答