线索二叉树是一种什么结构？
线索二叉树是一种物理结构。用二叉表中空指针域，存放指向该结点在某种遍历次序下的前驱与后续节点的指针称为线索，这种加上了线索的二叉链表称为线索链表，相应的二叉树也称为线索二叉树，根据性质不同分别有前序、中序、后序等线索二叉树。线索化具体实现以中序二叉树的线索化为例，线索化的具体实现就是将中序二叉树的遍历进行修改，把原本打印函数的代码改为指针修改的代码就可以了。我们设置一个pre指针，永远指向遍历当前结点的前一个结点。若遍历的当前结点左指针域为空，也就是无左孩子，则把左孩子的指针指向pre（相对当前结点的前驱结点）。右孩子同样的，当pre的右孩子为空，则把pre右孩子的指针指向当前结点（相对pre结点为后继结点）。最后把当前结点赋给pre，完成后续的递归遍历线索化。
线索二叉树的意义是什么?
线索二叉树的意义是减少了的空指针域的同时又对每个节点增加了两个标志位。实际应用意义：当路由器使用CIDR，选择下一跳的时候，或者转发分组的时候，通常会用最长前缀匹配（最佳匹配）来得到路由表的一行数据，为了更加有效的查找最长前缀匹配，使用了一种层次的数据结构中，通常使用的数据结构为二叉线索。线索二叉树优势与不足：一、优势1、利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。2、任意一个结点都能直接找到它的前驱和后继结点。二、不足1、结点的插入和删除麻烦，且速度也较慢。2、线索子树不能共用。
线索二叉树
线索二叉树概念 ．定义 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
