摘要

一、定义和数据结构

1. 定义

  结点结构中含有线索的的二叉树称为线索二叉树。
  若结点有左子树,则其lchild域指示其左子,否则令lchild域指示其前驱;若结点有右子树,则其rchild域指示其右子,否则令rchild域指示其后继。
  为了避免混淆,需要增加两个标志域LTag和RTag,标志域为0表示结点后接指针,标志位为1表示结点后接线索。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。

2. 数据结构

typedef struct BiThrNode
{
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    PointerTag LTag, RTag;
} BiThrNode, *BiThrTree;

  其中,PointerTag的定义为

typedef enum PointerTag
{
    Link,
    Thread
} PointerTag;

  Link == 0 表示指针,Thread == 1表示线索。

二、线索化

  线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索,而前驱或后继的信息只能在遍历时得到,所以线索化的过程即为在遍历过程中修改空指针的过程。所以为了记录遍历过程中访问结点的先后关系,附设一个指针pre始终指向刚刚访问过的结点,即若指针p指向当前访问的结点,则pre指向它的刚访问过的结点。

void InThreading(BiThrTree p, BiThrTree *pre)
{
    if (p)
    {
        // 左子树线索化.
        InThreading(p->lchild, pre);

        // 前驱线索.
        // 若当前结点无左子,则修改标志域并使得 lchild 指向 p 的前驱.
        if (!(p->lchild))
        {
            p->LTag = Thread;
            p->lchild = (*pre);
        }

        // 后继线索.
        if (!((*pre)->rchild))
        {
            (*pre)->RTag = Thread;

            // 将前驱结点的后继结点设置为当前结点.
            (*pre)->rchild = p;
        }

        // 更新 pre, 使其始终指向刚访问过的结点.
        (*pre) = p;

        // 右子树线索化.
        InThreading(p->rchild ,pre);
    }

    return;
} // InThreading

  我这里在学习的时候遇到一个问题:刚访问过的结点pre的后继线索设置失败。书中的伪代码未说明pre是否为全局变量,而数据结构中也没有存储pre,所以我先将pre作为一个局部变量定义并值传递给了InThreading,乍一看没什么问题,但是仔细debug之后发现,在调用这个递归形式的算法时,系统会维护一个函数调用栈,每进入一层新的递归,系统就会保存当前调用的返回地址,并压入新的调用的返回地址。在执行完子函数后,子函数的返回地址会被弹出栈,此时,之前做的一切修改就都不见了,pre也不会得到更新。

  改进方法有两个:
    1. 将pre设置为全局变量;
    2. 将值传递改为指针传递。

  本文采用了第二种方法。

三、遍历

  线索化之后,可以很方便地得到结点在遍历所得线性序列中的前驱和后继,也可以很方便地得到线性序列。

Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType e))
{
    // p 指向根结点.
    BiThrNode *p = T->lchild;

    // 空树或遍历结束时.
    while (p != T)
    {
        while (p->LTag != Thread)
        {
            p = p->lchild;
        }

        if (!Visit(p->data))
        {
            return ERROR;
        }

        // 访问后继结点.
        // 找到最左叶结点, 就可以轻松地访问其后继结点.
        while ((p->RTag == Thread) && (p->rchild != T))
        {
            p = p->rchild;
            Visit(p->data);
        }

        p = p->rchild;
    }

    return OK;
} // InOrderTraverse_Thr

参考文献

  1. 数据结构:C语言版/严蔚敏,吴伟民编著. ——北京:清华大学出版社,2007
  2. 线索二叉树详解 https://blog.csdn.net/s_999999/article/details/86157532
  3. 线索二叉树原理及前序、中序线索化(Java版)https://blog.csdn.net/UncleMing5371/article/details/54176252
  4. 关于函数调用栈(call stack)的个人理解 https://blog.csdn.net/VarusK/article/details/83031643

代码仓库

  1. https://github.com/tianshihao/data-structure/tree/master/chapter_6
扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