一、二分搜索树 —— Binary Search Tree
二、二分搜索树添加新元素
- 我们的二分搜索树不包含重复元素
- 如果想包含重复元素,只需要定义:
- 左子树小于等于节点;或者右子树大于等于节点
- 注意:我们之前讲的数组和链表,可以有重复元素
- 如果想包含重复元素,只需要定义:
- 二分搜索树添加元素的非递归写法,和链表非常的像。
- 我们这次二分搜索树方面的实现,更多关注递归的实现
- 在二分搜索树方面,递归的方式比非递归的方式实现起来要简单
详细代码
package bst; public class BST<E extends Comparable<E>> { private class Node { public E e; public Node left, right; public Node(E e) { this.e = e; left = null; right = null; } } private Node root; private int size; public BST() { root = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return size == 0; } // 向二分搜索树中添加新的元素e public void add(E e) { if (root == null) { root = new Node(e); size++; } else { add(root, e); } } // 向以node为根的二分搜索树中插入元素E,递归算法 private void add(Node node, E e) { if (e.equals(node.e)) { return; } else if (e.compareTo(node.e) < 0 && node.left == null) { node.left = new Node(e); size++; return; } else if (e.compareTo(node.e) > 0 && node.right == null) { node.right = new Node(e); size++; return; } if (e.compareTo(node.e) < 0) { add(node.left, e); } else { // e.compareTo(Node.e) > 0 add(node.right, e); } } }
三、改进add操作,深入了解递归终止函数
关键代码
// 向二分搜索树中添加新的元素e public void add(E e) { root = add(root, e); } // 向以node为根的二分搜索树中插入元素E,递归算法 // 返回插入新节点后二分搜索树的根 private Node add(Node node, E e) { if (node == null){ size++; return new Node(e); } if (e.compareTo(node.e) < 0) { node.left = add(node.left,e); } else if (e.compareTo(node.e)>0){ // e.compareTo(Node.e) > 0 node.right = add(node.right,e); } return node; }
四、查找元素
// 看二分搜索树中是否包含元素e public boolean contains(E e) { return contains(root, e); } // 看以node为根的二分搜索树中是否包含元素e,递归算法 private boolean contains(Node node, E e) { if (node == null) { return false; } if (e.compareTo(node.e) == 0) { return true; } else if (e.compareTo(node.e) > 0) { return contains(node.left, e); } else { return contains(node.right, e); } }
- 什么是遍历操作
- 遍历操作就是把所有节点都访问一遍
- 访问的原因和业务相关
- 在线性结构下,遍历是极其容易的
- 对于遍历操作,两颗子树都要顾及
// 二分搜索树的前序遍历 public void preOrder(){ preOrder(root); } // 前序遍历以node为根的二分搜索树,递归算法 private void preOrder(Node node){ if (node == null){ return; } System.out.println(node.e); preOrder(node.left); preOrder(node.right); }
也可以这样
// 前序遍历以node为根的二分搜索树,递归算法 private void preOrder(Node node) { // if (node == null){ // return; // } if (node != null) { System.out.println(node.e); preOrder(node.left); preOrder(node.right); } }
Main方法测试一下
public class Main { public static void main(String[] args) { BST<Integer> bst = new BST<>(); int[] nums = {5, 3, 6, 8, 4, 2}; for (int num : nums) { bst.add(num); } bst.preOrder(); } }
重写一下toString方法,方便观察树
@Override public String toString() { StringBuilder res = new StringBuilder(); generateBSTString(root, 0, res); return res.toString(); } // 生成以node为根节点,深度为depth的描述二叉树的字符串 private void generateBSTString(Node node, int depth, StringBuilder res) { if (node == null) { res.append(generateDepthString(depth) + "null\n"); return; } res.append(generateDepthString(depth) + node.e + "\n"); generateBSTString(node.left, depth + 1, res); generateBSTString(node.right, depth + 1, res); } private String generateDepthString(int depth) { StringBuilder res = new StringBuilder(); for (int i = 0; i < depth; i++) { res.append("---"); } return res.toString(); }
五、二分搜索树的中序遍历和后序遍历
中序遍历
// 二分搜索树的中序遍历 public void inOrder(){ inOrder(root); } // 中序遍历以node为根的二分搜索树,递归算法 private void inOrder(Node node){ if (node == null){ return; } inOrder(node.left); System.out.println(node.e); inOrder(node.right); }
看结果
后序遍历
// 二分搜索树的后续排序 public void postOrder(){ postOrder(root); } // 后序遍历以node为根的二分搜索树,递归算法 private void postOrder(Node node){ if (node == null){ return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); }
看结果
六、二分搜索树前序遍历的非递归实现
// 二分搜索树的非递归前序遍历 public void preOrderNR() { Stack<Node> stack = new Stack<Node>(); stack.push(root); while (!stack.isEmpty()) { Node cur = stack.pop(); System.out.println(cur.e); if (cur.right != null) { stack.push(cur.right); } if (cur.left != null) { stack.push(cur.left); } } }
结果如下
- 二分搜索树遍历的非递归实现,比递归实现复杂得多
- 中序遍历和后序遍历的非递归实现更复杂
- 中序遍历和后序遍历的非递归实现,实际应用不广
七、二分搜索树的层序遍历——广度优先遍历
// 二分搜索树的层序遍历 public void levelOrder() { Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { Node cur = q.remove(); System.out.println(cur.e); if (cur.left != null) { q.add(cur.left); } if (cur.right != null) { q.add(cur.right); } } }
结果输出
八、二分搜索树————删除元素
从最简单的开始,删除二分搜索树的最小值和最大值
// 寻找二分搜索树的最小元素 public E minimum() { if (size == 0) { throw new IllegalArgumentException("BST is empty!"); } return minimum(root).e; } // 返回以node为根的二分搜索树的最小值所在的节点 private Node minimum(Node node) { if (node.left == null) { return node; } return minimum(node.left); } // 寻找二分搜索树的最大元素 public E maximum() { if (size == 0) { throw new IllegalArgumentException("BST is empty!"); } return maximum(root).e; } // 返回以node为根的二分搜索树的最大值所在的节点 private Node maximum(Node node) { if (node.right == null) { return node; } return maximum(node.right); } // 从二分搜索树中删除最小值所在节点,返回最小值 public E removeMin() { E ret = minimum(); root = removeMin(root); return ret; } // 删除掉以node为根的二分搜索树中的最小节点 // 返回删除节点后新的二分搜索树的根 private Node removeMin(Node node) { if (node.left == null) { Node rightNode = node.right; node.right = null; size -- ; return rightNode; } node.left = removeMin(node.left); return node; } // 从二分搜索树中删除最小值所在节点,返回最大值 public E removeMax() { E ret = maximum(); root = removeMax(root); return ret; } // 删除掉以node为根的二分搜索树中的最大节点 // 返回删除节点后新的二分搜索树的根 private Node removeMax(Node node) { if (node.right == null) { Node leftNode = node.left; node.left = null; size -- ; return leftNode; } node.right = removeMax(node.right); return node; }
测试代码
点击查看完整内容
package bst; import java.util.ArrayList; import java.util.Random; public class Main { public static void main(String[] args) { BST<Integer> bst = new BST<>(); BST<Integer> bst2 = new BST<>(); Random random = new Random(); int n = 1000; for (int i = 0; i < n; i++) { bst.add(random.nextInt(10000)); bst2.add(random.nextInt(10000)); } ArrayList<Integer> nums1 = new ArrayList<>(); ArrayList<Integer> nums2 = new ArrayList<>(); while (!bst.isEmpty()) { nums1.add(bst.removeMin()); } while (!bst2.isEmpty()) { nums2.add(bst2.removeMax()); } System.out.println(nums1); for (int i = 1; i < nums1.size(); i++) { if (nums1.get(i - 1) > nums1.get(i)) { throw new IllegalArgumentException("Error"); } } System.out.println("成功!"); System.out.println(nums2); for (int i = 1; i < nums1.size(); i++) { if (nums2.get(i - 1) < nums2.get(i)) { throw new IllegalArgumentException("Error"); } } System.out.println("成功!"); } }
结果输出
九、删除二分搜索树的任意节点
// 从二分搜索树中删除元素为e的节点 public void remove(E e) { root = remove(root, e); } //删除以node为根的二分搜索树中值为e的节点,递归算法 // 返回删除节点后新的二分搜索树的根 private Node remove(Node node, E e) { if (node == null) { return null; } if (e.compareTo(node.e) < 0) { node.left = remove(node.left, e); return node; } else if (e.compareTo(node.e) > 0) { node.right = remove(node.right, removeMin()); return node; } else { // e == node.e // 待删除节点左子树为空的情况 if (node.left == null) { Node rightNode = node.right; node.right = null; size++; return rightNode; } // 待删除节点右子树为空的情况 if (node.right == null) { Node leftNode = node.left; node.left = null; size--; return leftNode; } // 待删除节点左右子树均不为空的情况 // 找到比待删除节点大的最小节点,即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); successor.right = removeMin(node.right); successor.left = node.left; node.left = node.right = null; return successor; } }
十、力扣题目 804
package Solution7; import java.util.TreeSet; /** * @author DBC * @version 1.0 * @date 2022-01-13 20:11 */ class Solution { public int uniqueMorseRepresentations(String[] words) { String[] codes = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."}; TreeSet<String> set = new TreeSet<>(); for (String word:words){ StringBuilder res = new StringBuilder(); for (int i = 0;i<word.length();i++){ res.append(codes[word.charAt(i) - 'a']); } set.add(res.toString()); } return set.size(); } }
十一、映射
public interface Map<K, V> { void add(K key, V value); V remove(K key); boolean contains(K key); V get(K key); void set(K key, V newValue); int getSize(); boolean isEmpty(); }
本文作者为DBC,转载请注明。