计算 BST 子树直到找到特定的给定键（中序遍历）

Question

家庭作业

我需要计算在找到给定键之前我经历了多少个子树，

例如：如果我有一棵树，&它的中序遍历是：1,3,7,8,9,10,11,15,20 当给出 key:9 时，我需要 return 5，当给出 key:3 时，我需要 return 2。我在互联网上到处寻找帮助，但找不到。

到目前为止我得到的是：

（"FUNC" 是比较整数或其他任何东西的特定函数，它有效）

    void PRINT_KEY_ORDER(PTN TRoot, void *nkey, CMP_KEYS FUNC)  // prints keys place (inorder)
{
    int counter = 1;
    fprintf(stdout, "%d", *(COUNT_INORDER(TRoot, nkey, FUNC, &counter)));   // prints counter which is always INT
}

int* COUNT_INORDER(PTN TRoot, void *nkey, CMP_KEYS FUNC, int *counter)      // counts times until reaches wanted key
{
    if (TRoot != NULL)
    {
        COUNT_INORDER(TRoot->left, nkey, FUNC, counter);
        if (FUNC(TRoot->key, nkey) == 0)
            return counter;
        (*counter)++;
        COUNT_INORDER(TRoot->right, nkey, FUNC, counter);
    }
}

此代码有效。

计数正确，但由于某些原因，如果我使用的不止这些，则会在 fprintf 行上崩溃：9 3 1 7 8 20

Answer 1

不确定这是否正确。尝试按顺序增加静态变量中的计数。找到密钥后将其作为 return 变量，否则默认 return 为 -1 表示未找到密钥。

int COUNT_INORDER(PTN TRoot, nkey, FUNC )     
   {
    static count=0;
    int ret=-1;

    ret= COUNT_INORDER(TRoot->left, nkey, FUNC);

    count++;
    if (FUNC(TRoot->key, nkey) == 0)
        ret = count;

    if(ret == -1)
        ret= COUNT_INORDER(TRoot->right, nkey, FUNC);


     return ret;
    }

计算 BST 子树直到找到特定的给定键（中序遍历）

COUNT BST subtrees until finding specific given key (inorder traversal)

c

recursion

count

binary-search-tree

inorder