二叉搜索树，Map，Set，LeetCode刷题

二叉搜索树，Map，Set

1. 二叉搜索树
2. 二叉搜索树的模拟实现
- 1.1 插入操作
- 1.2 查找操作
- 1.3 删除操作
3. 二叉搜索树时间复杂度分析
4. TreeMap和TreeSet
5. Map
- 5.1 Map的常用方法
- 5.2 Map.Entry<K,V>
6. Set
- 6.1 Set的常用方法
LeetCode刷题
- 1. 二叉搜索树与双向链表

1. 二叉搜索树

二叉搜索树是一棵特殊的树，它是“有序的”，因此又被叫做二叉排序树，它具有以下的性质：

根节点左子树的任意元素都小于根节点的元素
根节点右子树的任意元素都大于根节点的元素
上述两条性质对于该树的任意子树都成立

2. 二叉搜索树的模拟实现

待实现代码：

public class BinarySearchTree {static class TreeNode {public int key;public TreeNode left;public TreeNode right;TreeNode(int key) {this.key = key;}}public TreeNode root;/*** 插入一个元素* @param key*/public boolean insert(int key) {return true;}//查找key是否存在public TreeNode search(int key) {return null;}//删除key的值public boolean remove(int key) {return false;}
}

1.1 插入操作

插入一个新节点，首先要遍历原树，找到一个合适的位置去插入，而插入的节点会成为新树的叶子节点

具体实现如下：

    public boolean insert(int key) {if(root == null) {root = new TreeNode(key);return true;}TreeNode node = new TreeNode(key);TreeNode cur = root;TreeNode curParent = null;//找插入新节点的合适位置while(cur != null) {curParent = cur;if(cur.key < key) {cur = cur.right;}else if(cur.key > key) {cur = cur.left;}else {return false;}}//进行插入新节点操作if(curParent.key < key) {curParent.right = node;}else {curParent.left = node;}return true;}

1.2 查找操作

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

1.3 删除操作

二叉搜索树的删除操作是三个操作里最难的，难在需要考虑的情况较多，需要不断用测试用例去调试代码，可以用下面这个链接去验证代码是否还有遗漏的情况

题目链接：NC297 删除一个二叉搜索树中的节点

实现代码：

    public boolean remove(int key) {TreeNode cur = root;TreeNode curParent = root;//找到删除节点位置while(cur != null) {if(cur.key < key) {curParent = cur;cur = cur.right;}else if(cur.key > key) {curParent = cur;cur = cur.left;}else {break;}}if(cur == null) {return true;//节点不存在}TreeNode del = cur;//待删除节点TreeNode delParent = curParent;//待删除节点的父亲节点//找到待删除节点左子树的最大值（即左子树最右边的元素），用来替换法1待删除节点值if(del.left == null) {//待删除节点无左子树if(del.key > delParent.key) {delParent.right = del.right;}else if(del.key < delParent.key){delParent.left = del.right;}else {//此时，待删除节点为根节点root = root.right;}}else {//找到待删除节点左子树的最大值（即左子树最右边的元素），用来替换待删除节点值curParent = cur;cur = cur.left;while(cur.right != null) {curParent = cur;cur = cur.right;}del.key = cur.key;if(curParent == del) {//此时，待删除节点的左子树根节点无右子树curParent.left = cur.left;}else {curParent.right = cur.left;}}return true;}

3. 二叉搜索树时间复杂度分析

在最优情况下，即二叉搜索树是一棵完全二叉树，时间复杂度是O（log₂N）
在最坏情况下，即二叉搜索树是一棵单支二叉树，时间复杂度是O（N）

最优情况：
在这里插入图片描述
最坏情况：

4. TreeMap和TreeSet

TreeMap和TreeSet底层都是一棵红黑树，而红黑树是一棵近似平衡的二叉搜索树。TreeMap是Map接口的一个实现类，TreeSet是Set接口的一个实现类

5. Map

Map是一个接口，其实现需要依靠TreeMap类或者HashMap类。Map里存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。这就类比于一个集合，这个集合里放的都是具有两个元素的集合，例如：{{“abc”, 2}, {“cde”, 3}}

5.1 Map的常用方法

V put (K key, V value)
用于往map中存放键值对

演示1：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);System.out.println(map);//Map类可以直接输出}
}

