1. 线索树填充空指针域规则
(1)若左指针域为空，左指针指向前驱
(2)若右指针域为空，右指针指向后继
2. 如何填充
遍历二叉树的时候，保存上一个结点。
void preOrder(tree t，tree pre)
{
if(t != NULL)
{
visit(t);
preOrder(t->lchild,t);
preOrder(t->rchild,t);
}
if(t->lchild == NULL)
t->lchild = pre;
if(pre->rchild == NULL)
pre->rchlid = t;
}
3. 遍历线索数的方式
(1) 中序线索树遍历
- rtag不为0，通过访问rchlid访问后继
- rtag为0，则先访问结点的右子树，然后不断指向左孩子，直到结点右子树的最左下孩子
(2) 双向线索链表实现中序线索二叉树
Paste_Image.png
建立过程：建立头结点，头结点lchild指向第一个结点，rchild指向中序遍历的最后访问结点；第一个访问结点的前驱指向头结点，最后访问的结点指向头结点
中序遍历：通过头结点lchild找到第一个结点，之后和中序线索二叉树遍历一样
倒中序遍历：通过头结点rchild找到最后一个访问的结点，如果结点ltag为0，说明lchild为前驱，直接访问。如果ltag不为0，则访问其左子树，最右下结点。（从结点的左结点开始，不断指向右结点，直到rtag为0）
(3) 先序线索树遍历
- 若ltag为0，则访问其左孩子
- 若ltag不为0，rtag为0，则访问其右孩子
- 若ltag = 0，rtag = 1，通过rchild访问其后继
(4) 后序线索树遍历
常规方法无法遍历，需要结点添加双亲域或者tag或者使用栈才能进行遍历。因此可以理解为，后序线索二叉树并没什么特别意义，因为遍历后序线索树和后序遍历二叉树并没有简便多少。
