考研笔记

线索二叉树

线索二叉树是「废物利用」：把二叉链表里那 个空指针拿来存前驱和后继。

动机链条很短，但每一环都要能说出来：

  1. 遍历 把结点排成线性序列，每个结点都有直接前驱和直接后继。
  2. 但传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。
  3. 而含 个结点的二叉树中恰好有 个空指针闲着。
  4. 由此设想能否利用这些空指针来存放指向其前驱或后继的指针，这样就可以像遍历单链表那样方便地遍历二叉树。

「引入线索二叉树正是为了加快查找结点前驱和后继的速度。」

机制

个空指针的推导

这个数必须会推，不能只记结论：

  • 每个叶结点都有 2 个空指针，每个度为 1 的结点都有 1 个空指针，故空指针总数为 ；
  • 又由 5.2.1 的 ，得

结点结构与两个标志位

规定：若无左子树，令 lchild 指向其前驱结点；若无右子树，令 rchild 指向其后继结点。 还需增加两个标志域，以标识指针域指向左（右）孩子或前驱（后继）。

lchildltagdatartagrchild
域指示结点的左孩子域指示结点的前驱域指示结点的右孩子域指示结点的后继 
typedef struct ThreadNode{
    ElemType data;                        //数据元素
    struct ThreadNode *lchild,*rchild;    //左、右孩子指针
    int ltag,rtag;                        //左、右线索标志
}ThreadNode,*ThreadTree;

以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。

边界辨析：

「线索」指的是那些指针，不是标志位。 ltag/rtag 只是用来区分「这个指针是孩子还是线索」的标记， 一个结点最多有 2 个线索，一棵树最多有 个线索——恰好等于原来的空指针数，一个不多一个不少。

中序线索化：靠 pre 指针

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。

以中序线索二叉树的建立为例：附设指针 pre 指向刚刚访问过的结点，指针 p 指向正在访问的结点，即 pre 指向 p 的前驱。在中序遍历的过程中，检查 p 的左指针是否为空，若为空就将它指向 pre；检查 pre 的右指针是否为空，若为空就将它指向 p。

void InThread(ThreadTree &p,ThreadTree &pre){
    if(p!=NULL){
        InThread(p->lchild,pre);           //递归，线索化左子树
        if(p->lchild==NULL){               //当前结点的左子树为空
            p->lchild=pre;                 //建立当前结点的前驱线索
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL){  //前驱结点非空且其右子树为空
            pre->rchild=p;                 //建立前驱结点的后继线索
            pre->rtag=1;
        }
        pre=p;                             //标记当前结点成为刚刚访问过的结点
        InThread(p->rchild,pre);           //递归，线索化右子树
    }
}
 
void CreateInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){                           //非空二叉树，线索化
        InThread(T,pre);                   //线索化二叉树
        pre->rchild=NULL;                  //处理遍历的最后一个结点
        pre->rtag=1;
    }
}

边界辨析：

CreateInThread 末尾那两行不能漏。 中序遍历的最后一个结点没有后继，InThread 的循环走不到它， 必须在主过程里单独把它的 rchild 置空、rtag 置 1。 这是线索化代码里最容易被扣分的两行，也是「最后一个结点的右线索指向谁」这类选择题的答案来源。

中序线索二叉树的遍历

中序线索二叉树的结点中隐含了线索二叉树的前驱和后继信息。在对其进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继，直至其后继为空。

在中序线索二叉树中找结点后继的规律是：若其右标志为「1」，则右链为线索，指示其后继；否则遍历右子树中第一个访问的结点（右子树中最左下的结点）为其后继。

ThreadNode *Firstnode(ThreadNode *p){
    while(p->ltag==0) p=p->lchild;    //最左下结点（不一定是叶结点）
    return p;
}
 
ThreadNode *Nextnode(ThreadNode *p){
    if(p->rtag==0) return Firstnode(p->rchild);  //右子树中最左下结点
    else return p->rchild;                       //若 rtag==1 则直接返回后继线索
}
 
void Inorder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p))
        visit(p);
}

注意 Firstnode 的注释：「最左下结点（不一定是叶结点）」——它可能有右孩子。

遍历时不需要栈，空间复杂度 。 这是线索二叉树相对普通二叉链表的实质收益。

