搜索二叉树之字典实现

利用搜索二叉树判断一个单词是否拼写正确：

假设把所有单词都按照搜索树的性质插入到搜索二叉树中，我们判断一个单词拼写是否正确就是在树中查找该单词是否存在（查找key是否存在）。

/******************************************Date:2018年3月26日14:42:54*Author: Meng*WebSite:msyci.com*QQ:3515955122*****************************************/# include # include # include #includetypedef char* KeyType;typedef char* ValueType;typedef struct BSTreeNode{        struct BSTreeNode*  _left;        struct BSTreeNode*  _right;        KeyType  _key;        ValueType _value;}BSTreeNode;BSTreeNode *BuyTreeNode(KeyType x,ValueType value ) //创建节点{        BSTreeNode *node = (BSTreeNode*)malloc(sizeof(BSTreeNode));        assert(node);        node->_key = x;        node->_left = NULL;        node->_right = NULL;        node->_value = value;        return node;}//插入、查找函数int BSTreeNodeInsertR(BSTreeNode **tree,KeyType key, ValueType value) //搜索树的插入{        int tmp = 0;        if(*tree == NULL)        {                *tree = BuyTreeNode(key,value);                               return 0;        }        tmp  = strcmp((*tree)->_key,key);        if (tmp>0)                return BSTreeNodeInsertR(&(*tree)->_left,key,value);        else if (tmp<0)                return BSTreeNodeInsertR(&(*tree)->_right,key,value);        else                return -1;}BSTreeNode*  BSTreeNodeFindR(BSTreeNode* tree, KeyType  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;        }}void TestApplication(){                BSTreeNode *tree = NULL;                BSTreeNodeInsertR(&tree,"China","中国");                BSTreeNodeInsertR(&tree,"score","成绩");                BSTreeNodeInsertR(&tree,"char","字符");                BSTreeNodeInsertR(&tree,"int","×××");                BSTreeNodeInsertR(&tree,"float","浮点型");                printf("%s \n", BSTreeNodeFindR(tree,"char")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"int")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"float")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"China")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"score")->_value);                printf("%p \n", BSTreeNodeFindR(tree,"double"));                }int main(void){        TestApplication();        char c = getchar();        return 0;}

运行结果：

实现简单的中英文字典

/******************************************Date:2018年3月26日15:35:07*Author: Meng*WebSite:msyci.com*QQ:3515955122*****************************************/# include # include # include #includetypedef char* KeyType;typedef char* ValueType;typedef struct BSTreeNode{        struct BSTreeNode*  _left;        struct BSTreeNode*  _right;        KeyType  _key;        ValueType _value;}BSTreeNode;BSTreeNode *BuyTreeNode(KeyType x,ValueType value ) //创建节点{        BSTreeNode *node = (BSTreeNode*)malloc(sizeof(BSTreeNode));        assert(node);        node->_key = x;        node->_left = NULL;        node->_right = NULL;        node->_value = value;        return node;}//插入、查找函数int BSTreeNodeInsertR(BSTreeNode **tree,KeyType key, ValueType value) //搜索树的插入{        int tmp = 0;        if(*tree == NULL)        {                *tree = BuyTreeNode(key,value);                               return 0;        }        tmp  = strcmp((*tree)->_key,key);        if (tmp>0)                return BSTreeNodeInsertR(&(*tree)->_left,key,value);        else if (tmp<0)                return BSTreeNodeInsertR(&(*tree)->_right,key,value);        else                return -1;}BSTreeNode*  BSTreeNodeFindR(BSTreeNode* tree, KeyType  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;        }}void TestApplication(){                BSTreeNode *tree = NULL;                BSTreeNodeInsertR(&tree,"China","中国");                BSTreeNodeInsertR(&tree,"score","成绩");                BSTreeNodeInsertR(&tree,"char","字符");                BSTreeNodeInsertR(&tree,"int","×××");                BSTreeNodeInsertR(&tree,"float","浮点型");                printf("%s \n", BSTreeNodeFindR(tree,"char")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"int")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"float")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"China")->_value);                printf("%s \n", BSTreeNodeFindR(tree,"score")->_value);                printf("%p \n", BSTreeNodeFindR(tree,"double"));                }int main(void){        TestApplication();        char c = getchar();        return 0;}

运行结果：