本文将主要以动图方式展示二叉搜索树的结构，以及动态操作；但是对于基本的概念和性质则不会有过多的提及，如果想系统了解建议查看邓俊辉老师的《数据结构》课程；
一、结构概述二叉树：融合了向量的静态操作（二分查找）和列表的动态操作（插入和删除）的优点；使得树成了应用广泛的数据结构；
二叉搜索树：即顺序排列，可以搜索的树就是二叉搜索树；如下图所示；
忽略二叉树的大小，高度等信息的简版结构如下：
public class BST<T extends Comparable<? super T>> { private BSTNode<T> root; public BST() {root = null;} ... class BSTNode<T extends Comparable<? super T>> { T key; BSTNode<T> parent; BSTNode<T> left; BSTNode<T> right; BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) { this.key = key; this.parent = parent; this.left = left; this.right = right; } } } 二、查找根据二叉搜索树左孩子节点小于父节点，右孩子节点大于等于父节点，逐步深入查找；
实现如下：
private BSTNode<T> search(BSTNode<T> x, T key) { if (x == null) return x; int cmp = key.compareTo(x.key); if (cmp < 0) return search(x.left, key); else if (cmp > 0) return search(x.right, key); else return x; } public BSTNode<T> search(T key) { return search(root, key); }更好的实现还应该记录查找失败的上一个节点，除此之外还可以实现查找最大值，最小值；
三、插入插入，同样根据 BST 的排序规则，先查找插入位置，然后确定插入节点的引用关系；
1. 插入不重复节点如果有 size 等信息，则需要从节点向上依次更新祖先节点
private void insert(T key) { BSTNode<T> node = new BSTNode<T>(key, null, null, null); BSTNode<T> r = this.root; BSTNode<T> p = null; int cmp; // 查找插入位置 while (r != null) { p = r; cmp = node.key.compareTo(r.key); if (cmp < 0) r = r.left; else r = r.right; } if (p == null) this.root = node; else { node.parent = p; cmp = node.key.compareTo(p.key); if (cmp < 0) p.left = node; else p.right = node; } } 四、删除删除，同样首先需要查找该节点，然后删除；
1. 删除不完全节点目标节点没有左孩子或者右孩子时，直接删除节点，然后令其后代代替；
当目标节点同时拥有左孩子和右孩子时：
需要首先找到目标节点的直接后继（自然顺序或者中序遍历顺序的下一个节点），目标节点右孩子一直往左；当然这里同样可以找目标节点的前驱节点替换；
然后交换目标节点和后继节点的位置；
最后同上面的删除一样，直接删除节点；
注意这里只是实现的一种，还可以是可前驱进行交换
public void delete(T key) { BSTNode<T> node = search(root, key); if (node != null) delete(node); node = null; } private BSTNode<T> delete(BSTNode<T> node) { // 将完全节点和直接后继交换 if (node.left != null && node.right != null) { BSTNode<T> succ = successor(node); node.key = succ.key; node = succ; } // 将孩子节点的父亲接到祖父上 BSTNode<T> child = node.left != null ? node.left : node.right; if (child != null) child.parent = node.parent; // 目标节点没有父节点则是根节点 if (node.parent == null) root = child; // 目标节点是左孩子时 else if (node == node.parent.left) node.parent.left = child; // 目标节点是右孩子时 else node.parent.right = child; return node; } private BSTNode<T> successor(BSTNode<T> node) { BSTNode<T> succ = node.right; while (succ.left != null) succ = succ.left; return succ; }// 这里只是右子树中的直接后继；整个中序遍历中直接后继还可能是其父节点或者祖先节点；
五、前序遍历对于一个数据结构而言，了解他最直接的方式就是遍历操作，而对于二叉树则有前、中、后、层次遍历四种；
1. 描述首先遍历根节点
再一次递归遍历左子树和右子树；
具体过程如下：