|
线索二叉树概念 ．定义n个结点的二叉链表中含有n+个空指针域利用二叉链表中的空指针域存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为线索） 这种加上了线索的二叉链表称为线索链表相应的二叉树称为线索二叉树(Threaded BinaryTree)根据线索性质的不同线索二叉树可分为前序线索二叉树中序线索二叉树和后序线索二叉树三种 注意 线索链表解决了二叉链表找左右孩子困难的问题出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题 ．线索链表的结点结构 线索链表中的结点结构为 其中: ltag和rtag是增加的两个标志域用来区分结点的左右指针域是指向其左右孩子的指针还是指向其前趋或后继的线索 ．线索二叉树的表示 【例】下面(a)图所示的中序线索二叉树其线索链表如下面(b)图所示 注意 图中的实线表示指针虚线表示线索 结点C的左线索为空表示C是中序序列的开始结点无前趋 结点E的右线索为空表示E是中序序列的终端结点无后继 线索二叉树中一个结点是叶结点的充要条件为左右标志均是 二叉树的线索化 ．线索化和线索化实质将二叉树变为线索二叉树的过程称为线索化 按某种次序将二叉树线索化的实质是按该次序遍历二叉树在遍历过程中用线索取代空指针 具体过程可【参见动画演示】 ．二叉树的中序线索化 （）分析 算法与中序遍历算法类似只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索 该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL）而指针p指示当前正在访问的结点结点*pre是结点*p的前趋而*p是*pre的后继 （）将二叉树按中序线索化的算法 typedef enum { LinkThread} PointerTag //枚举值Link和Thread分别为 typedef struct node{ DataType data PointerTag ltagrtag //左右标志 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)?LinkThread //左指针非空时左标志为Link //(即)否则为Thread(即) p>rtag=(p>rchild)?LinkThread *(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) ．二叉树的前序线索化和后序线索化 前序线索化和后序线索化算法与二叉树的中序线索化类似具体可【参见参考书】 |
