数据结构之线索二叉树

基本概念　　用五个标志域来存储结点的结构  　　以这种结点结构构成的二叉链表作为二叉树的存储结构叫做线索链表（Threaded Linked Lists） 　　线索 指向结点前驱和后继的指针 　　线索二叉树（Threaded Binary Tree） 加上线索的二叉树 　　线索化 对二叉树以某种次序遍历使其变为线索二叉树的过程 在结构示意图中 指针用实线表示 线索通常用虚线表示 　　线索二叉树的存储结构 二叉树按中序线索化的算法  线索二叉树上常用运算

　　查找某结点*p在指定次序下的前趋和后继结点 　　在中序线索二叉树中 查找指定结点*p的中序后继结点和中序前趋结点 　　1 若结点*p的左子树（或右子树）非空 则*p的中序前趋（或中序后继）是从*p的左孩子（或右孩子）开始往下查找 由于二叉链表中结点的链域是向下链接的 所以在非线索二叉树中亦同样容易找到*p的中序前趋（或中序后继） 　　2 若结点*p的左子树（或右子树）为空 则在中序线索二叉树中是通过*p的左线索（或右线索）直接找到*p的中序前趋（或中序后继） 但中序线索一般都是 向上 指向其祖先结点 而二叉链表中没有向上的链接 因此在这种情况下 对于非线索二叉树 仅从*p出发无法找到其中序前趋（或中序后继） 而必须从根结点开始中序遍历 才能找到*p的中序前趋（或中序后继）

　　在后序线索二叉树中 查找指定结点*p的后序前趋结点 　　1 若*p的左子树为空 同p >lchild是前趋线索 指示其后序前趋结点 　　2 若*p的左子树非空 则p >lchild不是前趋线索 当*p的右子树非空时 *p的右孩子必是其后序前趋

　　在后序线索二叉树中 查找指定结点*p的后序后继结点 　　1 若*p是根 则*p是该二叉树后序遍历过程中最后一个访问到的结点 　　2 若*p是其双亲的右孩子 则*p的后序后继结点就是其双亲结点 　　3 若*p是其双亲的左孩子 但*p无右兄弟时 *p的后序后继结点是其双亲结点 　　4 若*p是其双亲的左孩子 但*p有右兄弟 则*p的后序后继是其双亲的右子树中第一个后序遍历到的结点 它是该子树中 最左下的叶结点

遍历线索二叉树