对应的中序线索二叉树存储结构如图所示：
注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G
root00--000EI11F1C10G1A00DH10B0111149
例2：【2000年计算机系考研题】给定如图所示
二叉树T，请画出与其对应的中序线索二叉树。
28NIL
2533NIL
4055600854解:因为中序遍历序列是：5540 25 60 2808 33 54
对应线索树应当按此规律连线，即在原二叉树中添加虚线。
50
线索二叉树的生成算法（算法6.6, 见教材P134）
目的：在依某种顺序遍历二叉树时修改空指针，添加前驱或后继。
注解：为方便添加结点的前驱或后继，需要设置两个指针：
p指针→当前结点之指针；pre指针→前驱结点之指针。
技巧：当结点p的左/右域为空时，只改写它的左域（装入前驱
pre），而其右域（后继）留给下一结点来填写。
或者说，当前结点的指针p应当送到前驱结点的空右域中。若p->lchild＝NULL,则{p->Ltag=1;p->lchild＝pre;}
//p的前驱结点指针pre存入左空域
若pre->rchild＝NULL, 则{pre->Rtag＝1;pre->rchild=p;}
//p存入其前驱结点pre的右空域
51
3. 线索二叉树的遍历
理论上，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空时结束。
但是，在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，R_child=右孩子地址指针，并非后继！需要通过一定运算才能找到它的后继。
以中序线索二叉树为例：
对叶子结点（RTag=1），直接后继指针就在其rchild域内；对其他结点（RTag=0），直接后继是其右子树最左下的结点；（因为中序遍历规则是LDR，先左再根再右）①
②
③
④⑤⑥⑦⑧⑨⑩……
52
