Fz's Blog
Fz's Blog

线索化二叉树找前驱后继节点

房子 房子 收录于 考研408
  约 3700 字 预计阅读 8 分钟 - 次阅读   - 条评论  
目录

线索二叉树中前驱和后继的查找方法

说明

如果某个结点的左指针或右指针是线索，那么查找前驱或后继就非常方便：

ltag = 1：lchild 直接指向前驱

rtag = 1：rchild 直接指向后继

但是如果 ltag = 0 或 rtag = 0，说明对应指针指向的是孩子，这时就需要根据不同遍历方 式进行分析。

一、中序线索二叉树中查找前驱和后继

1. 查找中序后继

已知结点 p，寻找它的中序后继。

情况一：p->rtag == 1直接返回p的右孩子 

1
2
3
4

if(p->rtag == 1)
{
    return p->rchild;
}

情况二：p->rtag == 0

说明 p 有右孩子。

根据中序遍历：

1

左 → 根 → 右

访问完 p 之后，接下来要进入 p 的右子树。

而右子树中，第一个被访问的结点是：

右子树中最左下的结点

所以

p 的中序后继 = p 的右子树中最左下的结点

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

ThreadNode* NextNode_InOrder(ThreadNode *p)
{
    if(p->rtag == 1)
    {
        return p->rchild;
    }
    else
    {
        p = p->rchild;

        while(p->ltag == 0)
        {
            p = p->lchild;
        }

        return p;
    }
}

2. 查找中序前驱

已知结点 p，寻找它的中序前驱。

情况一：p->ltag == 1直接返回左孩子 

1
2
3
4

if(p->ltag == 1)
{
    return p->lchild;
}

情况二：p->ltag == 0

说明 p 有左孩子。

根据中序遍历：

1

左 → 根 → 右

访问 p 之前，最后访问的是它左子树中最靠右的结点。

而左子树中，最后一个被访问的结点是：

左子树中最右下的结点

所以

p 的中序前驱 = p 的左子树中最右下的结点

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

        while(p->rtag == 0)
        {
            p = p->rchild;
        }

        return p;
    }
}

3. 中序查找总结

查找目标 条件 结果
中序后继 rtag == 1 rchild
中序后继 rtag == 0 右子树中最左下结点
中序前驱 ltag == 1 lchild
中序前驱 ltag == 0 左子树中最右下结点

中序线索二叉树中，查找前驱和后继都比较方便，所以它是最常用的线索二叉树。

二、先序线索二叉树中查找前驱和后继

先序遍历顺序为：

1

(根)根结点 → (左)左子树 → (右)右子树

1. 查找先序后继

已知结点 p，寻找它的先序后继。

情况一：p->ltag == 0说明有左孩子直接返回左孩子

代码：

1
2
3
4

if(p->ltag == 0)
{
    return p->lchild;
}

情况二：p->ltag == 1 且 p->rtag == 0

说明 p 没有左孩子，但是有右孩子。

这时访问完 p 后，就应该访问它的右孩子。

所以：

p 的先序后继 = p 的右孩子

代码：

1
2
3
4

if(p->ltag == 1 && p->rtag == 0)
{
    return p->rchild;
}

情况三：p->rtag == 1直接返回右孩子

代码：

1
2
3
4

if(p->rtag == 1)
{
    return p->rchild;
}

先序后继完整代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ThreadNode* NextNode_PreOrder(ThreadNode *p)
{
    if(p->ltag == 0)
    {
        return p->lchild;
    }
    else
    {
        return p->rchild;
    }
}
为什么这么写就可以？

因为：

如果 ltag == 0，说明有左孩子，先序后继就是左孩子；

如果 ltag == 1，说明没有左孩子，那么后继要么是右孩子，要么是右线索。

而这两种情况都可以用：

p->rchild

2. 查找先序前驱

注意

先序前驱比先序后继麻烦。

情况一：p->ltag == 1直接返回左孩子

代码：

1
2
3
4

if(p->ltag == 1)
{
    return p->lchild;
}

情况二：p->ltag == 0

说明 p 有左孩子。

注意：

有左孩子并不能直接推出前驱是谁

