Поиск двоичного дерева 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);
        }
    }
} 

Рабочий код

Использование:

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 = ≪
    l.r = &lr;
    ll.l = ll.r = lr.l = lr.r = NULL;
    bin_tree_search_inorder(&root, "tr");
    return 0;
}

Выход:

Не соответствует: [та]

Матч: [обход]

Матч: [travvv]

Совпадение: [дерево]

Совпадение: [tre]

Матч: [деревья]

Не соответствует: [tx]