当前位置：首页 > news >正文

Java：数据结构-MapSet

news 2024/10/30 14:55:43

搜索树

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树

搜索二叉树的操作

1.查找

public class BinarySearchTree {class TreeNode{TreeNode left;TreeNode right;public int val;public TreeNode(int val){this.val=val;}}public TreeNode root;public TreeNode search(int key){TreeNode cur=root;while (cur!=null) {if (cur.val == key) {return cur;} else if (cur.val < key) {cur = cur.right;} else {cur = cur.left;}}return null;}

2.插入

public class BinarySearchTree {class TreeNode{TreeNode left;TreeNode right;public int val;public TreeNode(int val){this.val=val;}}public TreeNode root;
public void insert(int key){if(root==null){root=new TreeNode(key);return;}TreeNode parent=null;TreeNode cur=root;TreeNode node=new TreeNode(key);while (cur!=null){if(cur.val<key){parent=cur;cur=cur.right;}else if(cur.val>key){parent=cur;cur=cur.left;}else {return;  //插入不能插入两个相同的数}}if(parent.val>key){parent.left=node;}else {parent.right=node;}}

3.删除

1. cur.left == null

1. cur 是 root，则 root = cur.right
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

2. cur.right == null

1. cur 是 root，则 root = cur.left 比特就业课
2. cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
3. cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

3. cur.left != null && cur.right != null

1. 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题

public class BinarySearchTree {class TreeNode{TreeNode left;TreeNode right;public int val;public TreeNode(int val){this.val=val;}}public TreeNode root;
public void remove(int key){TreeNode parent=null;TreeNode cur=root;while (cur!=null){if(cur.val<key){parent=cur;cur=cur.right;}else if(cur.val>key){parent=cur;cur=cur.left;}else {removeNode(parent,cur);return;}}}public void removeNode(TreeNode parent,TreeNode cur){if(cur.left==null){if(cur==root){root=cur.right;}else if(cur==parent.left){parent.left=cur.right;}else {parent.right=cur.right;}}else if(cur.right==null){if(cur==root){root=cur.left;}else if(cur==parent.left){parent.left=cur.left;}else {parent.left=cur.left;}}else {TreeNode targetParent=parent;TreeNode target=cur;while (target.left!=null){targetParent=target;target=target.left;}cur.val=target.val;if(targetParent.left==target){targetParent.left=target.right;}else {targetParent.right=target.right;}}}

Map 和 Set 是常用的接口，分别用于表示键值对和不重复的集合

Map

Map.Entry<K, V> 是 Map 接口的一个静态嵌套接口，表示 Map 中的一个键值对（entry）。它提供了对单个键值对的访问，使得可以在遍历 Map 时处理每个条目。K 表示键的类型，V 表示值的类型。

import java.util.HashMap;
import java.util.Map;public class Main {public static void main(String[] args) {Map<String, Integer> map = new HashMap<>();map.put("Alice", 25);map.put("Bob", 30);map.put("Charlie", 28);// 遍历 Mapfor (Map.Entry<String, Integer> entry : map.entrySet()) {String key = entry.getKey();Integer value = entry.getValue();System.out.println(key + ": " + value);}}
}

Map的常用的方法及使用

V get(Object key)	返回 key 对应的 value
V getOrDefault(Object key, V defaultValue)	返回 key 对应的 value，key 不存在，返回默认值
V put(K key, V value)	设置 key 对应的 value
V remove(Object key)	删除 key 对应的映射关系
Set keySet()	返回所有 key 的不重复集合
Collection values()	返回所有 value 的可重复集合
Set<Map,Integer<K,V>> entrySet()	返回所有的 key-value 映射关系
boolean containsKey(Object key)	判断是否包含 key
boolean containsValue(Object value)	判断是否包含 value

public class Test {public static void main(String[] args) {Map<String,Integer> map=new HashMap<>();map.put("h",012);map.put("p",123);map.put("l",234);map.put("k",456);map.put("m",567);map.put("n",789);map.get(123);map.get(234);map.get(234);map.get(567);map.getOrDefault(123,5);map.remove(123);}
}

注：

1. Map是一个接口，不能直接实例化对象，如果要实例化对象只能实例化其实现类TreeMap或者HashMap

2. Map中存放键值对的Key是唯一的，value是可以重复的

3. 在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，value可以为空。但是HashMap的key和value都可以为空。

4. Map中的Key可以全部分离出来，存储到Set中来进行访问(因为Key不能重复)。

5. Map中的value可以全部分离出来，存储在Collection的任何一个子集合中(value可能有重复)。

6. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入

Set

Set 是无重复元素的集合。Set 接口的常见实现有 HashSet、LinkedHashSet 和 TreeSet。其中，HashSet 无序，LinkedHashSet 按插入顺序保存，TreeSet 则按自然顺序排序。

Set常用的方法及其使用

public class Test {public static void main(String[] args) {Set<Integer> set=new HashSet<>();set.add(123);set.add(234);set.add(345);set.add(456);System.out.println(set);set.isEmpty();set.remove(123);set.remove(234);set.remove(345);set.remove(456);System.out.println(set);}

注：

1. Set是继承自Collection的一个接口类

2. Set中只存储了key，并且要求key一定要唯一

3. TreeSet的底层是使用Map来实现的，其使用key与Object的一个默认对象作为键值对插入到Map中的

4. Set最大的功能就是对集合中的元素进行去重

5. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

6. Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入

7. TreeSet中不能插入null的key，HashSet可以。

希望能对大家有所帮助！！！！！