搜索二叉树应用——简单字典实现

搜索二叉树基本概念请看上篇博客
这两个问题都是典型的K（key）V（value）问题，我们用KV算法解决。

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

结构声明下

typedef char* KeyType; typedef struct BSTreeNode { struct BSTreeNode *_left; struct BSTreeNode *_right; KeyType _key; }BSTreeNode;

插入，查找函数代码如下：

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; }

测试代码：

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")); }

测试结果:

2. 请模拟实现一个简单的字典（简单的中英文字典）

结构构建

typedef char* KeyType; typedef int ValueType; typedef struct BSTreeNode { struct BSTreeNode *_left; struct BSTreeNode *_right; KeyType _key; ValueType _count; }BSTreeNode;

查找函数与上面相同，插入函数有所改变。

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; }

测试代码：

void test() { BSTreeNode *tree = NULL; BSTreeNodeInsertR(&tree,"hello","你好"); BSTreeNodeInsertR(&tree,"world","世界"); 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,"hello")->_value); printf("%s \n", BSTreeNodeFindR(tree,"world")->_value); printf("%p \n", BSTreeNodeFindR(tree,"double")); }

测试结果

构建测试案例尽量构建全面，防止特殊情况被忽略。