二叉树的下一个结点
给定一棵二叉树和其中一个结点，如何找出中序遍历顺序的下一个结点
树中的结点除了有两个分别指向左右子结点的指针外，还有一个指向父结点的指针
分析：
如果该结点存在右子树，那么下一个结点就是右子树的最左结点
如果该结点不存在右子树，继续判断如果该结点是它父结点的左子结点，那么它的下一个结点就是它的父结点，如果不是，沿着指向父结点的指针一直向上遍历，直到找到一个是它父结点的左子结点的结点，如果存在，那么这个结点的父结点就是下一个结点
class BinaryNode<Key extends Comparable<Key>> {
public Key key;
public BinaryNode parent, left, right;
public BinaryNode(Key key) {
this.key = key;
}
}
public class I58_NextNodeInBinaryTrees {
public BinaryNode getNext(BinaryNode node) {
if (Optional.ofNullable(node).isEmpty()) {
return null;
}
BinaryNode next = null;
if (Optional.ofNullable(node.right).isPresent()) {
// 存在右子树，那么下个结点就是右子树中最左结点
BinaryNode right = node.right;
while (Optional.ofNullable(right.left).isPresent()) {
right = right.left;
}
next = right;
} else if (Optional.ofNullable(node.parent).isPresent()) {
BinaryNode current = node;
BinaryNode parent = node.parent;
while (Optional.ofNullable(parent).isPresent()
&& current == parent.right) {
current = parent;
parent = parent.parent;
}
next = parent;
}
return next;
}
}
