搜索二叉樹基本概念請(qǐng)看上篇博客
這兩個(gè)問(wèn)題都是典型的K（key）V（value）問(wèn)題，我們用KV算法解決。

成都創(chuàng)新互聯(lián)于2013年創(chuàng)立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站制作網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元惠濟(jì)做網(wǎng)站,已為上家服務(wù),為惠濟(jì)各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話:18980820575

1. 判斷一個(gè)單詞是否拼寫正確：假設(shè)把所有單詞都按照搜索樹的性質(zhì)插入到搜索二叉樹中，我們判斷一個(gè)單詞拼寫是否正確就是在樹中查找該單詞是否存在（查找key是否存在）。

結(jié)構(gòu)聲明下

typedef char* KeyType;

typedef struct BSTreeNode 
{
    struct BSTreeNode *_left;
    struct BSTreeNode *_right;

    KeyType _key;
}BSTreeNode;

插入，查找函數(shù)代碼如下：

int BSTreeNodeInsertR(BSTreeNode **tree,KeyType key) //搜索樹的插入
{
    int tmp = 0;
    if(*tree == NULL)
    {
        *tree = BuyTreeNode(key);
        return 0;
    }

    tmp  = strcmp((*tree)->_key,key);
    if (tmp>0)
        return BSTreeNodeInsertR(&(*tree)->_left,key);
    else if (tmp<0)
        return BSTreeNodeInsertR(&(*tree)->_right,key);
    else
        return -1;
}

BSTreeNode *BSTreeNodeFindR(BSTreeNode *tree,KeyType const key) //查找
{
    int tmp = 0;
    if (!tree)
        return NULL;

    tmp = strcmp(tree->_key,key);
    if (tmp > 0)
        return BSTreeNodeFindR(tree->_left,key);
    else if (tmp < 0)
        return BSTreeNodeFindR(tree->_right,key);
    else
        return tree;
}

測(cè)試代碼：

void TestApplication()
{
    BSTreeNode *tree = NULL;

    BSTreeNodeInsertR(&tree,"hello");
    BSTreeNodeInsertR(&tree,"world");
    BSTreeNodeInsertR(&tree,"int");
    BSTreeNodeInsertR(&tree,"char");
    BSTreeNodeInsertR(&tree,"float");
    BSTreeNodeInsertR(&tree,"double");

    printf("%s \n", BSTreeNodeFindR(tree,"char")->_key);
    printf("%s \n", BSTreeNodeFindR(tree,"double")->_key);
    printf("%s \n", BSTreeNodeFindR(tree,"int")->_key);
    printf("%s \n", BSTreeNodeFindR(tree,"float")->_key);
    printf("%s \n", BSTreeNodeFindR(tree,"hello")->_key);
    printf("%s \n", BSTreeNodeFindR(tree,"world")->_key);
    printf("%p \n", BSTreeNodeFindR(tree,"chars"));
    printf("%p \n", BSTreeNodeFindR(tree,"str"));
}

測(cè)試結(jié)果:

構(gòu)建測(cè)試案例盡量構(gòu)建全面，防止特殊情況被忽略。