可以将该结点分为两种情况，

1.没有左子树，那它是某一个结点的右子树的最左结点，然后找到这个右子树的parent即可

　　找它的parent，直到当前节点是parent的右子树为止

2.有左子树，那前驱节点就是它的左子树的最右结点

 

public static Node findPreNode(Node node){        if(node == null) return null;        if(node.left == null){            Node parentNode = node.parent;            while(parentNode != null && parentNode.right != node){                node = parentNode;                parentNode = node.parent;            }            return parentNode;        } else{            node = node.left;            while(node.right != null){                node = node.right;            }            return node;        }    }

 

　　

 

测试代码

 

public static void main(String[] args){        Node node = new Node(1);        node.left = new Node(2);        node.right = new Node(3);        node.left.left = new Node( 4 );        node.left.right = new Node(5);        node.right.left = new Node( 6 );        node.right.right = new Node( 7 );        node.left.left.left = new Node(11);        node.left.right.right = new Node( 8 );        node.right.left.right = new Node(9);        node.right.right.right = new Node(10);        node.parent = null;        node.left.parent = node;        node.right.parent = node;        node.left.left.parent = node.left;        node.left.right.parent = node.left;        node.right.left.parent = node.right;        node.right.right.parent = node.right;        node.left.left.left.parent = node.left.left;        node.left.right.right.parent = node.left.right;        node.right.left.right.parent = node.right.left;        node.right.right.right.parent = node.right.right;        System.out.println(findPreNode( node.left.right.right ).value);        System.out.println(findPreNode( node.right.left ).value);    }