前驅(qū)節(jié)點(diǎn)

• 前驅(qū)節(jié)點(diǎn)：中序遍歷時(shí)的前一個(gè)節(jié)點(diǎn)
  如果是二叉搜索樹，前驅(qū)節(jié)點(diǎn)就是前一個(gè)比它小的節(jié)點(diǎn)
• node.left!=null
  前驅(qū)節(jié)點(diǎn)predecessor=node.left.right.right.right....
  終止條件為:right為null
• node.left==null&&node.parent!=null
  前驅(qū)節(jié)點(diǎn)predecessor=node.parent.parent.paremt....
  終止條件:node在parent的右子樹中
• node.left==null&&node.parent==null
  該節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)

后繼節(jié)點(diǎn)

• 后繼節(jié)點(diǎn):中序遍歷時(shí)的后一個(gè)節(jié)點(diǎn)
  如果是二叉搜索樹,后繼節(jié)點(diǎn)就是后一個(gè)比它大的節(jié)點(diǎn)
• node.right!=null
  successor=node.right.left.left.left...
  終止條件:left為null
• node.right==null&&node.parent!=null
  successor=node.parent.parent.parent....
  終止條件:node在parent的左子樹中
• node.right==null&&node.parent==null
  沒有前驅(qū)節(jié)點(diǎn)