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;
}