基本概念
用五个标志域来存储结点的结构
以这种结点结构构成的二叉链表作为二叉树的存储结构叫做线索链表（Threaded Linked Lists）
线索指向结点前驱和后继的指针
线索二叉树（Threaded Binary Tree）加上线索的二叉树
线索化对二叉树以某种次序遍历使其变为线索二叉树的过程
在结构示意图中指针用实线表示线索通常用虚线表示
线索二叉树的存储结构
二叉树按中序线索化的算法
线索二叉树上常用运算
查找某结点*p在指定次序下的前趋和后继结点
在中序线索二叉树中查找指定结点*p的中序后继结点和中序前趋结点
１若结点*p的左子树（或右子树）非空则*p的中序前趋（或中序后继）是从*p的左孩子（或右孩子）开始往下查找由于二叉链表中结点的链域是向下链接的所以在非线索二叉树中亦同样容易找到*p的中序前趋（或中序后继）
２若结点*p的左子树（或右子树）为空则在中序线索二叉树中是通过*p的左线索（或右线索）直接找到*p的中序前趋（或中序后继）但中序线索一般都是向上指向其祖先结点而二叉链表中没有向上的链接因此在这种情况下对于非线索二叉树仅从*p出发无法找到其中序前趋（或中序后继）而必须从根结点开始中序遍历才能找到*p的中序前趋（或中序后继）
在后序线索二叉树中查找指定结点*p的后序前趋结点
１若*p的左子树为空同p>lchild是前趋线索指示其后序前趋结点
２若*p的左子树非空则p>lchild不是前趋线索当*p的右子树非空时*p的右孩子必是其后序前趋
在后序线索二叉树中查找指定结点*p的后序后继结点
１若*p是根则*p是该二叉树后序遍历过程中最后一个访问到的结点
２若*p是其双亲的右孩子则*p的后序后继结点就是其双亲结点
３若*p是其双亲的左孩子但*p无右兄弟时*p的后序后继结点是其双亲结点
４若*p是其双亲的左孩子但*p有右兄弟则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点它是该子树中最左下的叶结点
遍历线索二叉树
遍历某种次序的线索二叉树只要从该次序下的开始结点出发反复找到结点在该次序下的后继直至终端结点
