c - 如何找到 BST 中小于或等于给定值的节点数？ (AVL 树)

Question

所以我需要编写一个递归函数来获取BST根和另一个参数k，并且我需要找到BST中小于或等于k的节点的数量。有任何想法吗？ 谢谢 我尝试了这个函数，但它并没有真正起作用(仅适用于树中最小的 5 个节点)

int avl_rank( AVLNodePtr tnode, int k )

if (tnode == NULL)
    return 0;

int count = 0;

// if current root is smaller or equal
// to x increment count
if (tnode->key <= k)
    count++;

// Number of children of root
int numChildren;
if (tnode->child[0]==NULL && tnode->child[0]==NULL)
    numChildren = 0;
else if ((tnode->child[0]!=NULL && tnode->child[0]==NULL) || (tnode->child[0]==NULL && tnode->child[0]!=NULL))
    numChildren = 1;
else numChildren = 2;

// recursively calling for every child
int i;
for ( i = 0; i < numChildren; i++)
{
    AVLNodePtr child = tnode->child[i];
    count += avl_rank(child, k);
}

// return the count
return count;

}

Answer 1

int avl_rank( AVLNodePtr tnode, int k )
{
    if(tnode==NULL) return 0;
    int count = 0;
    if (tnode->key<=k) count++;
        count += (avl_rank(tnode->child[0],k) +
            avl_rank(tnode->child[1],k));
    return count;
}