定义
typedef struct BiThrNode
{
TelemType data;
struct BitThrNode *lchild,*rchild;
int lRag,rtag;
}BiThrNode,*BiThrTree;
- 以上述结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树就是线索二叉树
| 变量 |
value=0 |
value=1 |
| lTag |
lchild域指示结点的左孩子 |
lchild域知识结点的前驱 |
| rTag |
rchild域指示结点的右孩子 |
rchild域指示结点的后继 |
- 结点前驱： 遍历左子树时最后访问的结点。（比如中序线索二叉树，将二叉树中序遍历，此结点的上一个被访问结点就是它的前驱）
- 结点后继： 遍历右子树时访问的第一个结点。
将结点为p的子树中序线索化
BiThrTree pre;
void InThreading(BiThrTree p) {
if (p) {
InThreading(p->lchild); //讲左子树进行线索化
{
if (!p->lchild) { //如果左子树为空
p->lRag = 1; //p加上左线索
p->lchild = pre;//p的左孩子的指针指向前驱
} else {
p->lRag = 0; //p的左子树不为空
}
if (!pre->rchild) { //pre 结点加右线索
pre->rtag = 1;
pre->rchild = p; //pre 有孩子指向后继
} else {
p->rtag = 0;
}
pre = p; //保持pre指向p的前驱，反之后继
InThreading(p->rchild); //讲右子树进行线索化
}
}
}
