java实现数据结构07.02（映射详解代码之自定义二分搜索树映射）

我会带着你远行 2023-06-23 05:58 42阅读 0赞

## 阅读本文章前请先阅读[java实现数据结构05（二分搜索树详解代码之自定义二分搜索树）][java_05] ##

## 基于二分搜索树创建的映射 ##

/** * @description: 基于二分搜索树创建的映射 * @author: liangrui * @create: 2019-12-17 16:53 **/
    public class BSTMap<K extends Comparable,V> implements Map<K,V> { 
    
        private class Node{ 
            public K key;
            public V value;
            public Node left,right;
    
            public Node(K key,V value){ 
                this.key=key;
                this.value=value;
                left=null;
                right=null;
            }
        }
    
        private Node root;
        private int size;
    
        public BSTMap(){ 
            root=null;
            size=0;
        }
    
        /** * 根据key查询节点 */
        private Node getNod(Node node,K k){ 
            if (node==null){ 
                return null;
            }
    
            if (k.compareTo(node.key)<0){ 
                return getNod(node.left,k);
            }else if (k.compareTo(node.key)>0){ 
                return getNod(node.right,k);
            }else { 
                return node;
            }
        }
    
        /** * 获取最大键所在节点 * @param node * @return */
        private Node getMaxNode(Node node){ 
            if (node.right==null){ 
                return node;
            }
            return getMaxNode(node.right);
        }
    
        /** * 获取最小键所在节点 * @param node * @return */
        private Node getMinNode(Node node){ 
            if (node.left==null){ 
                return node;
            }
            return getMaxNode(node.left);
        }
    
        /** * 删除最大键的节点 * @return */
        public K removeMax(){ 
            Node maxNode = getMaxNode(root);
            root=removeMaxNode(root);
            return maxNode.key;
        }
    
        private Node removeMaxNode(Node node){ 
            if (node.right==null){ 
                Node leftNode=node.left;
                node.left=null;
                size--;
                return leftNode;
            }
    
            node.right=removeMaxNode(node.right);
            return node;
        }
    
        /** * 删除最大键的节点 * @return */
        public K removeMin(){ 
            Node minNode=getMinNode(root);
            root=removeMinNode(root);
            return minNode.key;
        }
    
        private Node removeMinNode(Node node){ 
            if (node.left==null){ 
                Node rightNode=node.right;
                node.right=null;
                size--;
                return rightNode;
            }
            node.left=removeMinNode(node.left);
            return node;
        }
    
    
    
        @Override
        public void add(K k, V v) { 
            root=add(root,k,v);
        }
    
        private Node add(Node node, K k, V v) { 
            if (node==null){ 
                node=new Node(k,v);
                size++;
                return node;
            }
    
            if (k.compareTo(node.key)>0){ 
                node.right=add(node.right,k,v);
            }else if (k.compareTo(node.key)<0){ 
                node.left=add(node.left,k,v);
            }else { 
                node.value=v;
            }
            return node;
        }
    
        @Override
        public V remove(K k) { 
            Node delNode=getNod(root,k);
            if (delNode==null){ 
                throw new IllegalArgumentException(k+"doesn't exist.");
            }
            return remove(root,k).value;
        }
    
        private Node remove(Node node, K k) { 
            if (node==null){ 
                return null;
            }
    
            if (k.compareTo(node.key)>0){ 
                node.right=remove(node.right,k);
                return node;
            }else if (k.compareTo(node.key)<0){ 
                node.left=remove(node.left,k);
                return node;
            }else { 
                if (node.left==null){ 
                    Node rightNode=node.right;
                    node.right=null;
                    size--;
                    return rightNode;
                }
    
                if (node.right==null){ 
                    Node leftNode=node.left;
                    node.left=null;
                    size--;
                    return leftNode;
                }
    
                Node reNode=getMinNode(node.right);
                reNode.right=removeMinNode(node.right);
                reNode.left=node.left;
                node.left=node.right=null;
                return reNode;
            }
        }
    
        @Override
        public void set(K k, V v) { 
            Node node = getNod(root, k);
            if (node==null){ 
                throw new IllegalArgumentException(k+"doesn't exist.");
            }
            node.value=v;
        }
    
        @Override
        public V get(K k) { 
            return getNod(root,k).value;
        }
    
        @Override
        public boolean contains(K k) { 
            return getNod(root,k)!=null;
        }
    
        @Override
        public int getSize() { 
            return size;
        }
    
        @Override
        public boolean isEmpty() { 
            return size==0;
        }
    }

