你好我是林森lsjs我的Github 地址sqyCoder (Qiyang) · GitHub以博文记录成长用心打磨代码与思维目录一、二叉搜索树1.1 概念1.2 查找用处1.3 手搓二叉搜索树1.3.1 find 方法1.3.2 insert 方法1.3.3 remove 方法1.3.4 removeNode 方法二、Set用法2.1 基础使用方法2.1.1 add2.1.2 contaics2.1.3 removes2.1.4 for(String e: set)遍历2.1.5 clean size isEmpty2.2 其他用法2.2.1 迭代器遍历三、Map用法3.1 基础用法3.1.1 put3.1.2 get(基础getOrDefault等)3.1.3 remove3.1.4 clean size isEmpty3.2 其他用法3.2.1 entry遍历map一、二叉搜索树1.1 概念二叉搜索树啊这个你得先知道它是一棵二叉树。二叉树是啥就是每个节点最多就俩孩子一个左孩子一个右孩子不能多。然后二叉搜索树在二叉树的基础上加了个规矩这个规矩就是每个节点的左子树里面所有节点的值都比根节点小右子树里面所有节点的值都比根节点大。而且这个规矩不是只管根节点是每个节点都得满足左边小右边大。你记住这个就抓住了核心。我举个例子比如一个节点是 8那它左边可能挂个 3右边挂个 10。那 3 的右边可能挂个 6但 6 不能跑到 3 的左边去因为 3 的左子树所有节点都得比 3 小因为 6 比 3 大所以它属于 3 的右子树。这样一层一层每个节点都左小右大。1.2 查找用处那这棵树有啥用呢主要是查找快。因为你有这个顺序你找一个数的时候先跟根比比根小就去左边找比根大就去右边找这样每次能砍掉一半最差时间复杂度未ON平均是OlogN啥时候二叉搜索树,查找的快?树比较平衡的时候 (左右子树高度差不多)一种严格的情况:任何一个子树,左右子树高度差 1平衡的二叉搜索树(AVL树)查找O(logN)1.3 手搓二叉搜索树这个二叉搜索树啊你怎么理解呢你先记住它是个二叉树每个节点左边小右边大就这个规矩没了。然后咱们看代码它给你一个节点类一个树类树里有 find、insert、remove 三个方法先看节点类这没啥的就是 data 存数据left 和 right 存左右孩子默认 null构造方法就是 new 的时候把 data 塞进去。// 二叉搜索树上的一个节点 class BinarySearchNode { // 数据域就是节点里面存的值 public int data; // 左孩子默认 null表示没有左孩子 public BinarySearchNode left null; // 右孩子默认 null表示没有右孩子 public BinarySearchNode right null; // 构造方法new 节点的时候直接给它赋值 public BinarySearchNode(int data) { this.data data; } }然后树类里面有 root是根节点初始 null就是空树没别的。1.3.1 find 方法find 就是查找你给它一个整数 data它去树里找这个数找到了就把那个节点返回给你找不到就返回 null。那怎么找呢你不能瞎找你得利用二叉搜索树的性质。从根开始你要找的数比当前节点小就往左走比当前节点大就往右走正好相等那就是找到了直接返回当前节点。如果走到 null 了还没找到那说明这个数不存在返回 null。你看代码里它先定义一个 cur从 root 开始。然后 while 循环条件是 cur ! null就是只要没走到空就一直比。每轮循环里if (data cur.data) 就是你要找的比当前小cur cur.left往左走。else if (data cur.data) 就是比当前大cur cur.right往右走。else 就是相等return cur找到了。循环外面 return null就是没找到。// 查找 // 参数 data 是要找的值 // 返回值是找到的节点找不到返回 null public BinarySearchNode find(int data) { // cur 从根节点出发表示当前正在看的节点 BinarySearchNode cur root; // 只要 cur 不是 null就继续比较 while (cur ! null) { if (data cur.data) { // 要找的数比当前节点小根据二叉搜索树性质往左子树找 cur cur.left; } else if (data cur.data) { // 要找的数比当前节点大往右子树找 cur cur.right; } else { // 相等找到了直接返回这个节点 return cur; } } // 循环结束cur 是 null说明找完整棵树都没找到 return null; }1.3.2 insert 方法insert 就是插入你给它一个 data它给你插到树里正确的位置让树还是满足左小右大。如果这个 data 已经存在了那咱们约定这棵树不能有重复元素所以返回 false插入成功返回 true。先处理特殊情况如果 root 是 null说明树是空的那直接 new 一个节点让 root 指向它返回 true完事。如果不是空树那就得找插入位置。怎么找跟 find 一样从根开始你要插的数比当前小就往左走比当前大就往右走。但是注意你不能走到 null 再插因为你要插到父节点的左孩子或者右孩子上所以你得记录父节点。所以代码里定义 cur 和 parentcur 从 root 开始parent 初始 null。每次移动前先把 parent cur就是记下当前节点是待插入位置的爸爸然后再让 cur 往左或者往右走。如果走到某个节点发现 data 跟 cur.data 相等那说明已经存在了直接 return false不插了。循环结束的时候cur 一定是 null说明走到空位置了这时候 parent 就是待插入位置的父节点。然后 new 一个节点 newNode判断 data 和 parent.data 的大小关系如果 data 小就挂在 parent.left否则挂在 parent.right。最后 return true。// 插入 // 参数 data 是要插入的值 // 插入成功返回 truedata 已存在返回 false public boolean insert(int data) { // 如果树是空的直接让 root 指向新节点 if (root null) { root new BinarySearchNode(data); return true; } // cur 从根开始找插入位置 BinarySearchNode cur root; // parent 用来记录 cur 的父节点因为最后要挂在 parent 的左边或右边 BinarySearchNode parent null; // 循环找位置直到 cur 走到 null while (cur ! null) { if (data cur.data) { // 要插入的数比当前节点小往左走 parent cur; // 先记下父节点 cur cur.left; // cur 再往左 } else if (data cur.data) { // 要插入的数比当前节点大往右走 parent cur; // 先记下父节点 cur cur.right; // cur 再往右 } else { // 相等说明 data 已经在树里了咱们这棵树不允许重复插入失败 return false; } } // 循环结束cur 是 nullparent 就是待插入位置的父节点 // 创建一个新节点 BinarySearchNode newNode new BinarySearchNode(data); if (data parent.data) { // 新节点比父节点小挂在左孩子 parent.left newNode; } else { // 新节点比父节点大挂在右孩子 parent.right newNode; } return true; }1.3.3 remove 方法remove 就是删除你给它一个 data它找到这个节点删掉返回 true找不到返回 false。它先查找跟 find 一样但是要同时记录 parent因为删除的时候要改父节点的 left 或者 right 指针。cur 从 root 开始parent 初始 null。while 循环如果 data cur.dataparent curcur cur.left如果 data cur.dataparent curcur cur.right如果相等说明找到了调用 removeNode(cur, parent) 把这个节点删掉然后返回 true。如果循环结束没找到返回 false。// 删除 // 参数 data 是要删除的值 // 删除成功返回 truedata 不存在返回 false public boolean remove(int data) { // 先查找要删除的节点同时记录它的父节点 BinarySearchNode cur root; BinarySearchNode parent null; while (cur ! null) { if (data cur.data) { // 要删的数比当前小往左走 parent cur; cur cur.left; } else if (data cur.data) { // 要删的数比当前大往右走 parent cur; cur cur.right; } else { // 找到了cur 就是要删除的节点调用 removeNode 删除它 removeNode(cur, parent); return true; } } // 循环结束没找到删除失败 return false; }1.3.4 removeNode 方法这个方法是删除的核心它处理三种情况你听我慢慢说。第一种情况cur.left null就是 cur 没有左子树。这个情况包括了 cur 左右都为空或者只有右子树。因为没有左子树要把 cur 删掉就把它的右孩子接到 parent 上就行了。再细分三种小情况如果 cur 就是根节点那 root 直接指向 cur.right。如果 cur 是 parent 的右孩子那 parent.right cur.right。如果 cur 是 parent 的左孩子那 parent.left cur.right。if (cur.left null) { // 1. cur 没有左子树包含了 left 和 right 都是 null 的情况 if (cur root) { // 1.1 cur 是根节点root 直接指向 cur 的右孩子 root cur.right; } else if (cur parent.right) { // 1.2 cur 不是根并且 cur 是 parent 的右孩子把 parent 的右孩子指向 cur 的右孩子 parent.right cur.right; } else if (cur parent.left) { // 1.3 cur 不是根并且 cur 是 parent 的左孩子把 parent 的左孩子指向 cur 的右孩子 parent.left cur.right; } }第二种情况cur.right null就是 cur 没有右子树。这个跟第一种对称把左孩子接上去就行。else if (cur.right null) { // 2. cur 没有右子树 if (cur root) { // 2.1 cur 是根节点root 直接指向 cur 的左孩子 root cur.left; } else if (cur parent.right) { // 2.2 cur 不是根并且 cur 是 parent 的右孩子把 parent 的右孩子指向 cur 的左孩子 parent.right cur.left; } else if (cur parent.left) { // 2.3 cur 不是根并且 cur 是 parent 的左孩子把 parent 的左孩子指向 cur 的左孩子 parent.left cur.left; } }第三种情况cur 左右子树都有这个最复杂用“移花接木”。思路是在 cur 的右子树中找到最小的那个节点也就是右子树最左侧的节点。这个节点一定没有左子树它的值正好比 cur 左子树所有值都大比 cur 右子树其他值都小所以它能替代 cur。把它的值赋给 cur再把那个最小节点删掉就回到第一种情况了。代码实现定义 goat cur.rightgoatParent cur。goat 就是替罪羊先指向 cur 的右孩子。然后 while(goat.left ! null) 循环goatParent goatgoat goat.left。一直往左走直到 goat.left 为 null此时 goat 就是右子树最左侧节点。然后把 goat.data 赋值给 cur.data。接着删除 goat如果 goat 是 goatParent 的左孩子goatParent.left goat.right否则 goat 是 goatParent 的右孩子这种情况发生在 goat 就是 cur.right 本身goatParent.right goat.right。else { // 3. cur 有两个子树用移花接木 // a) 在 cur 的右子树中找最小值也就是右子树的最左侧节点 BinarySearchNode goat cur.right; // goat 先指向右子树的根 BinarySearchNode goatParent cur; // goatParent 记录 goat 的父节点 // 一直往左走直到 goat.left 为 null while (goat.left ! null) { goatParent goat; goat goat.left; } // 循环结束goat 就是 cur 右子树中最左侧的节点也就是最小值 // b) 把 goat 的值赋值给 cur相当于把 cur 的值替换成 goat 的值 cur.data goat.data; // c) 删除 goat 节点goat 一定没有左子树 if (goat goatParent.left) { // goat 是它父节点的左孩子把父节点的左孩子指向 goat 的右孩子 goatParent.left goat.right; } else { // goat 是它父节点的右孩子goat 就是 cur.right 本身的情况 goatParent.right goat.right; } }这样整个 removeNode 就讲完了。最后 main 方法就是测试插入 1、2、3、4查找 4删除 4你可以用调试器看树结构。二、Set用法有HashSet和TreeSet先TreeSet为例用法都一样2.1 基础使用方法2.1.1 add第一个是 add就是往集合里加东西。你写set.add(abc)它就把 abc 加进集合。如果集合里本来就有 abc那你再加一遍它不会报错也不会加进去就相当于没加集合里还是只有一个 abc。add 这个方法会返回一个 boolean加成功了返回 true如果已经存在没加进去返回 false你可以接也可以不接。SetString set new TreeSet(); set.add(abc); // 加成功返回 true set.add(abc); // 已存在返回 false集合里还是只有一个 abc2.1.2 contaics第二个是 contains就是判断某个元素在不在集合里。你写set.contains(abc)如果在就返回 true不在就返回 false。这个很快因为集合底层是用哈希表实现的查找接近 O(1)不像列表要一个个遍历。if (set.contains(abc)) { System.out.println(在); } else { System.out.println(不在); }2.1.3 removes第三个是 remove就是删掉集合里的某个元素。你写set.remove(abc)它就把 abc 从集合里拿掉。如果本来就没有 abc那它啥也不干也不会报错。remove 也返回 boolean删掉了返回 true没找到返回 false。set.remove(abc); // 删掉 abc返回 true set.remove(xyz); // 没有 xyz返回 false集合不变2.1.4 for(String e: set)遍历for (String e : set) { System.out.println(e); }2.1.5 clean size isEmptyclear 是干啥的呢就是把集合里所有元素全部删掉一个不留集合就变成空的了。你写set.clear();调用完之后这个 set 里面就啥也没有了size 变成 0isEmpty 变成 true。它不返回东西是 void 的你直接调就行不用接返回值。SetString set2 new TreeSet(); set2.add(apple); set2.add(banana); set2.add(cherry); System.out.println(set2.size()); // 3 set2.clear(); // 清空 System.out.println(set2.size()); // 0 System.out.println(set2.isEmpty()); // true2.2 其他用法2.2.1 迭代器遍历Set 的迭代器遍历啊你怎么理解呢之前咱们说用 for-each 就能遍历那个确实方便但有时候你需要在遍历的时候删元素或者你用的不是 for-each或者你想更灵活一点那你就得用迭代器。迭代器是啥你就把它理解成一个指针一开始指向集合里第一个元素的前面然后你不停地问它“还有下一个吗”有的话就让它把下一个拿出来就这么个东西。在 Java 里迭代器是 Iterator 接口你写IteratorString it set.iterator();这就拿到一个迭代器。然后你用 while 循环条件是it.hasNext()就是问还有没有下一个。如果有就String e it.next();把下一个元素拿出来然后你就可以对它干啥干啥。注意next() 每调一次指针就往后走一个所以你不能重复调调多了会跳元素或者报错。还有一点迭代器遍历的时候如果你想删元素你不能直接用 set.remove()那样会报 ConcurrentModificationException就是并发修改异常。你得用it.remove()它是删掉刚刚 next() 拿出来的那个元素这样才安全。这个考试有时候会考。SetString set new TreeSet(); set.add(a); set.add(b); set.add(c); // 拿到迭代器 IteratorString it set.iterator(); // while 循环只要还有下一个 while (it.hasNext()) { // next() 取出下一个元素 String e it.next(); System.out.println(e); // 如果要在遍历中删除用 it.remove() // if (e.equals(b)) { // it.remove(); // } }三、Map用法Map 啊你怎么理解呢首先你要知道Map 跟 Set 不一样Set 里面装的是单个元素Map 里面装的是键值对就是一个键对应一个值像字典一样你拿键去查就能拿到对应的值。键不能重复你放两个一样的键后面那个会把前面那个覆盖掉值可以重复这个没关系。3.1 基础用法3.1.1 putMapString, Integer map new TreeMap(); map.put(apple, 1); // 键不存在返回 nullmap 里是 apple1 map.put(banana, 2); // 键不存在返回 nullmap 里是 apple1, banana2 map.put(apple, 3); // 键已存在返回旧值 1map 里 apple 变成 33.1.2 get(基础getOrDefault等)System.out.println(map.get(apple)); // 3因为 apple 存在 System.out.println(map.get(cherry)); // null因为 cherry 不存在 System.out.println(map.getOrDefault(cherry, 0)); // 0不存在返回默认值 03.1.3 removeSystem.out.println(map.remove(banana)); // 2删掉 banana2返回 2 System.out.println(map.remove(cherry)); // nullcherry 不存在返回 null3.1.4 clean size isEmptyMapString, Integer map new TreeMap(); map.put(apple, 1); map.put(banana, 2); map.put(cherry, 3); System.out.println(map.size()); // 3 map.clear(); // 清空 System.out.println(map.size()); // 0 System.out.println(map.isEmpty()); // true3.2 其他用法3.2.1 entry遍历mapMap 的 entry 遍历啊你怎么理解呢你之前不是学了 Map 的 put、get、remove 这些基础操作嘛那你要想把 Map 里所有的键值对都拿出来看一遍你不能只拿键也不能只拿值你得键和值一起拿那你就得用 entrySet 来遍历。entry 是啥你就把它理解成一个小包裹里面装着两样东西一个是 key一个是 value你拿到这个包裹之后用 getKey() 拿键用 getValue() 拿值就这么简单。那代码怎么写呢你先有个 Map比如 TreeMap 或者 HashMap然后你写map.entrySet()这个方法返回的是一个 Set里面装的就是一个个 entry 小包裹。然后你就可以用 for-each 去遍历这个 Set。你写MapString, Integer map new TreeMap(); map.put(apple, 1); map.put(banana, 2); map.put(cherry, 3); // 用 entrySet 遍历 for (Map.EntryString, Integer entry : map.entrySet()) { // entry 就是一个小包裹 String key entry.getKey(); // 拿到键 Integer value entry.getValue(); // 拿到值 System.out.println(key value); }今天的数据结构讲解就到这了我们下期再见诸位共勉