二叉树的下一个结点

问题

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。
注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

算法

二叉树的下一个结点

我们不关心当前节点的左子节点,因为它不在我们的考虑范围内,它必定出现在当前节点的前面。

第一种情况:一个节点有右子树,找到它右子树最左孩子
(比如B的下一个节点是G节点)

第二种情况:一个节点没有右子树,此时又分为两种情况
1、若有父节点并且是父节点的左子节点,则父节点就是其下一个节点
2、若有父节点但不是父节点的左子节点(比如E),不断向上找,直到找到是某个节点的左子树