数据结构 - 7（Map和Set 15000字详解）

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
  public Node search(int key) {
    Node cur = root; // 当前结点为根结点
    while (cur != null) { // 当前结点不为空时继续循环
      if (key == cur.key) { // 如果找到结点的值等于 key
        return cur; // 返回当前结点
      } else if (key < cur.key) { // 如果 key 小于当前结点的值
        cur = cur.left; // 继续在左子树中查找
      } else { // 如果 key 大于当前结点的值
        cur = cur.right; // 继续在右子树中查找
      }
    }
    return null; // 搜索树中未找到 key，返回 null
  }
  // 插入操作，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) { // 如果 key 已经存在于树中
        return false; // 返回插入失败
      } else if (key < cur.key) { // 如果 key 小于当前结点的值
        parent = cur; // 更新父结点为当前结点
        cur = cur.left; // 继续在左子树中查找
      } else { // 如果 key 大于当前结点的值
        parent = cur; // 更新父结点为当前结点
        cur = cur.right; // 继续在右子树中查找
      }
    }
    Node node = new Node(key); // 新建结点
    if (key < parent.key) { // 如果 key 小于父结点的值
      parent.left = node; // 将新结点插入左子树
    } else { // 如果 key 大于父结点的值
      parent.right = node; // 将新结点插入右子树
    }
    return true; // 返回插入成功
  }
  // 删除操作，成功返回 true，失败返回 false
  // 获取以指定结点为根的子树的最小结点
private Node getMin(Node node) {
  while (node.left != null) {
    node = node.left;
  }
  return node;
}
// 删除操作，return 值为 true 表示删除成功，false 表示删除失败
public boolean remove(int key) {
  Node cur = root; // 当前结点为根结点
  Node parent = null; // 父结点为空
  while (cur != null) { // 当前结点不为空时继续循环
    if (key == cur.key) { // 如果找到要删除的结点
      break; // 跳出循环
    } else if (key < cur.key) { // 如果 key 小于当前结点的值
      parent = cur; // 更新父结点为当前结点
      cur = cur.left; // 继续在左子树中查找
    } else { // 如果 key 大于当前结点的值
      parent = cur; // 更新父结点为当前结点
      cur = cur.right; // 继续在右子树中查找
    }
  }
  if (null == cur) { // 当前元素不在搜索树中
    return false; // 返回删除失败
  }
  // 如果 cur 的左孩子不存在
  if (cur.left == null) {
    // 如果 cur 是根结点
    if (parent == null) {
      root = cur.right; // 将右孩子作为根结点
    } else if (cur == parent.left) { // 如果 cur 是父结点的左孩子
      parent.left = cur.right; // 将 cur 的右孩子赋给父结点的左孩子
    } else { // 如果 cur 是父结点的右孩子
      parent.right = cur.right; // 将 cur 的右孩子赋给父结点的右孩子
    }
  }
  // 如果 cur 的右孩子不存在
  else if (cur.right == null) {
    // 如果 cur 是根结点
    if (parent == null) {
      root = cur.left; // 将左孩子作为根结点
    } else if (cur == parent.left) { // 如果 cur 是父结点的左孩子
      parent.left = cur.left; // 将 cur 的左孩子赋给父结点的左孩子
    } else { // 如果 cur 是父结点的右孩子
      parent.right = cur.left; // 将 cur 的左孩子赋给父结点的右孩子
    }
  }
  // 如果 cur 的左右孩子都存在
  else {
    Node successor = getMin(cur.right); // 获取右子树中的最小结点
    int successorKey = successor.key; // 保存该结点的值
    remove(successor.key); // 递归删除该结点
    cur.key = successorKey; // 将后继结点的值替换到要删除的结点上
  }
  return true; // 返回删除成功
}
}

import java.util.*;
public class MapEntryExample {
    public static void main(String[] args) {
        // 创建一个Map，并添加一些键值对
        Map<String, Integer> map = new HashMap<>();
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Orange", 3);
        // 使用entrySet()方法获取Map中所有的键值对
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        // 遍历键值对并执行操作
        for (Map.Entry<String, Integer> entry : entries) {
            // 获取键
            String key = entry.getKey();
            // 获取值
            Integer value = entry.getValue();
            // 打印键值对
            System.out.println("Key: " + key + ", Value: " + value);
            // 替换值为指定值
            entry.setValue(value * 10);
        }
        // 打印替换后的键值对
        System.out.println("After replacing values:");
        for (Map.Entry<String, Integer> entry : entries) {
            System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
        }
    }
}

