十三、前驱节点(predecessor)&后继节点(succes

前驱节点(predecessor)

• 前驱节点：中序遍历时的前一个节点
  • 如果是二叉搜索树，前驱节点就是前一个比它小的节点

前驱节点(predecessor)

寻找前驱节点有三种情况：

当node.left != null(左子树不为null)
举例：6、13、8
前驱节点：predecessor = node.left.right.right.right...
终止条件：right为null

当node.left == null && node.parent != null(左子树为null但是它的父节点不为null)
举例：7、11、9、1
前驱节点：predecessor = node.parent.parent.parent...
终止条件：node在parent的右子树中

当node.left == null && node.parent == null(左子树为null并且父节点也为null)
举例：没有左子树的根节点(上图中8没有左子树的情况)
那就没有前驱节点

private Node<E> predecessor(Node<E> node){
    if(node == null) return null;
    
    // 前驱节点在左子树当中(left.right.right.right...)
    Node<E> 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;
}

后继节点(successor)

• 后继节点：中序遍历时的后一个节点

  • 如果是二叉搜索树，后继节点就是后一个比它大的节点

    
    后继节点(successor)

寻找后继节点有三种情况：

当node.right != null
举例：1、8、4
后继节点：successor = node.right.left.left.left...
终止条件：left为null

当node.right == null && node.parent != null
举例：7、6、3、11
后继节点：successor = node.parent.parent.parent...
终止条件：node在parent的左子树中

当node.right == null && node.parent == null
举例：没有右子树的根节点(上图中8没有右子树的情况)
那就没有前驱节点

private Node<E> successor(Node<E> node){
    if(node == null) return null;
    
    // 后继节点在右子树当中(right.left.left.left...)
    Node<E> 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;
    }
    // 第一种情况：node.parent == null
    // 第二种情况：node == node.parent.left
    return node.parent;
}

代码链接