对于先序遍历来说，某个结点的前驱可能是它的父结点，也可能是其他结点。因为根左右,p既可能为左又可能为右,前驱不固定

如果结点结构中没有父指针，只靠当前结点 p，通常无法直接找到它的先序前驱。

在先序线索二叉树中，如果 ltag == 0，仅凭当前结点通常无法直接找到它的先序前驱，往往需要父指针或从根结点重新遍历。

使用父指针时的先序前驱

如果结点中有父指针：

1

struct ThreadNode *parent;

那么可以进一步分析。

对于结点 p：

情况一：p 是父结点的左孩子

先序遍历是：

1

根 → 左 → 右

如果 p 是父结点的左孩子，那么访问 p 之前刚访问的是它的父结点。

所以：

1

p 的先序前驱 = parent

情况二：p 是父结点的右孩子

如果 p 是父结点的右孩子，那么访问 p 之前，通常已经访问完父结点的左子树。

所以它的前驱是：

找父结点左子树中，先序遍历的最后一个结点

而在一棵子树中，先序遍历最后访问的结点，一般要这样找：

1
2
3
4

从该子树根开始：
如果有右孩子，就一直往右走；
否则如果有左孩子，就往左走；
直到走到没有孩子的结点。

先序前驱总结

条件 先序前驱
ltag == 1 lchild
ltag == 0 且无父指针 通常不能直接找
p 是父结点左孩子 父结点
p 是父结点右孩子 父结点左子树中先序遍历的最后一个结点

三、后序线索二叉树中查找前驱和后继

1. 查找后序前驱

Tip

后序遍历中，访问某个结点 p 之前，最后访问的是它的右子树中的根个结点。

所以访问根结点之前，通常先访问它的右子树。

情况一：p->rtag == 0直接返回右孩子

说明 p 有右孩子。

因为后序遍历中，根结点的前一个结点通常是右子树的根，或者右子树中最后访问的结点(左右(左右根)根)。

对于后序遍历来说，访问完右子树后才访问根结点。

而右子树的根结点正是右子树后序遍历的最后一个结点。

代码：

1
2
3
4

if(p->rtag == 0)
{
    return p->rchild;
}

情况二：p->rtag == 1 且 p->ltag == 0直接返回左孩子

说明 p 没有右孩子，但是有左孩子。

这时访问 p 之前，最后访问的是左子树的根结点。

代码：

1
2
3
4

if(p->rtag == 1 && p->ltag == 0)
{
    return p->lchild;
}

情况三：p->ltag == 1直接返回左孩子

代码：

1
2
3
4

if(p->ltag == 1)
{
    return p->lchild;
}

后序前驱完整代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ThreadNode* PreNode_PostOrder(ThreadNode *p)
{
    if(p->rtag == 0)
    {
        return p->rchild;
    }
    else
    {
        return p->lchild;
    }
}
为什么可以这样写？

如果有右孩子，后序前驱是右孩子；

如果没有右孩子，那么前驱要么是左孩子，要么是左线索。

2. 查找后序后继

后序后继比后序前驱麻烦。

某个结点访问完之后，接下来可能访问它的父结点，也可能访问父结点的右子树中的结点。

情况一：p->rtag == 1直接返回右孩子

代码：

1
2
3
4

if(p->rtag == 1)
{
    return p->rchild;
}

情况二：p->rtag == 0

说明 p 有右孩子。

但是注意：

有右孩子并不能直接推出后继是谁(没有线索节点)

在后序遍历中，当前结点 p 的后继往往与父结点有关。

如果没有父指针，仅凭当前结点 p 通常无法直接找到它的后序后继。

使用父指针时的后序后继

如果结点中有父指针：

1

struct ThreadNode *parent;

那么可以根据 p 与父结点的关系判断。

情况一：p 是父结点的右孩子

如果 p 是父结点的右孩子，那么访问完 p 后，就访问它的父结点。

所以：

p 的后序后继 = parent

情况二：p 是父结点的左孩子，并且父结点没有右孩子

如果 p 是父结点的左孩子，而且父结点没有右孩子，那么访问完左子树后，就访问父结点。

所以：

p 的后序后继 = parent

情况三：p 是父结点的左孩子，并且父结点有右孩子

