一、前驱结点

中序遍历的前一个结点

image.png

中序遍历

先遍历左子树，再访问结点，然后遍历右子树

查询结点的前驱结点

1.如果结点的left不为空，那么它一定是有前驱结点，并且，前驱结点在它的左子树中
根据中序遍历的特点，左子树的最右边的结点，就是它的前驱结点

如：8的前驱结点是7
4的前驱结点是3
13的前驱结点是12

2.如果结点的left为空，并且parent不为空，那么它的前驱结点一定在它的parent.parent.parent...中。如果parent一直是left结点，那么可以继续向上查，如果parent是parent.right可以终止查询
原因：中序遍历中，当遍历右子树的时候，也只先遍历它的右子树的左子树，寻找前驱结点的时候，就是逆向查询

如5的前驱结点4：=> 5的parent是 6 ， 6的parent是4，6是4的right结点所以5的结点是5.parent.parent
7的前驱结点6 : => 7的parent是6，7是6的right那么7的前驱结点是7.parent

3.如果left 为空，parent为空，说明该节点是根结点，所以它没有前驱结点

查找前驱结点

-(Node *)predecessorNode:(Node *)node{
    
    // 1.如果该节点的left不为空,前驱结点在左子树中的最右边
    Node *tempNode = node.left;
    if (tempNode != nil) {
        while (tempNode.right != nil) {
            tempNode = tempNode.right;
        }
        return tempNode;
    }
    // 2.如果left为空，parent中
    while (node.parent != nil && node == node.parent.right) {
        node = node.parent;
    }

    return node.parent;
}

二、后继结点

中序遍历时的后一个节点

查询结点的后继结点

1.如果结点的right不为空，那么它的后继结点就是它的右子树的最左边的那个结点

2.如果右子树为空，父结点不为空，查询父结点，直到某一个节点的是父结点是左子树中的时候，终止查询

3.如果右子树为空并且父结点为空的时候，说明没有后继结点

-(Node *)successor:(Node *)node{
    // 1.如果该节点的right不为空，后继结点就在它的右子树中
    Node *tempNode = node.right;
    if (tempNode != nil) {
        while (tempNode.right != nil) {
            tempNode = tempNode.right;
        }
        return tempNode;
    }
    
    // 2.如果right为空，parent不为空
    while (node.parent != nil && node == node.parent.left) {
        node = node.parent;
    }
    
    return node;
}