Key: Apple, Value: 1
Key: Banana, Value: 2
Key: Orange, Value: 3
After replacing values:
Key: Apple, Value: 10
Key: Banana, Value: 20
Key: Orange, Value: 30

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.Collection;
public class MapEntryExample {
    public static void main(String[] args) {
        // 创建一个Map对象
        Map<String, Integer> scores = new HashMap<>();
        // 添加元素到Map
        scores.put("Alice", 90);
        scores.put("Bob", 85);
        scores.put("Charlie", 95);
        // 获取指定key的value
        Integer aliceScore = scores.get("Alice");
        System.out.println("Alice的成绩是：" + aliceScore);
        // 获取指定key的value，如果key不存在则返回默认值
        Integer davidScore = scores.getOrDefault("David", 0);
        System.out.println("David的成绩是：" + davidScore);
        // 设置指定key的value
        scores.put("Bob", 88);
        System.out.println("Bob的新成绩是：" + scores.get("Bob"));
        // 删除指定key的映射关系
        scores.remove("Charlie");
        System.out.println("Charlie的成绩已删除，现在的Map大小是：" + scores.size());
        // 获取所有的key集合
        Set<String> keySet = scores.keySet();
        System.out.println("所有的学生姓名：" + keySet);
        // 获取所有的value集合
        Collection<Integer> values = scores.values();
        System.out.println("所有的学生成绩：" + values);
        // 获取所有的key-value映射关系
        Set<Map.Entry<String, Integer>> entrySet = scores.entrySet();
        for (Map.Entry<String, Integer> entry : entrySet) {
            String name = entry.getKey();
            Integer score = entry.getValue();
            System.out.println(name + " 的成绩是：" + score);
        }
        // 判断是否包含指定的key
        boolean containsAlice = scores.containsKey("Alice");
        System.out.println("是否包含 Alice：" + containsAlice);
        // 判断是否包含指定的value
        boolean contains85 = scores.containsValue(85);
        System.out.println("是否包含成绩 85：" + contains85);
    }
}

Alice的成绩是：90
David的成绩是：0
Bob的新成绩是：88
Charlie的成绩已删除，现在的Map大小是：2
所有的学生姓名：[Alice, Bob]
所有的学生成绩：[90, 88]
Alice 的成绩是：90
Bob 的成绩是：88
是否包含 Alice：true
是否包含成绩 85：false

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class SetExample {
    public static void main(String[] args) {
        // 创建一个HashSet对象
        Set<String> set = new HashSet<>();
        // 使用add方法添加元素到set中
        set.add("Apple");
        set.add("Banana");
        set.add("Orange");
        set.add("Grape");
        set.add("Apple"); // 重复元素，不会被添加成功
        // 打印set中的元素个数
        System.out.println("Set size: " + set.size()); // 输出: Set size: 4
        // 判断元素是否存在于set中
        System.out.println("Set contains Apple: " + set.contains("Apple")); // 输出: Set contains Apple: true
        // 使用iterator方法获取set的迭代器
        Iterator<String> iterator = set.iterator();
        // 使用while循环通过迭代器遍历set中的元素
        System.out.print("Set elements: ");
        while (iterator.hasNext()) {
            String element = iterator.next();
            System.out.print(element + " "); // 输出: Set elements: Apple Banana Orange Grape
        }
        System.out.println();
        // 从set中移除特定的元素
        set.remove("Orange");
        // 打印移除元素之后的set
        System.out.println("Set after removal: " + set); // 输出: Set after removal: [Apple, Banana, Grape]
        // 检测set是否为空
        System.out.println("Set is empty: " + set.isEmpty()); // 输出: Set is empty: false
        // 将set中的元素转换为数组
        Object[] array = set.toArray();
        // 打印转换后的数组元素
        System.out.print("Array elements: ");
        for (Object element : array) {
            System.out.print(element + " "); // 输出: Array elements: Apple Banana Grape
        }
        System.out.println();
        // 创建另一个集合
        Set<String> anotherSet = new HashSet<>();
        anotherSet.add("Apple");
        anotherSet.add("Banana");
        // 检查集合anotherSet中的元素是否都在set中存在
        boolean containsAll = set.containsAll(anotherSet);
        System.out.println("Set contains all elements from anotherSet: " + containsAll); // 输出: Set contains all elements from anotherSet: true
        // 将另一个集合中的元素添加到set中
        boolean addedAll = set.addAll(anotherSet);
        System.out.println("Elements added from anotherSet: " + addedAll); // 输出: Elements added from anotherSet: false (因为已经存在了，所以没有添加成功)
    }
}