如果 p 是父结点的左孩子，并且父结点还有右子树，那么访问完左子树后，要进入右子树。

后序遍历右子树时，第一个访问的结点是：左右(左右根)根

右子树中后序遍历的第一个结点

所以找“后序遍历第一个结点”的规则是：

  • 从右子树根开始：
  • 如果有左孩子，就一直往左走；
  • 否则如果有右孩子，就往右走；
  • 直到走到没有孩子的结点。

p 的后序后继 = 父结点右子树中后序遍历的第一个结点

后序后继总结

条件 后序后继
rtag == 1 rchild
rtag == 0 且无父指针 通常不能直接找
p 是父结点右孩子 父结点
p 是父结点左孩子，父结点无右孩子 父结点
p 是父结点左孩子，父结点有右孩子 父结点右子树中后序遍历的第一个结点

四、三种线索树查找前驱和后继总结

1. 中序线索二叉树

查找目标 方法
中序前驱 若 ltag == 1，则为 lchild；否则为左子树中最右下结点
中序后继 若 rtag == 1，则为 rchild；否则为右子树中最左下结点

中序线索二叉树中，前驱和后继都比较容易找。

2. 先序线索二叉树

查找目标 方法
先序前驱 若 ltag == 1，则为 lchild；否则通常需要父指针或从根重新遍历
先序后继 若有左孩子，则为左孩子；否则为 rchild

先序线索二叉树中，找后继容易，找前驱困难。

3. 后序线索二叉树

查找目标 方法
后序前驱 若有右孩子，则为右孩子；否则为 lchild
后序后继 若 rtag == 1，则为 rchild；否则通常需要父指针或从根重新遍历

后序线索二叉树中，找前驱容易，找后继困难。

五、完整代码整理

下面给出三种线索二叉树中常见的前驱、后继查找函数。

1. 中序线索二叉树

中序后继 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

ThreadNode* NextNode_InOrder(ThreadNode *p)
{
    if(p->rtag == 1)
    {
        return p->rchild;
    }
    else
    {
        p = p->rchild;

        while(p->ltag == 0)
        {
            p = p->lchild;
        }

        return p;
    }
}

中序前驱 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

        while(p->rtag == 0)
        {
            p = p->rchild;
        }

        return p;
    }
}

2. 先序线索二叉树

先序后继 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ThreadNode* NextNode_PreOrder(ThreadNode *p)
{
    if(p->ltag == 0)
    {
        return p->lchild;
    }
    else
    {
        return p->rchild;
    }
}

先序前驱

如果 ltag == 1，可以直接找到前驱：

1
2
3
4
5
6
7
8
9

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

    return NULL;
}

这里返回 NULL 并不是说一定没有前驱，而是表示：

1

仅凭当前结点和普通先序线索，不能直接确定前驱。

如果要完整查找，通常需要父指针，或者从根结点重新进行先序遍历查找。

3. 后序线索二叉树

后序前驱 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ThreadNode* PreNode_PostOrder(ThreadNode *p)
{
    if(p->rtag == 0)
    {
        return p->rchild;
    }
    else
    {
        return p->lchild;
    }
}

后序后继

如果 rtag == 1，可以直接找到后继：

1
2
3
4
5
6
7
8
9

ThreadNode* NextNode_PostOrder(ThreadNode *p)
{
    if(p->rtag == 1)
    {
        return p->rchild;
    }

    return NULL;
}

这里返回 NULL 同样不是说一定没有后继，而是表示：

1

仅凭当前结点和普通后序线索，不能直接确定后继。

如果要完整查找，通常需要父指针，或者从根结点重新进行后序遍历查找。

六、记忆口诀

可以这样记：

中序：前驱、后继都好找

先序：后继好找，前驱难找

后序：前驱好找，后继难找

原因

先序：根 → 左 → 右 访问完根以后，很容易知道下一个是谁，所以后继好找。

后序：左 → 右 → 根 访问根之前，很容易知道前一个是谁，所以前驱好找。

中序：左 → 根 → 右 左右方向都比较对称，所以前驱和后继都好找。

中序最常用 先序找后继方便 后序找前驱方便

相关内容

更新于 2026-06-23 
数据结构代码算法
返回 | 主页

目录