■ 前提是：中序遍历才有所谓的前驱和后驱结点。
1. 前驱结点：中序遍历时的前一个结点。
即：前驱结点（就是比当前结点小的前一个结点）。
（1） 哪个位置的结点有机会有前驱（根 和 右）：
（2) “前一个结点”：需要离得最近。
①根（看左，找左区间最大的，离得近）
②右（看根，找根）
(3)方法（接口）：public Node<E> predecessor(Node<E> node)；
分析：public Node<E> predecessor(Node<E> node){
//当前传入结点（可，需要判断一下：是否有左（有左即可，不需要有右））
node = node.left;
//① 若node 非空：则作为“根”，去左区间找最大的
//② 若node 空：找根（“父结点”），通过判断是否构成“根-右”的关系。【找的过程是逆思维：因为需要遍历 while(“根-左”)， 跳出循环则是找到了“根-右”的关系】
}
（4）具体代码：
// 内部类（一般是静态内部类） private static class Node<E> { E elmement; Node<E> left; Node<E> right; // 父结点（很有用） Node<E> parent; // 当你在外部传入一个结点时，还可以直接指定父结点（但是该结点的左右结点还没诞生，so。。。） public Node(E element, Node<E> parent) { this.elmement = element; this.parent = parent; } }
// 前驱结点 public Node<E> predecessor(Node<E> node) { // 有左节点（left.right.right.right...） Node<E> p = node.left; if (p != null) { // while(p != null) 这样会导致最后一个结点为null，此时 p = null while (p.right != null) { p = p.right; } return p; } // 没有左节点（视图找到第一个父结点的右结点等于当前结点） // 若一直是父节点左，就继续上一层的父节点 while (node.parent != null && node.parent.left == node) { node = node.parent; } // 来到这里：要么父节点是null，要么是 当前结点是父节点的右结点 return node.parent; }
2. 后驱结点：中序遍历时的后一个结点。
同理可得
