前驱节点:中序遍历时的前一个节点
思路:
1.node.left != null时predecessor = node.left.right.right.right... 终止条件为node.right = null
2.node.left == null && node.parent != null时predecessor = node.parent.parent.parent...终止条件为node.parent=null && node != node.parent.left
3.node.left == null && node.parent == null 则没有前驱节点
java代码:
//前驱节点 public Nodepredecessor(Node node) { if(node == null) return null; //前驱节点在左子树中(left.right.right.right.....) Node p = node.left; if (p != null) { while(p.right != null) { p = p.right; } return p; } //从祖父节点、祖父节点中寻找前驱节点 while(node.parent != null && node == node.parent.left) { node = node.parent; } //node.parent == null //node == node.parent.right return node.parent; }



