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

不念不忘少年蓝@ 2023-02-14 01:59 8阅读 0赞

**目录**

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

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

三、先序线索二叉树找先序后继

四、先序线索二叉树找先序前驱

五、后序线索二叉树找后序前驱

六、后序线索二叉树找后序后继

七、总结

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70][]

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

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

②若p->rtag == 0

![2020053020370466.png][]

![20200530203714345.png][]

//找到以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);
    }

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1][]

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

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

②若p->ltag == 0

![20200530204812584.png][]

![20200530204818166.png][]

//找到以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);
    }

## **三、先序线索二叉树找先序后继** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2][]

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

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

②若p->rtag == 0

![20200530205500788.png][]

![20200530205508424.png][]

## **四、先序线索二叉树找先序前驱** ##

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

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

② 若p->ltag = 0

![2020053021020867.png][]

![20200530210216980.png][]

前提：改用三叉链表可以找到父节点

①如果能找到p的父节点，且p是左孩子

![20200530210337964.png][]

②如果能找到p的父节点，且p是右孩子，其左兄弟为空

![20200530210408990.png][]

③如果能找到p的父节点，且p是右孩子，其左兄弟非空

![2020053021043478.png][]

④如果p是根结点，则p没有先序前驱

## **五、后序线索二叉树找后序前驱** ##

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

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

②若p->ltag == 0

![20200530211013158.png][]

![20200530211021317.png][]

## **六、后序线索二叉树找后序后继** ##

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

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

②若p->rtag == 0

![20200530211143683.png][]

![20200530211201362.png][]

前提：改用三叉链表可以找到父节点

①如果能找到p的父节点，且p是右孩子

![20200530211343832.png][]

②如果能找到p的父节点，且p是左孩子，且右兄弟为空

![20200530211356422.png][]

③如果能找到p的父节点，且p是左孩子，且右兄弟非空

![20200530211424179.png][]

④如果p是根节点，则p没有后序后继

## **七、总结** ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200530203612625.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[2020053020370466.png]: https://img-blog.csdnimg.cn/2020053020370466.png
[20200530203714345.png]: https://img-blog.csdnimg.cn/20200530203714345.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200530204720363.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200530204812584.png]: https://img-blog.csdnimg.cn/20200530204812584.png
[20200530204818166.png]: https://img-blog.csdnimg.cn/20200530204818166.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200530205412445.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[20200530205500788.png]: https://img-blog.csdnimg.cn/20200530205500788.png
[20200530205508424.png]: https://img-blog.csdnimg.cn/20200530205508424.png
[2020053021020867.png]: https://img-blog.csdnimg.cn/2020053021020867.png
[20200530210216980.png]: https://img-blog.csdnimg.cn/20200530210216980.png
[20200530210337964.png]: https://img-blog.csdnimg.cn/20200530210337964.png
[20200530210408990.png]: https://img-blog.csdnimg.cn/20200530210408990.png
[2020053021043478.png]: https://img-blog.csdnimg.cn/2020053021043478.png
[20200530211013158.png]: https://img-blog.csdnimg.cn/20200530211013158.png
[20200530211021317.png]: https://img-blog.csdnimg.cn/20200530211021317.png
[20200530211143683.png]: https://img-blog.csdnimg.cn/20200530211143683.png
[20200530211201362.png]: https://img-blog.csdnimg.cn/20200530211201362.png
[20200530211343832.png]: https://img-blog.csdnimg.cn/20200530211343832.png
[20200530211356422.png]: https://img-blog.csdnimg.cn/20200530211356422.png
[20200530211424179.png]: https://img-blog.csdnimg.cn/20200530211424179.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200530211532246.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200530211553992.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMzEwMTQ4,size_16,color_FFFFFF,t_70