接受BCT（二进制计数树）中的第K个元素；

Question

该函数的问题是，对其进行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);
    }
}

Answer 1

else{
    root -> t = root -> t - 1;
    return nextK(root -> right, k - leftSize);
}

写在那的root->正确！=空吗？