package arithmetic;
import java.util.*;
class DicNode
{
int count;//当前字符在这个位置出现的次数
int next[] = new int[26];//其下一个字符的指针 ,next[i] 中， i 表示字符 ch , next[i] 表示地址
public String toString()
{
StringBuffer s = new StringBuffer();
s.append(count+" |");
for(int i =0;i<26;i++)
{
if(next[i]==0)
s.append(" | ");
else
s.append((char)(i+'a')+"| ");
}
return s.toString();
}
}
public class DicTree {
static DicNode tree[] = new DicNode[10000];
public static void main(String args[])
{
for(int i =0;i<tree.length;i++)
tree[i]= new DicNode();
create("abcdefg");
create("ab");
create("google");
for(int i =0;i<7;i++)
{
System.out.print(i+" ");
System.out.println(tree[i].toString());
}
System.out.println(find("google"));
del("google");
System.out.println(find("google"));
}
public static void create(String str)
{
int treepos =1;
int index = 0;
for(int i = 0;i<str.length();i++)
{
int ch = str.charAt(i)-'a';
if(tree[tree[index].next[ch]].count==0) //表明 字符 ch 还不在树中
{
tree[index].next[ch]=treepos;// tree[index].next[ch] 表示指向 ch 结点的孩子指针，里面存放的是 ch 在树中的位置，其值为索引
tree[treepos++].count=1;
}else
{
tree[tree[index].next[ch]].count++;
}
index = tree[index].next[ch]; //当前结点变为其孩子结点
}
}
public static int find(String str)//找出有没有以str 为参数的单词，如果有，在文件中出现几次，没有返回0
{
int index = 0;
for(int i =0;i<str.length();i++)
{
int ch = str.charAt(i)-'a';
if(tree[tree[index].next[ch]].count!=0) //表示出现过
index = tree[index].next[ch];
else
return 0;
}
return tree[index].count;
}
public static void del(String str)
{
int index =0 ;
if(find(str)==0)
{
System.out.println("this word not find...");
return ;
}
for(int i=0;i<str.length();i++)
{
int ch = str.charAt(i)-'a';
tree[tree[index].next[ch]].count--;
index=tree[index].next[ch];
}
}
}
/*
* 字典树建立
* 1.定义一个字典树的结点，最简单的是里面有两个变量，count 表示出现次数,next[i] i 可以直接表示字符，next[i]里面保存是地址，是孩子结点的地址,其实就是孩子结点在tree[] 数组里面的索引变量
* 2.循环单词的所有字符，建立树进，对于一个单词，只可能向下走，不能向回走
* 3.treepos 表示已经插入的结点的个数，index 表示在插入一个单词的字符时，走到当前结点在tree[] 里面的位置，也就是当前结点的位置
* 4.tree[index].next[ch] 表示当前结点的孩子结点中，保存字符 ch 的孩子结点的索引,靠，有点不好表达，要插入字符 b,
* tree[index].next[b-'a'] 表示的就是 当前所有结点中 字符为b 的结点， 那么 tree[index].next[b-'a'] 里面存放的值就是其孩子结点在tree[] 中的索引
* 5.如果其孩子结点中的count 值为0，那么就表示这个字符还没有插入树中，所以就要插入，
* 6.如果其孩子结点的count 值不为0，那就就直接count ++ 就可以了
* 7.无论存不存在，插入操作还是要继续下一个字符的，所以 index = tree[index].next[ch]
* 记住 tree[n].next[i] 中，i 表示的字符，next[i]是指针，指向其孩子结点为i 的指针，其值就是字符i 结点在tree[] 中的索引值
*
*
* 字典树的查找
*
* 1. 遍历单词，对于第一个字符从树根开始查找 ，查看当前结点的 ch 孩子结点里面count 是否为1 ，即 tree[tree[index].next[ch]].count 是否为1
* 2. 如果为1 ，则表明此字符存在，向下遍历，如果为1，则表示不存在，返回
* 3. 向下遍历为 index = treee[index].next[ch] ，这样会指向其孩子结点
*
*
*
* 字符树的删除
* 1. 如果单词在树中，那么遍历单词，如果于单词的每个字符找到在树中的位置 ，将其对应结点中的count--
* 2. index = tree[index].next[ch];
* */