---
What is it?
Attempt_1
要找到指定节点p在中序遍历序列中的前驱：
再次遍历，设置两个工作指针pre和q分别指向前一个访问的结点和当前访问的结点
直到q指向指定结点p，此时pre即为前驱
Attempt_2
n个结点的二叉树拥有（n+1）个空链域，利用这些空链域来提供线索，即形成了线索二叉树
存储结构
显然，只有具有空链域的结点可以在 O(1) 时间内根据线索找到结果
三种线索二叉树
线索化
中序线索化
实际上在中序遍历中上图绿框的检查是不必要的，因为中序遍历下最后一个结点的右孩子必定为空，所以处理到最后一个结点时可以直接将 rtag置为1
按照类似的思路，我们来看看先序线索化：
先序线索化
注意！！！：在构建前后继关系时，能依靠的只有两个工作指针 pre和 q，即只能通过这两个指针来确定已知的前后继关系（pre是 q的前继，q是 pre的后继）
因此，需要关注线索的读写顺序，例如在先序遍历中，由于 visit 发生在递归左子树之前，如果 visit 将本来为null的q的左孩子修改为了指向pre的线索，就会形成死循环
为何只会在先序遍历中出现上述“转圈现象”呢？从下面的访问次序就可以看出
中序：左 根 右
后序：左 右 根
先序：根 左 右 只有在先序中对根的操作先于左孩子，相当于发生了读后写冲突（本来期望在读到左孩子为null后再对根线索化）
解决方法如下：在递归线索化左子树之前先判断左孩子是否已经是线索（ ltag == 0 ？）：
后序线索化
这里就要注意对最后一个结点的处理，因为后序遍历下最后访问的结点是可能有右孩子的
小结
=== 后序注意尾结点判断，先序注意死循环 ===