字首樹

字首樹是一個非常好用的資料結構，特别是針對求相同字首字元串有多少個的時候。如圖

字首樹.jpg

下面是字首樹的一些代碼操作。

public class TrieTree {

    //内部類
    private class TrieNode{
        public int path;
        public int end;
        public TrieNode nexts[];

        public TrieNode(){
            this.path = 0;
            this.end = 0;
            this.nexts = new TrieNode[26];//這裡假設是26個字母，如果有其他的情況，參照ascii表
        }
    }

    private TrieNode root;

    public TrieTree(){
        this.root = new TrieNode();
    }

    //插入操作
    public void insert(String word){
        if(word == null || word.length() == 0)
            return;
        char[] chs = word.toCharArray();
        TrieNode node = this.root;
        int index = 0;
        for(int i = 0; i < chs.length; i++){
            index = chs[i] - 'a';
            if(node.nexts[index] == null){
                node.nexts[index] = new TrieNode();
            }
            node = node.nexts[index];
            node.path++;
        }
        node.end++;
    }

    //查找操作
    public int search(String word){
        if(word == null || word.length() == 0)
            return 0;
        char[] chs = word.toCharArray();
        TrieNode node = this.root;
        int index = 0;
        for(int i = 0; i < chs.length; i++){
            index = chs[i] - 'a';
            if(node.nexts[index] == null){
                return 0;
            }
            node = node.nexts[index];
        }
        return node.end;
    }

    //删除操作
    public void delete(String word){
        if(search(word) != 0){
            char[] chs = word.toCharArray();
            TrieNode node = this.root;
            int index = 0;
            for(int i = 0; i < chs.length; i++){
                index = chs[i] - 'a';
                if(--node.nexts[index].path == 0){
                    node.nexts[index] = null;
                    return;
                }
                node = node.nexts[index];
            }
            node.end--;
        }
    }

    //判斷字首相同的字元串個數
    public int prefix(String prefix){
        if(prefix == null)
            return 0;
        char[] chs = prefix.toCharArray();
        TrieNode node = root;
        int index = 0;
        for(int i = 0; i < chs.length; i++){
            index = chs[i] - 'a';
            if(node.nexts[index] == null)
                return 0;
            node = node.nexts[index];
        }
        return node.path;
    }

    public static void main(String[] args) {
        TrieTree root = new TrieTree();
        root.insert("abc");
        root.insert("bdc");
        root.insert("abe");
        root.insert("abfg");
        System.out.println(root.prefix("ab"));
        root.delete("abe");
        System.out.println(root.prefix("ab"));
    }
}