二分搜索树的学习

二分搜索树基础模块学习

通过对慕课网bobo老师讲解的二分搜索树的总结 玩转数据结构

二分搜索树的前序遍历

/** * 二分搜索树的前序遍历 * @param node */ private void preOrder(Node node) { if (node == null) { return; } System.out.println(node.e); preOrder(node.left); preOrder(node.right); }

二分搜索树的中序遍历

/** * 二分搜索树的前序遍历 * @param node */ private void preOrder(Node node) { if (node == null) { return; } preOrder(node.left); System.out.println(node.e); preOrder(node.right); }

可以看出就是访问元素的位置不同.。同理后序遍历

二分搜索树的后序遍历

/** * 二分搜索树的后序遍历 * @param node */ private void postOrder(Node node) { if (node == null) { return; } postOrder(node.left); postOrder(node.right); System.out.println(node.e); }

二分搜索树的层序遍历

通过使用队列的方式，先进先出实现层序遍历

/** * 二分搜索树的层序遍历 */ public void levelOrder() { LinkedList<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 T searchMin() { //对外调用方法 if (size == 0) { throw new IllegalArgumentException("BST is null!"); } return searchMin(root).e; //Node对象中 e为泛型, root为根节点 } /** * 查询二分搜索树最小元素 * @param node node不为空 * @return */ private Node searchMin(Node node) { if (node.left == null) { return node; } return searchMin(node.left); } public T removeMin() { //对外调用方法 T min = searchMin(); root = removeMin(root); return min; } /** * 删除最小二分搜索树元素 * @param node * @return */ private Node removeMin(Node node) { if (node.left == null) { Node RNode = node.right; node.right = null; size--; //元素总数 return RNode; } node.left = removeMin(node.left); return node; }

二分搜索树查询与删除最大元素

同上，对称就行

二分搜索树删除元素

删除只有左或者右子节点的元素时，用上面的逻辑，然而删除有左右子节点的元素时，可以利用当前节点的右子节点里面的最小元素进行替换当前节点 或者 最小元素重新连接当前节点左右子节点。 同理，也可以使用当前节点的左子节点里面的最大元素！

public void deleteElement(T e) { deleteElement(root, e); //root 根节点，e待删除节点元素 } /** * 删除二分搜索树的元素 * @param node * @param e * @return */ private Node deleteElement(Node node, T e) { if (node == null) { return null; } if (node.e.compareTo(e) > 0) { node.left = deleteElement(node.left, e); return node; } else if (node.e.compareTo(e) < 0) { node.right = deleteElement(node.right, e); return node; } if (node.left == null) { //待删除左节点为空 Node RNode = node.right; node.right = null; size--; //元素总数 return RNode; } if (node.right == null) {//待删除右节点为空 Node LNode = node.left; node.left = null; size--; //元素总数 return LNode; } //(1)左右不为空时,找到右节点最小节点，然后连接node节点左右子节点 Node min = searchMin(node.right);//查找最小元素方法 min.right = removeMin(node.right);//调用删除最小元素方法 min.left = node.left; node.left = node.right = null; return min; //(2)左右不为空时,找到右节点最小节点，替换当前节点元素 // Node min = searchMin(node.right);//查找最小元素方法 // node.right = removeMin(node.right);//调用删除最小元素方法 // node.e = min.e; // return node; }