## 文件操作类 ##

此处用到自定义数组Array类，请阅读[java实现数据结构01(数组详解代码之自定义数组)][java_01]

import java.io.FileInputStream;
    import java.util.Scanner;
    import java.util.Locale;
    import java.io.File;
    import java.io.BufferedInputStream;
    import java.io.IOException;
    
    // 文件相关操作
    public class FileOperation { 
    
        // 读取文件名称为filename中的内容，并将其中包含的所有词语放进words中
        public static boolean readFile(String filename, Array<String> words){ 
    
            if (filename == null || words == null){ 
                System.out.println("filename is null or words is null");
                return false;
            }
    
            // 文件读取
            Scanner scanner;
    
            try { 
                File file = new File(filename);
                if(file.exists()){ 
                    FileInputStream fis = new FileInputStream(file);
                    scanner = new Scanner(new BufferedInputStream(fis), "UTF-8");
                    scanner.useLocale(Locale.ENGLISH);
                }else{ 
                    return false;
                }
            }catch(IOException ioe){ 
                System.out.println("Cannot open " + filename);
                return false;
            }
    
            // 简单分词
            // 这个分词方式相对简陋, 没有考虑很多文本处理中的特殊问题
            // 在这里只做demo展示用
            if (scanner.hasNextLine()) { 
    
                String contents = scanner.useDelimiter("\\A").next();
    
                int start = firstCharacterIndex(contents, 0);
                for (int i = start + 1; i <= contents.length(); )
                    if (i == contents.length() || !Character.isLetter(contents.charAt(i))) { 
                        String word = contents.substring(start, i).toLowerCase();
                        words.addLast(word);
                        start = firstCharacterIndex(contents, i);
                        i = start + 1;
                    } else { 
                        i++;
                    }
            }
            return true;
        }
    
        // 寻找字符串s中，从start的位置开始的第一个字母字符的位置
        private static int firstCharacterIndex(String s, int start){ 
            for( int i = start ; i < s.length() ; i ++ ){ 
                //Character.isLetter()判断字符是否为字母
                if(Character.isLetter(s.charAt(i))){ 
                    return i;
                }
            }
            return s.length();
        }
    }

## main测试 ##

此处用到自定义数组Array类，请阅读[java实现数据结构01(数组详解代码之自定义数组)][java_01]

public class Main { 
    
        public static void main(String[] args) { 
            Array<String> array=new Array<>();
            //将所有单词添加到array中
            FileOperation.readFile("pride-and-prejudice.txt",array);
            System.out.println("Total words:"+array.getSize());
    
            BSTMap<String,Integer> bstMap=new BSTMap<>();
            for (int i = 0; i < array.getSize(); i++) { 
                String word=array.get(i);
                //如果映射中存在该元素，则将其值+1
                if (bstMap.contains(word)){ 
                    bstMap.set(word,bstMap.get(word)+1);
                }else { 
                    //如果映射中不存在该元素，则添加该元素到映射
                    bstMap.add(word,1);
                }
            }
    
            //不同单词个数
            System.out.println("Different words:"+bstMap.getSize());
            //'pride'出现的频率
            System.out.println("Frequency of 'pride':"+bstMap.get("pride"));
            //'prejudice'出现的频率
            System.out.println("Frequency of 'prejudice':"+bstMap.get("prejudice"));
        }
    }

## 测试结果： ##

> Total words:125901  
> Different words:6530  
> Frequency of ‘pride’:53  
> Frequency of ‘prejudice’:11

## pride-and-prejudice.txt文件（傲慢与偏见）随便一个txt文件都可以测试（必须为英文） ##

[java_05]: https://blog.csdn.net/liangruilz/article/details/103572142
[java_01]: https://blog.csdn.net/liangruilz/article/details/103430382