思路:
(1)若该节点存在右子树:则下一个节点为右子树最左子节点(如图节点B)
(2)若该节点不存在右子树:这时分两种情况:
2.1 该节点为父节点的左子节点,则下一个节点为其父节点(如图节点D)
2.2 该节点为父节点的右子节点,则沿着父节点向上遍历,直到找到这样一个节点:它是它父节点的左子节点,则该节点的父节点就是我们要找的(如图节点I,沿着父节点一直向上查找找到B(B为其父节点的左子节点),则B的父节点A为下一个节点)。
其实(2)也可以总结为一点:若该节点不存在右子树,则沿着父节点向上遍历,直到找到这样一个节点:它是它父节点的左子节点,则该节点的父节点就是我们要找的