输出结果：
在这里插入图片描述
演示2：

map类存储的key是不能重复的，但往map里put同一个key，是可以的，只是在key里依然只会保存一个key，只是key对应的value会发生更新

如果key不存在，会将key-value的键值对插入到map中,返回null
如果key存在，会使用value替换原来key所对应的value，返回旧value
put(key,value): 注意key不能为空，但是value可以为空。 key如果为空，会抛出空指针异常

V get(Object key)
用于得到key对应的value

演示：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);Integer val = map.get("cde");System.out.println(val);}
}

输出结果为：3

注意： 该方法接收返回值时，建议使用包装类而不是基本数据类型，因为使用基本数据类型会发生自动拆箱，会调用intValue方法，假如该key不存在，就会返回null，这时如果进行拆箱的话，就会出现空指针异常
在这里插入图片描述

3. V getOrDefault(Object key, V defaltValue)
该方法与get方法的不同之处在于有一个默认值，如果key存在，则返回key对应的value值；如果key不存在，就会返回这个默认值

演示：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);Integer val = map.getOrDefault("cde2",-1);System.out.println(val);}
}

输出结果为：-1

V remove(Object key)
删除key对应的映射关系

演示：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);System.out.println("删除前：" + map);map.remove("abc");System.out.println("删除后：" +map);}
}

输出结果：
在这里插入图片描述

Set<K> keySet()
返回所有的key的不重复集合，keySet()是将map中的key放在set中返回的

演示：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);// 打印所有的keySet<String> set = map.keySet();System.out.println(set);for(String s : set) {System.out.print(s + " ");}}
}

输出结果：
在这里插入图片描述

Collection<V> values()
返回所有value的可重复集合，values()是将map中的value放在collect的一个集合中返回的

演示：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);// 打印所有的valueCollection<Integer> collection = map.values();System.out.println(collection);for(Integer x: collection) {System.out.print(x + " ");}}
}

输出结果：
在这里插入图片描述

boolean containsKey(Object key)
判断是否包含key

演示：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);boolean flg1 = map.containsKey("abc");boolean flg2 = map.containsKey("cba");System.out.println(flg1);System.out.println(flg2);}
}

输出结果：
在这里插入图片描述

boolean containsValue(Object value)
判断是否包含value

演示：

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8);boolean flg1 = map.containsValue(1);boolean flg2 = map.containsValue(3);System.out.println(flg1);System.out.println(flg2);}
}

输出结果：
在这里插入图片描述

Set<Map.Entry<K, V>> entrySet()
返回所有的 key-value 映射关系，entrySet()将Map中的键值对放在Set中返回了

注意：

Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入
在TreeMap中插入键值对时，key不能为空，否则就会抛NullPointerException异常，因为插入键值对时，会在二叉搜索树里进行比较（因此插入的key元素类型要可比，或者在key类中实现了比较方式），将新节点插入到合适位置，而value可以为空。但是HashMap的key和value都可以为空，因为插入时不涉及比较。因此，输出时，如果是TreeMap实现的，则是有序的；若是HashMap实现的，则是无序的

5.2 Map.Entry<K,V>

Map.Entry<K, V> 是Map内部实现的用来存放<key, value>键值对映射关系的内部类，该内部类中主要提供了<key, value>的获取，value的设置以及Key的比较方式

K getKey()
返回entry中的key
V getValue()
返回entry中的value
V setValue(V value)
将键值对中的value值替换成指定value

通过该方法转化，既可以获取key，也可以获取value；而Map中的get方法只能获取key所对应的value值

public class Test {public static void main(String[] args) {Map<String,Integer> map = new TreeMap<>();map.put("fbc",2);map.put("cde",3);map.put("abc",5);map.put("grh",8); 打印所有的键值对Set<Map.Entry<String,Integer>> entrySet = map.entrySet();System.out.println(entrySet);System.out.println("========");for (Map.Entry<String,Integer> entry:entrySet) {System.out.println("key:" + entry.getKey()+" val:" + entry.getValue());}}
}

输出结果：
在这里插入图片描述

6. Set

