【数据结构与算法】系列十 - 前驱后继节点

前驱后继节点是针对中序遍历的。可以借助二叉搜索树来理解，但是前驱和后继是适用于任何二叉树的。

一、前驱节点

前驱节点（predecessor）：中序遍历时当前节点的前一个节点。

如果是二叉搜索树，前驱节点就是前一个比它小的节点。

如上图，中序遍历结果：1、2、3、4、5、6、7、8、9、10、11、12、13。

根据中序遍历的特点可以得知，左子树最右边的节点遍历结束，才开始遍历（输出）根节点。

如果node.left != null，例如上图中的6、13、8，前驱节点就是predecessor = node.left.right.right.right...，终止条件是right == null。

上面的前驱节点是建立在左子树不为空的情况下，如果左子树是空呢（即node.left == null）？

如果node.left == null，就需要找node的父节点，直到node在parent的右子树中，最终parent就是node的前驱节点，即predecessor = node.parent.parent.parent...（例如上图中的7、11、9）。如果最终父节点是空的（node.parent == null），那就没有前驱节点（例如上图中的1）。

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  前驱就是node的父节点
  return node.parent;
}

二、后继节点

后继节点（successor）：中序遍历时当前节点的后一个节点。

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

后继节点和前驱节点思路基本一致，唯一区别就是一个是往左找，一个是往右找。

如果node.right != null，例如上图中的1、8、4，后继节点就是successor = node.right.left.left.left...，终止条件是left == null。

上面的后继节点是建立在右子树不为空的情况下，如果右子树是空呢（即node.right == null）？

如果node.right == null，就需要找node的父节点，直到node在parent的左子树中，最终parent就是node的后继节点，即successor = node.parent.parent.parent...（例如上图中的7、6、3）。如果最终父节点是空的（node.parent == null），那就没有后继节点（例如上图中的11）。

private Node<E> successor(Node<E> node) {
  if (node == null) return null;
  
  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;
  }

  return node.parent;
}