本文共 10795 字，大约阅读时间需要 35 分钟。
二叉搜索树，添加、删除、搜索、的最坏时间复杂度为 O ( l o g n ) O(log^n) O(logn)
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树
我看重要的说
步骤
找到父节点parent
创建新节点node
parent.left = node 或parent.right = node
代码
public void add(E element) { elementNotNullCheck(element); // 添加第一个节点 if (root == null) { root = new Node<>(element, null); size++; return; } // 添加的不是第一个节点 // 找到父节点 Node parent = root; Node node = root; int cmp = 0; do { cmp = compare(element, node.element); parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { // 相等 node.element = element; return; } } while (node != null); // 看看插入到父节点的哪个位置 Node newNode = new Node<>(element, parent); if (cmp > 0) { parent.right = newNode; } else { parent.left = newNode; } size++; }/***当比较自定义类时，传入一个Comparator，自定义比较方案*如果没有传入Comparator，强制转换元素*/private int compare(E e1, E e2) { if (comparator != null) { return comparator.compare(e1, e2); } return ((Comparable )e1).compareTo(e2); }private void elementNotNullCheck(E element) { if (element == null) { throw new IllegalArgumentException("element must not be null"); } } 删除叶子结点
直接删除
删除度为1的结点
用子节点代替原节点位置
删除度为2的结点
先用前驱或后驱节点覆盖原结点的值，再删除其对应的前驱或后驱结点
public void remove(E element) { remove(node(element)); }private void remove(Node node) { if (node == null) return; size--; if (node.hasTwoChildren()) { // 度为2的节点 // 找到后继节点 Node s = successor(node); // 用后继节点的值覆盖度为2的节点的值 node.element = s.element; // 删除后继节点 node = s; } // 删除node节点（node的度必然是1或者0） Node replacement = node.left != null ? node.left : node.right; if (replacement != null) { // node是度为1的节点 // 更改parent replacement.parent = node.parent; // 更改parent的left、right的指向 if (node.parent == null) { // node是度为1的节点并且是根节点 root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { // node == node.parent.right node.parent.right = replacement; } } else if (node.parent == null) { // node是叶子节点并且是根节点 root = null; } else { // node是叶子节点，但不是根节点 if (node == node.parent.left) { node.parent.left = null; } else { // node == node.parent.right node.parent.right = null; } } }private Node node(E element) { Node node = root; while (node != null) { int cmp = compare(element, node.element); if (cmp == 0) return node; if (cmp > 0) { node = node.right; } else { // cmp < 0 node = node.left; } } return null; }@SuppressWarnings("unused") private Node predecessor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（left.right.right.right....） Node p = node.left; if (p != null) { while (p.right != null) { p = p.right; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.left) { node = node.parent; } // node.parent == null // node == node.parent.right return node.parent; } private Node successor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（right.left.left.left....） Node p = node.right; if (p != null) { while (p.left != null) { p = p.left; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.right) { node = node.parent; } return node.parent; } //此为二叉搜索树的代码，import java.util.Comparator;import java.util.LinkedList;import java.util.Queue;@SuppressWarnings("unchecked")public class BinarySearchTree implements BinaryTreeInfo { private int size; private Node root; private Comparator comparator; public BinarySearchTree() { this(null); } public BinarySearchTree(Comparator comparator) { this.comparator = comparator; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { root = null; size = 0; } public void add(E element) { elementNotNullCheck(element); // 添加第一个节点 if (root == null) { root = new Node<>(element, null); size++; return; } // 添加的不是第一个节点 // 找到父节点 Node parent = root; Node node = root; int cmp = 0; do { cmp = compare(element, node.element); parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { // 相等 node.element = element; return; } } while (node != null); // 看看插入到父节点的哪个位置 Node newNode = new Node<>(element, parent); if (cmp > 0) { parent.right = newNode; } else { parent.left = newNode; } size++; } public void remove(E element) { remove(node(element)); } public boolean contains(E element) { return node(element) != null; } private void remove(Node node) { if (node == null) return; size--; if (node.hasTwoChildren()) { // 度为2的节点 // 找到后继节点 Node s = successor(node); // 用后继节点的值覆盖度为2的节点的值 node.element = s.element; // 删除后继节点 node = s; } // 删除node节点（node的度必然是1或者0） Node replacement = node.left != null ? node.left : node.right; if (replacement != null) { // node是度为1的节点 // 更改parent replacement.parent = node.parent; // 更改parent的left、right的指向 if (node.parent == null) { // node是度为1的节点并且是根节点 root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { // node == node.parent.right node.parent.right = replacement; } } else if (node.parent == null) { // node是叶子节点并且是根节点 root = null; } else { // node是叶子节点，但不是根节点 if (node == node.parent.left) { node.parent.left = null; } else { // node == node.parent.right node.parent.right = null; } } } private Node node(E element) { Node node = root; while (node != null) { int cmp = compare(element, node.element); if (cmp == 0) return node; if (cmp > 0) { node = node.right; } else { // cmp < 0 node = node.left; } } return null; } public void preorder(Visitor visitor) { if (visitor == null) return; preorder(root, visitor); } private void preorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; visitor.stop = visitor.visit(node.element); preorder(node.left, visitor); preorder(node.right, visitor); } public void inorder(Visitor visitor) { if (visitor == null) return; inorder(root, visitor); } private void inorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; inorder(node.left, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); inorder(node.right, visitor); } public void postorder(Visitor visitor) { if (visitor == null) return; postorder(root, visitor); } private void postorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; postorder(node.left, visitor); postorder(node.right, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); } public void levelOrder(Visitor visitor) { if (root == null || visitor == null) return; Queue > queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); if (visitor.visit(node.element)) return; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } public boolean isComplete() { if (root == null) return false; Queue > queue = new LinkedList<>(); queue.offer(root); boolean leaf = false; while (!queue.isEmpty()) { Node node = queue.poll(); if (leaf && !node.isLeaf()) return false; if (node.left != null) { queue.offer(node.left); } else if (node.right != null) { // node.left == null && node.right != null return false; } if (node.right != null) { queue.offer(node.right); } else { // node.right == null leaf = true; } } return true; } // public boolean isComplete() { // if (root == null) return false;// // Queue > queue = new LinkedList<>();// queue.offer(root);// // boolean leaf = false;// while (!queue.isEmpty()) { // Node node = queue.poll();// if (leaf && !node.isLeaf()) return false;//// if (node.left != null && node.right != null) { // queue.offer(node.left);// queue.offer(node.right);// } else if (node.left == null && node.right != null) { // return false;// } else { // 后面遍历的节点都必须是叶子节点// leaf = true;// if (node.left != null) { // queue.offer(node.left);// }// }// }// // return true;// } public int height() { if (root == null) return 0; // 树的高度 int height = 0; // 存储着每一层的元素数量 int levelSize = 1; Queue > queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); levelSize--; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (levelSize == 0) { // 意味着即将要访问下一层 levelSize = queue.size(); height++; } } return height; } public int height2() { return height(root); } private int height(Node node) { if (node == null) return 0; return 1 + Math.max(height(node.left), height(node.right)); } @Override public String toString() { StringBuilder sb = new StringBuilder(); toString(root, sb, ""); return sb.toString(); } private void toString(Node node, StringBuilder sb, String prefix) { if (node == null) return; toString(node.left, sb, prefix + "L---"); sb.append(prefix).append(node.element).append("\n"); toString(node.right, sb, prefix + "R---"); } /** * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2 */ private int compare(E e1, E e2) { if (comparator != null) { return comparator.compare(e1, e2); } return ((Comparable )e1).compareTo(e2); } private void elementNotNullCheck(E element) { if (element == null) { throw new IllegalArgumentException("element must not be null"); } } @SuppressWarnings("unused") private Node predecessor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（left.right.right.right....） Node p = node.left; if (p != null) { while (p.right != null) { p = p.right; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.left) { node = node.parent; } // node.parent == null // node == node.parent.right return node.parent; } private Node successor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（right.left.left.left....） Node p = node.right; if (p != null) { while (p.left != null) { p = p.left; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.right) { node = node.parent; } return node.parent; } public static abstract class Visitor { boolean stop; /** * @return 如果返回true，就代表停止遍历 */ public abstract boolean visit(E element); } private static class Node { E element; Node left; Node right; Node parent; public Node(E element, Node parent) { this.element = element; this.parent = parent; } public boolean isLeaf() { return left == null && right == null; } public boolean hasTwoChildren() { return left != null && right != null; } }} 转载地址：http://gnnwi.baihongyu.com/