[数据结构与算法]线索二叉树根据任意结点P找前驱和后继

二叉树结构

typedef struct threadNode
{
    /* data */
    ElemType data;
    threadNode *lchild, *rchild;
    /*
    
        tag = 0 指针指向孩子
        tag = 1 线索指针
    */
    int ltag, rtag;
} threadNode, *threadTree;

一，先序线索二叉树

1.前驱

先序遍历是 (根左右）， 我们是通过子节点的线索来找根节点( P )的前驱和后继，所以在先序遍历中，子节点的指针指向不可能是根节点的前驱，所以不可能找到P的前驱；

但如果知道P的父节点F（可建立三叉树），且F的左右儿子为L,R,分以下四种情况讨论：

• P没有父节点，F不存在为NULL，P没有前驱
• P的父节点有左右儿子，并且P是左儿子L, 遍历顺序：F ( P ) ( R ); 以P为根节点的先序遍历（P, P的左儿子，P的右儿子）；代入F P (P的左儿子) （P的右儿子）R,所以这种情况P的前驱就是父节点；
• 同理，F没有左儿子，P就是F的右儿子，先序遍历：F ( R ) 代入
  有F P (P的左儿子) （P的右儿子），所以这种情况P的前驱就是父节点；
  以此类推F没有右儿子，P就是F的左儿子，也能得到P的前驱就是父节点；
• P的父节点有左右儿子，并且P是右儿子R, 遍历顺序：F ( L ) ( P );
  P的前驱是F的左儿子先序遍历的最后一个结点。

2.后继

如果p->rtag == 1; p的后继就是p->rchild;

如果p->rtag == 0;P一定有右儿子

• P也有左儿子，根据先序遍历，P (P的左儿子) （P的右儿子)，那么P的后继就是一定是P的左儿子先序遍历的第一个结点，P P的左儿子 （P的左儿子的左儿子）（P的左儿子的右儿子） （P的右儿子)，显而易见，P的后继是P的左儿子；
• 同理P没有左儿子，P的后继就是P的右儿子；

二，后序线索二叉树

同先序一样分析

三，中序线索二叉树

中序线索二叉树，任意一个结点P都能找到对应的前驱,后继

1. 前驱
   (左 根P 右);

如果P->ltag == 1: 前驱就是 P->lchild

如果P->ltag == 0: 前驱就是 左孩子中序遍历的最后一个结点，要想找到左孩子中序遍历的最后一个结点，我们应该左孩子出发，一直探寻它的右节点，这是因为(（P的左儿子的左儿子）P的左儿子 （P的左儿子的右儿子） 根P 右);如果 右节点不存在显然，对应的根节点就是最后一个

//找到以P为根的子树中，最后一个被中序遍历的点
threadTree LastNode(threadTree p){
    while(p->rtag == 0)
        p = p->rchild;
    return p;
}
//找到p的前驱结点
threadTree PreNode(threadTree p){
    if(p->ltag == 0)
        reutrn LastNode(p->lchild);//如果p有左孩子，找到以p左孩子为根节点先序遍历的最后一个节点
    else
    {
        return p->lchild;
    }
    //return p->ltag ? p->lchild : LastNode(p->lchild);
}

2. 后继

   和前驱同理

如果P->rtag == 0: 后继就是 P右孩子中序遍历的第一个结点，要想找到右孩子中序遍历的第一个结点，我们应该右孩子出发，一直探寻它的左节点，这是因为( 左 根P（P的右儿子的左儿子）P的右儿子 （P的右儿子的右儿子）);如果 右节点不存在显然，对应的根节点就是最后一个

//找到以P为根的右子树中，第一个被中序遍历的点
threadTree FirstNode(threadTree p)
{
    while (p->ltag == 0)
        p = p->lchild;
    return p;
}
//找到p的后继结点
threadTree NextNode(threadTree p)
{
    if (p->rtag == 0)
        reutrn LastNode(p->rchild); //如果p有右孩子，找到以p右孩子为根节点中序遍历的第一个节点
    else
    {
        return p->rchild;
    }
    //return p->rtag ? p->rchild : LastNode(p->rchild);
}