0

该函数的问题在于，在调用它 1 次后，它不能正常工作。例如，对于 k = 4，并且树的大小 n = 7，调用时它应该首先返回值为 4 的节点，然后返回 5，而实际上它返回值为 4 和 NULL 指针的节点。找不到解决方案。

我已经为这个函数苦苦挣扎了很长一段时间，它将 node_t *root 作为我们树的根，将 k 作为第 k 个元素。我们的结构看起来像它。

typedef struct node_t{
  struct node_t *left, *right, *up;
  node *key; // its just a node from linked list from which tree was created, so key -> value
  bool isVisited;
  int t; // number of subnodes + 1
}

我们的函数还应该在从根节点到指定节点的每个节点上减少 t 并将 isVisited 更改为 true，因此我们不会再次访问它。

node_t *nextK(node_t *root, int k){
    int leftSize = 0;
    if(root == NULL) return NULL;
    if(root -> left != NULL){
        leftSize = root -> left -> t;
    }
    if(k <= leftSize) {
        root -> t = root -> t - 1;
        return nextK(root -> left, k);
    }
    if(k == leftSize + 1 && root -> isVisited == false) {
        root -> isVisited = true;
        return root;
    }
    else{
        root -> t = root -> t - 1;
        return nextK(root -> right, k - leftSize);
    }
}

示例我们的 BCT 是如何从linked_list 创建的：

node_t *linkedListToBST(node *linked_list, node_t *root, node_t *temp){
    if(linked_list!=NULL) {
        node_t *new;
        new = malloc(sizeof(node_t));
        new -> isVisited = false;
        new -> up = root;
        new -> key = middle(linked_list);
        new -> right=linkedListToBST(new -> key -> next, new, temp);
        if(new-> key!=linked_list)
            new-> left= linkedListToBST(linked_list, new, temp);
        else{
            new-> left= linkedListToBST(NULL, new, temp);
        }
        new -> t= new -> right -> t + new -> left -> t +1;
        return new;
    }
    else{
        return temp;
    }
}
node_t *iniBST2(node_t *root, node *head){
    node_t sentinel;
    sentinel.t = 0;
    sentinel.left = &sentinel;
    sentinel.right = &sentinel;
    sentinel.up = &sentinel;
    node_t *new_root;
    new_root = linkedListToBST(head, root, &sentinel);
    return new_root;
}

void addFirst(node **head, int v) {
    node *new_head;
    new_head = malloc(sizeof(node));
    new_head->value = v;
    new_head->next = *head;
    *head = new_head;
}
int n = 7;
    for(int i = n; i > 0; i--){
        addFirst(&linked_list, i);
        if(i == n){
            tail = linked_list;
        }
    }
4

0 回答 0