数据结构笔记——线索二叉树找前驱/后继_中序线索二叉树找前驱后继

作者：羊村懒王 | 2024-05-31 05:52:48

踩

中序线索二叉树找前驱后继

一、中序线索二叉树找中序后继

一、中序线索二叉树找中序后继

在中序线索二叉树中找到指定结点*p的中序后继next

①若p->rtag == 1,则next = p->rchild

②若p->rtag == 0


//找到以P为跟的子树中，第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下结点（不一定是叶子结点）
    while(p->ltag == 0)
        p = p->lchild;
    return p;
}
 
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *Nextnode(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag == 0)
        return Firstnode(p->rchild);
    else
        return p->rchild;
}
 
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）  空间复杂度O(1)
void Inorder(ThreadNode *T){
    for(ThreadNode *p = Firstnode(T);p != NULL; p = Nextnode(p))
        visit(p);
}

二、中序线索二叉树中找中序前驱

在中序线索二叉树中找到指定结点*p的中序前驱pre

①若p->ltag == 1,则pre = p->lchild

②若p->ltag == 0


//找到以P为跟的子树中，最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
    //循环找到最右下结点（不一定是叶子结点）
    while(p->rtag == 0)
        p = p->rchild;
    return p;
}
 
//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Prenode(ThreadNode *p){
    //左子树中最右下结点
    if(p->ltag == 0)
        return Lastnode(p->lchild);
    else
        return p->lchild;
}
 
//对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）  空间复杂度O(1)
void RevInorder(ThreadNode *T){
    for(ThreadNode *p = Lastnode(T);p != NULL; p = Prenode(p))
        visit(p);
}