线索二叉树的后继

一.中序线索二叉树

中序后继
在中序线索二叉树中找到指定的结点*p的中序后继next
1.如果p->rtag == 1,则next = p->rchild
2.如果p->rtag == 0,那么在p的右子树中最左下的那个结点为后继结点

//找到以p为子树的最左下的结点
ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下的结点（不一定是叶节点）
    while(p->ltag = 0) p=p->lchild;
    return p; 
} 

//中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p)
{
    if(p->rtag = 1) return p->rchild; //满足条件1时的做法 
    else return FirstNode(p->rchild);//满足条件2时的做法 
 } 



//对中序线索二叉树进行中序遍历
void InOrder(ThreadNode *T){
    for(ThreadNode *p = Firstnode(T);p!=NULL;p=Nextnode(p))
    visit(p);
} 

中序前驱
在中序线索二叉树中找到指定结点*p的中序前驱pre
1.如果p->ltag = 1,则pre = p->lchild
2.如果p->rtag = 0,则p的左子树最右下那个结点为前驱结点

//找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p)
{
    while(p->rtag = 0) p = p->rchild;
    return p;
}

ThreadNode *Prenode(ThreadNode *p)
{
    if(p->ltag = 1) return p->lchild;
    else return LastNode(p->lchild);
}

void RevInorder(ThreadNode *T)
{
    for(ThreadNode *p = Lastnode(T);p!=NULL;p=Prenode(p))  //p结点初始为最右下即最后一个结点 
    visit(p);
}

二.先序线索二叉树

在先序线索二叉树中找到指定结点*p的先序后继next
1.若p->rtag = 1,则next=p->rchild
2.若p->rtag = 0,则如果有左孩子那么next为左孩子，如果有
右孩子那么next为右孩子

在先序线索二叉树中找到指定结点*p的先序前驱pre
1.若P->ltag = 1，则pre = p->lchild
2.若p->ltag = 0,找不到
如果能找到p的父节点，且p为左孩子 那么 pre=父节点
如果能找到p的父节点，且p为右孩子 且左兄弟为空 pre=父节点
如果能找到p的父节点，且p为右孩子，左兄弟非空 pre=左兄弟子树中最后一个被遍历的结点
如果p是根节点，则p没有先序结点

三.后序线索二叉树

在后序线索二叉树中找到指定结点*p的后序前驱pre
1.如果p-> ltag = 1,则pre = p->lchild
2.如果p-> ltag = 0,若有右孩子那么pre=右孩子，若没有右孩子则为左孩子

在后序线索二叉树中找到指定结点*p的后序后继next
1.如果p-> rtag = 1,则next = p->rchild
2.如果p-> rtag = 0,则找不到
如果能找到p的父节点，且p是右孩子 next=父节点
如果能找到p的父节点，且p是左孩子且右兄弟为空 next=父节点
如果能找到p的父节点，且p是左孩子，其右兄弟为空，p的后继结点为右兄弟子树第一个被后序遍历的结点
如果p是根节点，则p没有后序后继