COUNT BST子树，直到找到特定的给定键（序遍历）

我需要算我通过（序）有多少子树去，直到找到指定键，

例如：如果我有一棵树，&它的inorder遍历是：1,3,7,8,9,10,11,15,20 当给定键：9，我需要返回5，当给定键：3时，我需要返回2. 我已经遍布互联网试图找到一些帮助&无法找到。

我走到这一步是：

（在“功能”是比较整数或任何特定的功能，它的工作原理）

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

来源

2017-06-28 Julian Broude

首先，在调试器中运行。 – KevinDTimm

什么是FUNC的声明？你也有定义吗？我想你会希望''COUNT_INORDER'函数结束时返回NULL。 – Elyasin

不知道这是正确的。尝试进入并增加静态变量的计数。一旦发现密钥，将其作为返回变量，否则默认返回值为-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; 
    }

来源

2017-06-28 20:06:54 physicist

你不能在递归函数中使用变量，因为它会在每个递归中重置，我做了一些更改并得到了更好的答案，但出于某种原因构建树：9 3 1 7 8 20 does not work＆i得到正确的答案，但它程序崩溃，如果我从右子树添加一些其他数字，我会更新代码现在 –

你可以使用静态变量。它们不会被重置 – physicist

在每次遍历一个节点时，count变量都会增加。如果节点的关键字与nkey匹配，则ret将被替换为count，否则ret始终为-1。让我知道如果这工作。 – physicist

COUNT BST子树，直到找到特定的给定键（序遍历）

回答

相关问题