- 对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化
- 线索二叉树是一种物理结构
- 引入线索的目的是加快对二叉树的遍历
- n个节点的线索二叉树上含有线索数量为n+1个
- 线索二叉树就是利用二叉树的n+1个空指针来存放节点的前驱和后继信息的
- 后续线索二叉树不能有效解决求后续后继的问题，后续线索树的遍历仍需要栈的支持
ltag=0，表示指向节点的左孩子
rtag=0，表示指向节点的右孩子
ltag=1，则表示lchild为线索，指向节点的直接前驱
rtag=1，则表示rchild为线索，指向节点的直接后继
中序线索化的过程
- 对二叉树进行中序遍历
- 节点右子节点为空的指针域指向它的后继节点
- 节点左子节点为空的指针域指向它的前驱节点