数据结构从青铜到王者第十八话---Map和Set（1）

public class BinarySearchTree {
    public static class Node {
        int key;
        Node left;
        Node right;
 
        public Node(int key) {
            this.key = key;
        }
    }
 
    private Node root = null;
 
    /**
     * 在搜索树中查找 key，如果找到，返回 key 所在的结点，否则返回 null
     * @param key
     * @return
     */
    public Node search(int key) {
        Node cur = root;
        while (cur != null) {
            if (key == cur.key) {
                return cur;
            } else if (key < cur.key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
 
        return null;
    }
 
    /**
     * 插入
     * @param key
     * @return true 表示插入成功, false 表示插入失败
     */
    public boolean insert(int key) {
        if (root == null) {
            root = new Node(key);
            return true;
        }
 
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                return false;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
 
        Node node = new Node(key);
        if (key < parent.key) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        return true;
    }
 
    /**
     * 删除成功返回 true，失败返回 false
     * @param key
     * @return
     */
    public boolean remove(int key) {
        Node cur = root;
        Node parent = null;
        while (cur != null) {
            if (key == cur.key) {
                break;
            } else if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else {
                parent = cur;
                cur = cur.right;
            }
        }
        
        // 该元素不在二叉搜索树中
        if(null == cur){
            return false;
        }
 
        /*
        根据cur的孩子是否存在分四种情况
        1. cur左右孩子均不存在
        2. cur只有左孩子
        3. cur只有右孩子
        4. cur左右孩子均存在
        看起来有四种情况，实际情况1可以与情况2或者3进行合并，只需要处理是那种情况即可
        除了情况4之外，其他情况可以直接删除
        情况4不能直接删除，需要在其子树中找一个替代节点进行删除
        */
        // 请同学们根据上课掌握内容，完成删除的关键部分代码
        return true;
    }
}

import java.util.TreeMap;
import java.util.Map;
 
public static void TestMap(){
    Map<String, String> m = new TreeMap<>();
 
    // put(key, value):插入key-value的键值对
    // 如果key不存在，会将key-value的键值对插入到map中,返回null
    m.put("林冲", "豹子头");
    m.put("鲁智深", "花和尚");
    m.put("武松", "行者");
    m.put("宋江", "及时雨");
    String str = m.put("李逵", "黑旋风");
    System.out.println(m.size());
    System.out.println(m);
 
    // put(key,value): 注意key不能为空，但是value可以为空
    // key如果为空，会抛出空指针异常
    //m.put(null, "花名");
    str = m.put("无名", null);
    System.out.println(m.size());
 
    // put(key, value):
    // 如果key存在，会使用value替换原来key所对应的value，返回旧value
    str = m.put("李逵", "铁牛");
 
    // get(key): 返回key所对应的value
    // 如果key存在，返回key所对应的value
    // 如果key不存在，返回null
    System.out.println(m.get("鲁智深"));
    System.out.println(m.get("史进"));
 
    //GetOrDefault(): 如果key存在，返回与key所对应的value，如果key不存在，返回一个默认值
    System.out.println(m.getOrDefault("李逵", "铁牛"));
    System.out.println(m.getOrDefault("史进", "九纹龙"));
    System.out.println(m.size());
 
    //containKey(key)：检测key是否包含在Map中，时间复杂度：O(logN)
    // 按照红黑树的性质来进行查找
    // 找到返回true，否则返回false
    System.out.println(m.containsKey("林冲"));
    System.out.println(m.containsKey("史进"));
 
    // containValue(value): 检测value是否包含在Map中，时间复杂度: O(N)
    // 找到返回true，否则返回false
    System.out.println(m.containsValue("豹子头"));
    System.out.println(m.containsValue("九纹龙"));
 
 
    // 打印所有的key
    // keySet是将map中的key防止在Set中返回的
    for(String s : m.keySet()){
        System.out.print(s + " ");
    }
    System.out.println();

    // 打印所有的value
    // values()是将map中的value放在collect的一个集合中返回的
    for(String s : m.values()){
        System.out.print(s + " ");
    }
    System.out.println();
    // 打印所有的键值对
    // entrySet(): 将Map中的键值对放在Set中返回了
    for(Map.Entry<String, String> entry : m.entrySet()){
        System.out.println(entry.getKey() + "--->" + entry.getValue());
    }
    System.out.println();
}