线索二叉树及其存储结构

【线索链表】

对于二叉链表来说，在 $n$ 个结点的二叉树中，每个叶结点有 $2$ 个空指针，每个度为 $1$ 的结点有 $1$ 个空指针

假设叶结点的个数为 $n_0$，度为 $1$ 的结点个数为 $n_1$，度为 $2$ 的结点个数为 $n_2$

那么，对于二叉链表来说，共有 $2n_0+n_1$ 个空指针

而根据二叉树的性质，有：$n_0=n_2+1$

联立两式，可知二叉链表共有 $n_0+n_1+n_2+1 = n+1$ 个空指针

对于二叉链表来说，每个结点有一个数据域、一个左指针、一个右指针

typedef struct BiTNode {    //二叉链表
    int data;               //数据域
    struct BiTNode *lchild; //左指针
    struct BiTNode *rchild; //右指针
} BiTNode, *BiTree;

因此，在二叉链表上，只能知道每个结点的左右孩子的地址，无法知道某个结点在某种遍历序列下的前驱和后继

如果想要知道某个结点结点在某种序列遍历下的前驱或后继，要想知道，则必须从根结点开始遍历，而且以后每想知道都要遍历一次，这无疑浪费了时间

综合以上两个方面，可以考虑利用空地址，存放指向结点在某种遍历次序下的前驱与后继，将指向前驱与后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树

【存储结构】

在二叉链表的基础上将二叉链表中的空指针改为指向前驱或后继的线索，因此其存储结构相较于二叉链表有了更改：

• 若无左子树，令 lchild 指向其遍历序列的前驱结点
• 若无右子树，令 rchild 指向其遍历序列的后继结点
• 增设两个标志位 ltag、rtag，指示指针域是指向左右子树还是指向前驱后继结点

typedef struct ThNode {    //线索链表
    int data;              //数据域
    struct ThNode *lchild; //左指针
    struct ThNode *rchild; //右指针
    int ltag, rtag;        //标志位
} ThNode, *ThTree;
bool initThTree(ThTree &root) { //初始化
    root = NULL; //空树
    ltag = 0;    //建树时设为0
    rtag = 0;    //建树时设为0
    return true;
}