1

宿題があり、大部分は完了しましたが、ある時点で立ち往生しています。二分木を検索してキーワードを見つけなければなりません。キーワードが表示されない場合は、検索したいキーワードを接頭辞として持っているツリーで、辞書的に次の文字列を見つけなければなりません。以前の基準。

次のコードは、正確な単語が見つからなかった後に検索するためのものです。

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

4

1 に答える 1

2

検索されたキーワードを含むすべての単語を出力するには、ツリーをトラバースする必要があります。これは、子孫のいずれかが一致するかどうかを事前に知る方法がないためです。

基本的な考え方

ツリーをトラバースするには、次のような関数を使用できます。

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

出力：

一致しない: [た]

一致: [トラバーサル]

一致: [travvv]

一致: [木]

一致: [tre]

一致: [木]

一致しません: [tx]

于 2016-01-12T01:12:39.827 に答える