带头结点的线索链表

为方便起见，可在二叉树的线索链表上也添加一个头结点：令其 lchild 域的指针指向二叉树的根结点，其 rchild 域的指针指向中序遍历时访问的最后一个结点；令二叉树中序序列中的第一个结点的 lchild 域指针和最后一个结点的 rchild 域指针均指向头结点。

这好比为二叉树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历。

先序线索与后序线索

建立先序线索二叉树和后序线索二叉树的代码与中序类似，只需变动线索化改造的代码段与调用线索化左右子树递归函数的位置。

教材以图 5.19(a)（先序序列 、后序序列 ）手工示范：依次判断每个结点的左右链域，若为空，则将其改造为线索。

在先序线索二叉树中找结点的后继：

情况后继
有左孩子左孩子就是其后继
无左孩子但有右孩子右孩子就是其后继
是叶结点右链域直接指示了结点的后继

层次辨析：

三种线索树里，中序线索树是唯一「找前驱和后继都不需要回溯到父结点」的。 先序线索树找前驱、后序线索树找后继，都可能需要知道双亲——而二叉链表里没有双亲指针。 所以考试只让你在中序线索树上真正做遍历，先序/后序线索树只考「某个空链域指向谁」。 这解释了为什么教材把 Firstnode/Nextnode 这套算法只给了中序版本。

手算模板

给一棵二叉树，画出它的中序线索树：

  1. 先写出中序序列。
  2. 逐个结点看：左链空 → 指向序列里它的前一个；右链空 → 指向序列里它的后一个，并把对应 tag 置 1。
  3. 序列的第一个结点左链指空（或指头结点），最后一个结点右链指空（或指头结点）。
  4. 数一下线索条数，应当等于原来的空链域数 （无头结点时首尾两个是空）。

先序 / 后序线索树同理，只是第 1 步换成写先序 / 后序序列。

边界

说法判断说明
「线索二叉树中每个结点都有 2 个线索」❌只有空链域才变线索；全树共 个
「 个结点的二叉链表有 个空链域」❌ 个
「ltag=1 表示有左孩子」❌反了。ltag=0 才是左孩子，1 是前驱线索
「线索化就是加指针，不用遍历」❌线索化的实质就是遍历一次二叉树
「CreateInThread 只要调 InThread 就够了」❌还要单独处理最后一个结点的右线索
「Firstnode 返回的是最左下的叶结点」❌教材注释明说「不一定是叶结点」，它可能有右孩子
「中序线索树遍历需要栈」❌不需要，空间
「先序线索树找前驱很方便」❌可能需要双亲信息，二叉链表里没有
「加了头结点线索数会变」⚠️线索指向变了（首尾指向头结点），条数不变
「线索二叉树是一种新的树结构」❌是同一棵二叉树 + 一种存储结构上的改造

口径差异：

线索二叉树在工程和算竞里基本绝迹——内存不再紧张，需要有序遍历直接用迭代器或显式栈。 所以这一节是纯考试内容，没有任何可迁移的直觉，只能按教材的定义死抠： tag 的 0/1 含义、pre 指针的作用、最后一个结点的特殊处理、Firstnode 不一定是叶结点。 好消息是它的考法非常固定：画线索树、判断某个空链域指向谁、tag 值是多少。

对照速查

域值含义
ltag0lchild 指向左孩子
1lchild 指向前驱
rtag0rchild 指向右孩子
1rchild 指向后继
量值
二叉链表空链域数
线索条数（无头结点时首尾各差一个）
中序线索树遍历空间
线索树找后继找前驱
中序rtag=1 取线索；否则右子树最左下ltag=1 取线索；否则左子树最右下
先序有左孩子取左孩子；否则取右孩子；叶结点取线索可能需要双亲
后序可能需要双亲有右孩子取右孩子；否则取左孩子

考点

  • 个空链域的推导（用 ）。
  • 线索二叉树的定义（2010 命题追踪）与 tag 的 0/1 含义。
  • 中序线索二叉树中线索的指向（2014 命题追踪）。
  • pre 指针的作用与最后一个结点的特殊处理。
  • Firstnode 是最左下结点，不一定是叶结点。
  • 中序线索树遍历无须栈，空间 。
  • 先序线索树找后继的三种情况。

链接

反向链接