搜索二叉树C，字典顺序，下一个排列，递归

Question

我有作业，完成了大部分，但我卡在了一个点上。我必须搜索一个二叉树并找到一个关键字，如果关键字没有出现我必须在树中找到字典顺序的下一个字符串作为前缀我想找到的关键字，直到没有其他字符串满足前面的条件。

下面的代码是在我没有找到确切的单词后进行搜索。

int successor(TreeNode *v,char* x){

int lenght = strlen(x);
printf("%d\n", lenght);
if (v != NULL) {

    if (strncmp(x , v->key, lenght) == 0)
    {
        // found
        printf("%s, %d\n", v->key, v->appears);
    }

    else if (strncmp(x , v->key, lenght) < 0)
        return successor(v->left, x); 

    else if (strncmp( x , v->key, lenght) > 0)
        return successor(v->right, x);      

    else 
        printf("Query string not found.\n");
    }
}
else return 0; }

例子

如果我有的话：树遍历树

         tree   <---(not root)
traversal    trees

如果我搜索："tr"

我只得到遍历返回。

遍历后无法向左或向右移动，原因是一片叶子，而且我也找不到显示树和树的方法。

我已经尝试了一些方法，但没有成功，所以现在我要问你，除此之外，我什至不知道如何处理字典顺序下一个关键字或我必须用它做什么！

感谢任何帮助！ :D

Answer 1

要打印所有包含搜索关键字的单词，您必须遍历树，因为无法提前知道是否有任何后代匹配。

基本方法

要遍历树，您可以使用与此类似的函数：

void
bin_tree_search_inorder(struct TreeNode *t)
{
    if (t == NULL)
        return;
    bin_tree_search_inorder(t->left);
    // do check here
    bin_tree_search_inorder(t->right);
}

这个函数的工作原理是尽可能向左遍历二叉树，然后从底部开始向右遍历，如此反复。要检查是否包含前缀，您可以使用 strstr 函数：

if (strstr(t->key, key) != 0)
    printf("\nMatch: [%s]", t->key);
else
    printf("\nDoesn't match: [%s]", t->key);

更好的方法

要限制搜索区域，您可以考虑到只要有机会在树下找到匹配项，您就应该继续搜索，并且您可以使其更精确：您确切知道何时有任何匹配项使用右转、左转或两者兼而有之。

void
bin_tree_search_inorder(struct t *t, char *key)
{
    int res;
    if (t == NULL)
        return;
    if (strstr(t->key, key) != 0)
    {
        printf("\nMatch: [%s]", t->key);
        bin_tree_search_inorder(t->l, key);
        bin_tree_search_inorder(t->r, key);
    } else {
        printf("\nDoesn't match: [%s]", t->key);
        if (strlen(t->key) >= strlen(key))
        {
            res = strcmp(key, t->key);
            if (res > 0)
                bin_tree_search_inorder(t->l, key);
            else
                bin_tree_search_inorder(t->r, key);
        }
    }
}

Working code

用法：

int
main(void)
{
    struct t root, l, r, rl, rr, ll, lr;
    strcpy(&root.key, "tree");
    strcpy(&l.key, "traversal");
    strcpy(r.key, "trees");
    root.l = &l;
    root.r = &r;
    l.l = l.r = r.l = r.r = NULL;
    strcpy(rl.key, "tre");
    strcpy(rr.key, "tx");
    r.l = &rl;
    r.r = &rr;
    rl.l = rl.r = rr.l = rr.r = NULL;
    strcpy(ll.key, "ta");
    strcpy(lr.key, "travvv");
    l.l = &ll;
    l.r = &lr;
    ll.l = ll.r = lr.l = lr.r = NULL;
    bin_tree_search_inorder(&root, "tr");
    return 0;
}

输出：

不匹配：[ta]

匹配：[遍历]

匹配：[travvv]

匹配：[树]

匹配：[tre]

匹配：[树木]

不匹配：[tx]

搜索二叉树C，字典顺序，下一个排列，递归

Search Binary Tree C, Lexicographic order, next permutation, recursive

c

algorithm

permutation

lexicographic

binary-search-tree

基本方法

更好的方法