温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

搜索二叉树之字典实现

发布时间:2020-07-07 16:14:43 来源:网络 阅读:593 作者:liam2199 栏目:软件技术


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

    假设把所有单词都按照搜索树的性质插入到搜索二叉树中,我们判断一个单词拼写是否正确就是在树中查找该单词是否存在(查找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);
	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 <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);
	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;
}

运行结果:

搜索二叉树之字典实现


向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI