trie树java_【数据结构】Trie树的应用：查询IP地址的ISP（Java实现）
查詢IP地址的ISP
給定一個IP地址，如何查詢其所屬的ISP，如：中國移動(ChinaMobile)，中國電信(ChinaTelecom)，中國鐵通(ChinaTietong)？
現(xiàn)在網(wǎng)上有ISP的IP地址區(qū)段可供下載，比如中國移動的IP地址段
103.20.112.0/22
103.21.176.0/22
111.0.0.0/10
112.0.0.0/10
117.128.0.0/10
120.192.0.0/10
183.192.0.0/10
211.103.0.0/17
211.136.0.0/14
211.140.0.0/15
211.142.0.0/17
211.142.128.0/17
211.143.0.0/16
218.200.0.0/14
218.204.0.0/15
218.206.0.0/15
221.130.0.0/15
221.176.0.0/13
223.112.0.0/14
223.116.0.0/15
223.120.0.0/13
223.64.0.0/11
223.96.0.0/12
36.128.0.0/10
39.128.0.0/10
上述網(wǎng)絡(luò)地址是CIDR記法：IP地址/網(wǎng)絡(luò)id位數(shù)，其中IP地址分為兩部分
網(wǎng)絡(luò)id
主機id
比如，192.168.23.35/21，其子網(wǎng)掩碼為11111111 11111111 11111000 00000000即255.255.248.0，網(wǎng)絡(luò)ID：192.168.00010111
ip地址103.20.112.168，發(fā)現(xiàn)與103.20.112.0/22前22位相匹配，則此IP地址屬于中國移動
Trie樹實現(xiàn)查詢
Trie樹使用公共前綴，降低查詢時間，減小了存儲空間。為了構(gòu)建Trie樹，將IP地址二進制化，這樣Trie樹變成了一棵二叉樹，左孩子節(jié)點為0，右孩子節(jié)點為1。葉子節(jié)點存儲IP地址所對應(yīng)的ISP。
Trie樹的Java實現(xiàn)
/*
* Trie樹，用于存儲、檢索ip地址
* 葉子節(jié)點標記為ip地址對應(yīng)的ISP
*/
public class TrieTree{
private Node root = null; //根節(jié)點
/*二叉樹的節(jié)點*/
private static class Node{
String element; //非葉子節(jié)點為空 葉子節(jié)點標記為ISP
Node[] children; //左孩子節(jié)點為0 右孩子節(jié)點為1
public Node() {
element = "";
children = new Node[2];
for (int i = 0; i < children.length; i++) {
children[i] = null;
}
}
}
public TrieTree() {
root = new Node();
}
/*插入ip地址*/
public void insert(Node root, String ipAddress, String isp) {
if(ipAddress.length() > 32) {
System.out.println("ip地址處理錯誤");
} else {
Node crawl = root;
for(int i=0; i
int index = (int) ipAddress.charAt(i) - ‘0‘;
if(crawl.children[index] == null) {
crawl.children[index] = new Node();
}
crawl = crawl.children[index];
}
crawl.element = isp;
}
}
public void insert(String ipAddress, String isp) {
insert(root, ipAddress, isp);
}
/*
* 檢索ip地址，返回其所對應(yīng)的ISP
* 若不在Trie樹中，則返回null
* */
public String search(String binaryIP) {
Node crawl = root;
for(int i = 0; crawl.element.length() == 0; i++) {
int index = (int) binaryIP.charAt(i) - ‘0‘;
if(crawl.children[index] == null) {
return null;
}
crawl = crawl.children[index];
}
return crawl.element;
}
}
IP地址格式化
下面的class給出兩個方法，實現(xiàn)
將IP地址轉(zhuǎn)變成二進制
從CIDR記法的IP地址中得到網(wǎng)絡(luò)ID部分
/*
* IP地址CIDR記法：network.host/size
* 比如：103.20.112.0/22
* 功能：將IP地址轉(zhuǎn)換成其network地址
*/
public class IPFormat{
/*將ip地址轉(zhuǎn)換成32位的二進制*/
public static String toBinaryNumber(String ipAddress) {
String[] octetArray = ipAddress.split("\\.");
String binaryNumber = "";
for(String str: octetArray) {
int octet = Integer.parseInt(str, 10);
String binaryOctet = Integer.toBinaryString(octet);
int bolength = binaryOctet.length();
if(bolength < 8) {
for (int i = 0; i < 8 - bolength; i++) {
binaryOctet = ‘0‘ + binaryOctet; //補前導(dǎo)0
}
}
binaryNumber += (binaryOctet);
}
return binaryNumber;
}
/*獲取network地址部分*/
public static String getNetworkAddress(String cidrAddress) {
String[] cidrArray = cidrAddress.split("/");
String binaryNumber = toBinaryNumber(cidrArray[0]);
int size = Integer.parseInt(cidrArray[1]);
return binaryNumber.substring(0, size);
}
/*main方法用于測試*/
public static void main(String[] args) {
String ip = "103.20.112.0/20";
String bn = getNetworkAddress(ip);
System.out.println(bn);
}
}
總結(jié)
以上是生活随笔為你收集整理的trie树java_【数据结构】Trie树的应用：查询IP地址的ISP（Java实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： sqlbulkcopy mysql_c#
- 下一篇： coloros基于java_基于Andr