前驱节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的前一个节点为该节点的前驱节点；
后继节点：对一棵二叉树进行中序遍历，遍历后的顺序，当前节点的后一个节点为该节点的后继节点；
例如一颗完全二叉树（1,2,3,4,5,6,7），按照中序遍历后的顺序为：（4,2,5,1,6,3,7），1节点的前驱节点为：5，后继节点为6.
若每次遍历二叉树进行查找前驱节点或后继节点，复杂度太高，需要O(n)的时间复杂度。例如查找5节点的后继节点，则需要对整棵树进行遍历，而真正可以做到的是，只需要经过两者之间的距离就可以找到其后继节点：52
1。
因此可以断定：
前驱节点：当前节点左子树的最右节点（例如1节点的前驱节点为5），若无左子树，则：当前节点是其父节点的右子树（5节点的前驱节点为2）；
后继节点：当前节点右子树的最左节点（1节点的后继节点为6），若无右子树，则：当前节点为其父节点的左子树（6节点的后继节点为3）。
Java代码：找后继节点：
public class GetSuccessposNode {//找后继节点
public static class Node{
int value;
Node parent;
Node leftNode;
Node rightNode;
public Node(int data) {
this.value = data;
}
}
public static Node getSuccessNode(Node node) {
if (node == null) {
return node;
}
if (node.rightNode!=null) {
return getLeftNode(node.rightNode);
}else {
Node parent = node.parent;
while (parent!=null && parent.leftNode!=node) {
node = parent;
parent = node.parent;
}
return parent;
}
}
private static Node getLeftNode(Node node) {
if (node == null) {
return node;
}
while (node.leftNode!=null) {
node = node.leftNode;
}
return node;
}
}
找前驱节点：
public class GetSuccesspreNode {
public static class Node {
int value;
Node parentNode;
Node leftNode;
Node rightNode;
public Node(int data) {
this.value = data;
}
}
public static Node getSuccessPreNode(Node node) {
if (node==null) {
return node;
}
if (node.leftNode!=null) {
return getRightNode(node.leftNode);
}else {
Node parent = node.parentNode;
while (parent!=null && parent.rightNode!=node) {
node = parent;
parent = node.parentNode;
}
return node;
}
}
private static Node getRightNode(Node node) {
if (node==null) {
return node;
}
while (node.rightNode!=null) {
node = node.rightNode;
}
return node;
}
}
