搜索二叉树之字典实现

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

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

/*****************************************
*Date:2018年3月26日14:42:54
*Author: Meng
*WebSite:msyci.com
*QQ:3515955122
*****************************************/# include <stdio.h>
# include <stdlib.h>
# include <string.h>
#include<assert.h>typedef 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);elsereturn -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 <stdio.h>
# include <stdlib.h>
# include <string.h>
#include<assert.h>typedef 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);elsereturn -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;
}

运行结果：

二叉树遍历java，