线索二叉树前驱结点与后继结点的查找

【中序线索二叉树】

前驱结点

对于中序线索二叉树来说，当给出指定结点 p，要找到其中序前驱结点 pre，可按照如下步骤：

1. 若 p->ltag=1，说明进行了线索化，那么 pre=p->lchild
2. 若 p->ltag=0，说明其必有左孩子，那么 pre 为 p 的左子树中最右下结点

ThNode *findPreByInThreadTree(ThNode *p) { //中序线索二叉树找前驱
    if (p->ltag == 1) //已线索化
        return p->lchild;
    else{ //未线索化
        p = p->lchild; //p的左子树
        while (p->rtag == 0) //寻找以p为根的子树中，最右下方的结点
            p = p->rchild;
        return p;
    }
}

后继结点

对于中序线索二叉树来说，当指定结点 p，要找到其中序后继结点 post，可按照如下步骤：

1. 若 p->rtag=1，说明进行了线索化，那么 post=p->rchild
2. 若 p->rtag=0，说明其必有右孩子，那么 post 为 p 的右子树中最左下结点

ThNode *findPostByInThreadTree(ThNode *p) { //中序线索二叉树找后继
    if (p->rtag == 1) //已线索化
        return p->rchild;
    else { //未线索化
        p = p->rchild; //p的右子树
        while (p->ltag == 0) //寻找以p为根的子树中，最左下方的结点
            p = p->lchild;
        return p;
    }
}

【前序线索二叉树】

前驱结点

对于前序线索二叉树来说，当指定结点 p，要找到其前序前驱结点 pre，可按照如下步骤：

1. 若 p->ltag=1，说明进行了线索化，那么 post=p->lchild
2. 若 p->ltag=0，说明没有进行线索化，此时 p 的前驱与 p 的父结点有关，因此只能从头开始遍历

---

为克服上述问题，一般采用三叉链表线索化的来建立前序线索二叉树，这样一来，可以很容易的找到其前驱：

1. 若 p->ltag=1，说明进行了线索化，那么 post=p->lchild
2. 若 p->ltag=0，说明没有进行线索化，此时根据三叉链表的 parent 指针，寻找 p 的父结点：
   • 若能找到 p 的父结点，且 p 是左孩子，那么 p 的父结点即为前驱
   • 若能找到 p 的父结点，且 p 是右孩子，左兄弟为空，那么 p 的父结点即为前驱
   • 若能找到 p 的父结点，且 p 是右孩子，左兄弟非空，那么 p 的左兄弟子树中最后一个被先序遍历的点即为前驱
   • 若不能找到 p 的父结点，即 p 是根结点，则 p 没有前序前驱

后继结点

对于前序线索二叉树来说，当指定结点 p，要找到其前序后继结点 post，可按照如下步骤：

1. 若 p->rtag=1，说明进行了线索化，那么 post=p->rchild
2. 若 p->rtag=0，说明没有进行线索化，必有右孩子，那么 post 为 p 的子树中第一个被先序遍历的结点
   • 若 p 有左孩子，则先序后继为左孩子
   • 若 p 没有左孩子，则先序后继为右孩子

ThNode *findPostByPreThreadTree(ThNode *p) { //前序线索二叉树找后继
    if (p->rtag == 1) //已线索化
        return p->rchild;
    else { //未线索化
        if (p->lchild != NULL) //左孩子存在
            return p->lchild;
        else //左孩子不存在
            return p->rchild;
    }
}

【后序线索二叉树】

前驱结点

对于后序线索二叉树来说，当指定结点 p，要找到其后序前驱结点 pre，可按照如下步骤：

1. 若 p->ltag=1，说明进行了线索化，那么 pre=p->lchild
2. 若 p->ltag=0，说明没有进行线索化，必有左孩子，那么 pre 为 p 的子树中最后一个被后序遍历的结点
   • 若 p 有右孩子，则前驱为 p 的右孩子
   • 若 p 没有右孩子，则前驱为 p 的左孩子

ThNode *findPreByPostThreadTree(ThNode *p) { //后序线索二叉树找前驱
    if (p->ltag == 1) //已线索化
        return p->lchild;
    else { //未线索化
        if (p->rchild != NULL) //右孩子存在
            return p->rchild;
        else //左孩子不存在
            return p->lchild;
    }
}

后继结点

对于后序线索二叉树来说，当指定结点 p，要找到其后序后继结点 post，可按照如下步骤：

1. 若 p->rtag=1，说明进行了线索化，那么 post=p->rchild
2. 若 p->rtag=0，说明没有进行线索化，此时 p 的左右结点只可能是其前驱，p 的后继与 p 的父结点有关，因此只能从头开始遍历

---

为克服上述问题，一般采用三叉链表线索化的来建立后序线索二叉树，这样一来，可以很容易的找到其后继：

1. 若 p->rtag=1，说明进行了线索化，那么 post=p->rchild
2. 若 p->rtag=0，说明没有进行线索化，此时根据三叉链表的 parent 指针，寻找 p 的父结点：
   • 若能找到 p 的父结点，且 p 是右孩子，则 p 的父结点为其后继
   • 若能找到 p 的父结点，且 p 是左孩子，其右兄弟为空，则 p 的父结点为其后继
   • 若能找到 p 的父结点，且 p 是左孩子，其右兄弟非空，则 p 的右兄弟子树中第一个被后序遍历的结点为其后继
   • 若不能找到 p 的父结点，即 p 是根结点，则 p 没有后序后继