Set与Map主要的不同有两点：Set是继承自Collection的接口类，Set中只存储了Key，且Key唯一。Set类似于一个集合，具有互异性，最大的作用就是去重。Set的实现依靠TreeSet、HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。

6.1 Set的常用方法

boolean add(E e)
用来给集合添加元素，但不会添加重复元素

演示1：

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(4);set.add(7);set.add(1);set.add(3);System.out.println(set);}

输出结果：
在这里插入图片描述

演示2：

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(1);set.add(7);set.add(1);set.add(3);System.out.println(set);}

输出结果

在这里插入图片描述
和Map类似，Set也可以add集合中已有的元素，但不会将其加入集合中，从而达到去重的效果

void clear()
清空集合中的元素

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(4);set.add(7);set.add(1);set.add(3);System.out.println(set);set.clear();System.out.println(set);}

输出结果：
在这里插入图片描述

boolean contains(Object o)
判断o是否在集合中

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(4);set.add(7);set.add(1);set.add(3);System.out.println(set);System.out.println(set.contains(4));System.out.println(set.contains(5));}

输出结果：
在这里插入图片描述

Iterator iterator()
返回迭代器

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(4);set.add(7);set.add(1);set.add(3);Iterator<Integer> it = set.iterator();while(it.hasNext()) {System.out.print(it.next()+" ");}}

输出结果：
在这里插入图片描述

boolean remove(Object o)
删除集合中的o

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(4);set.add(7);set.add(1);set.add(3);System.out.println(set);set.remove(4);System.out.println(set);}

输出结果：
在这里插入图片描述

int size()
返回set中的元素个数

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(4);set.add(7);set.add(1);set.add(3);System.out.println(set.size());}

在这里插入图片描述

boolean isEmpty()
判断集合set是否为空，为空则返回true，反之返回false

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();System.out.println(set.isEmpty());set.add(4);set.add(7);set.add(1);set.add(3);System.out.println(set.isEmpty());}

输出结果：
在这里插入图片描述

Object[] toArray()
将set中的元素转换为数组返回

    public static void main(String[] args) {Set<Integer> set = new TreeSet<>();set.add(4);set.add(7);set.add(1);set.add(3);System.out.println(Arrays.toString(set.toArray()));System.out.println("========");Object[] arr = set.toArray();for (Object o : arr) {System.out.print(o + " ");}}

输出结果：
在这里插入图片描述

boolean containsAll(Collection<?> c)
检查集合c中的元素是否在set中全部存在，是则返回true，否则返回false

    public static void main(String[] args) {Collection<Integer> c = new ArrayList<>();c.add(1);c.add(2);c.add(3);Set<Integer> set = new TreeSet<>();set.add(1);set.add(2);System.out.println(set.containsAll(c));set.add(3);System.out.println(set.containsAll(c));}

输出结果：
在这里插入图片描述

boolean addAll(Collection<?extends E> c)
将集合c中的元素添加到set中，可以达到去重的效果

    public static void main(String[] args) {Collection<Integer> c = new ArrayList<>();c.add(1);c.add(2);c.add(1);c.add(3);c.add(2);c.add(4);System.out.println(c);Set<Integer> set = new TreeSet<>();set.addAll(c);System.out.println(set);}

输出结果：
在这里插入图片描述

注意：

Set中的Key不能修改，如果要修改，先将原来的删除掉，然后再重新插入
TreeSet中不能插入null的key，若插入null，则会抛出空指针异常；而HashSet可以

LeetCode_614">LeetCode刷题

1. 二叉搜索树与双向链表

题目链接：将二叉搜索树转化为排序的双向链表

解题思路：

对该二叉搜索树采取中序遍历，先找到二叉搜索树最左边的节点
定义两个引用prev和head，prev用来引用当前pRootOfTree的前一个节点，head始终引用原二叉搜索树最左边的节点，用于返回转化成的双向链表

代码如下：

public class Solution {public TreeNode prev;public TreeNode head;public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree == null) {return null;}Convert(pRootOfTree.left);if (prev == null) {prev = pRootOfTree;head = pRootOfTree;} else{prev.right = pRootOfTree;pRootOfTree.left = prev;prev = pRootOfTree;}Convert(pRootOfTree.right);return head;}
}