用java语言实现IP地址字典树
字典树,又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
字典树示例:
字典树的基本性质:
(1)根节点不包含字符,除根节点外每一个节点都只包含一个字符;
(2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
(3)每个节点的所有子节点包含的字符都不相同。
字典树的基本操作有:查找、插入和删除,
搜索字典项目的方法为:
(1)从根结点开始一次搜索;
(2)取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
(3)在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4)迭代过程……
(5)在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
根据字典树的上述特性,设计一种字典树,实现下列要求:
(1)该字典树能够实现对IP地址的查找。IP地址采用点分形式表示,如:192.168.1.1,即字典树每个节点只能包含0-9和”.”十一个字符中的一个。
(2)该字典树具有插入和查找和统计的功能
(3)用一组IP地址(期中一些IP地址以192开始)初始化该字典树
(4)在该字典树中查找以192开始的IP地址的个数,并打印出查找结果。
(5)查找10.10.10.10是否在该字典数据中存在,并打印出查找结果。