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

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

一、前驱节点

前驱节点（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;
}