线索二叉树
线索二叉树概念
．定义 n个结点的二叉链表中含有n+ 个空指针域 利用二叉链表中的空指针域 存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为 线索 ） 这种加上了线索的二叉链表称为线索链表 相应的二叉树称为线索二叉树(Threaded BinaryTree) 根据线索性质的不同 线索二叉树可分为前序线索二叉树 中序线索二叉树和后序线索二叉树三种 注意 线索链表解决了二叉链表找左 右孩子困难的问题 出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题
．线索链表的结点结构 线索链表中的结点结构为
其中: ltag和rtag是增加的两个标志域 用来区分结点的左 右指针域是指向其左 右孩子的指针 还是指向其前趋或后继的线索
．线索二叉树的表示 【例】下面(a)图所示的中序线索二叉树 其线索链表如下面(b)图所示
注意 图中的实线表示指针 虚线表示线索 结点C的左线索为空 表示C是中序序列的开始结点 无前趋 结点E的右线索为空 表示E是中序序列的终端结点 无后继 线索二叉树中 一个结点是叶结点的充要条件为 左 右标志均是
二叉树的线索化 ．线索化和线索化实质 将二叉树变为线索二叉树的过程称为线索化 按某种次序将二叉树线索化的实质是 按该次序遍历二叉树 在遍历过程中用线索取代空指针 具体过程可【参见动画演示】
．二叉树的中序线索化 （ ）分析 算法与中序遍历算法类似 只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索 该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL） 而指针p指示当前正在访问的结点 结点*pre是结点*p的前趋 而*p是*pre的后继
（ ）将二叉树按中序线索化的算法 typedef enum { Link Thread} PointerTag //枚举值Link和Thread分别为 typedef struct node{ DataType data PointerTag ltag rtag //左右标志 Struct node *lchild *rchild } BinThrNode \\线索二叉树的结点类型 typedef BinThrNode *BinThrTree BinThrNode *pre=NULL //全局量 void lnorderThreading(BinThrTree p) {//将二叉树p中序线索化 if(p){ //p非空时 当前访问结点是*p InorderThreading(p >lchild) //左子树线索化 //以下直至右子树线索化之前相当于遍历算法中访问结点的操作 p >ltag=(p >lchild)?Link Thread //左指针非空时左标志为Link //(即 ) 否则为Thread(即 ) p >rtag=(p >rchild)?Link Thread *(pre){ //若*p的前趋*pre存在 if(pre >rtag==Thread) //若*p的前趋右标志为线索 pre >rchild=p //令*pre的右线索指向中序后继 if(p >ltag==Thread) //*p的左标志为线索 p >lchild=pre //令*p的左线索指向中序前趋 } // 完成处理*pre的线索 pre=p //令pre是下一访问结点的中序前趋 InorderThreeding(p >rehild) //右子树线索化 }//endif } //InorderThreading
（ ）算法分析 和中序遍历算法一样 递归过程中对每结点仅做一次访问 因此对于n个结点的二叉树 算法的时间复杂度亦为O(n)
lishixinzhi/Article/program/sjjg/201311/22726
