前序线索是什么

前序线索是首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。在遍历过程中用线索取代空指针。

前序遍历（VLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。按某种次序将二叉树线索化的实质是按该次序遍历二叉树，在遍历过程中用线索取代空指针。

分析：

算法根据二叉树遍历的方式而定。只需要将遍历算法中访问结点的 *** 作具体化为建立正在访问的结点与其非空中序前趋结点间线索。

该算法应附设一个指针pre始终指向刚刚访问过的结点（pre的初值应为NULL），而指针p指示当前正在访问的结点。结点pre是结点p的前趋，而p是pre的后继。

基本概念用五个标志域来存储结点的结构  以这种结点结构构成的二叉链表作为二叉树的存储结构叫做线索链表（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的后序后继是其双亲的右子树中第一个后序遍历到的结点 它是该子树中 最左下的叶结点

遍历线索二叉树

lishixinzhi/Article/program/sjjg/201311/23149

我觉得你主要是不清楚pre指向的是什么。
我的数据结构书是严蔚敏版的，书上是这么说的：pre始终指向刚刚访问过的结点，若指针root指向当前访问的结点，则pre指向它的前续。
说的有点抽象。其实主要就是要清楚何时改变pre的值，“pre始终指向刚刚访问过的结点”就是说访问完一个结点后，就改变pre的值。
具体的思路是这样：首先书上建立线索的代码是一个中序遍历过程，其访问顺序分三步：左子树->本身结点->右子树。其中访问左子树就是指调用函数inthread(root->lchild)。任何一次访问结点的 *** 作必然处在这三步中的第二步，因为第一步又可以分为三步。可见pre值的修改应该在第二步之后，且在第三步之前，即在inthread(root->rchild)之前。正如代码中一样。
另外要注意第一次调用inthread前要先给pre赋值。
1此代码中的root可能指向的是二叉树中的任意一结点，由于任意一结点可以看做一个子树的根节点，所以可以理解为root指向二叉树本身或其子树的根节点。
root->lchild=pre这个代码是说让当前结点的左子树指向当前结点的前驱(pre)，即建立一个前续索引。
2此代码主要是判断是否要给pre建立一个后续线索。那么建立后续线索的前提条件是要右结点为空，这就是if中的判断。
pre->rchild=root就是给pre建立一个后续索引。pre是root的前续，反过来root就是pre的后续。
3前续和后续结点的指向通过pre与root互为前续后续的关系实现的。以首结点为例的话比较特殊，因为如果root指向首结点，那么这就是第一次调用，在调用前要预先给pre赋值。

这个应该是先序线索或者后序线索，中序是可以在线索化的二叉树上双向遍历的
大部分先序线索化二叉树找先序前驱困难，所有的先序线索二叉树可以很方便地找到先序后继，这样往后遍历可以，往前不行
大部分后序线索化二叉树找后序后继困难，所有的后序线索二叉树可以很方便地找到后序前驱，这样往前可以，往后不行
不知道你的问题详细问的什么

/二叉树的二叉线索存储表示/
typedef enum PointerTag{Link,Thread};//Link==0:指针； Thread==1：线索
typedef struct CTNode{
int data;
struct CTNode firstchild;
struct CTNode nextsibling;
PointerTag LTag,RTag;
}CTNode,CTree;
CTree pre=NULL;
void InThreading(CTree p) /线索化/
{
if(p)
{
InThreading(p->firstchild);// 左子树线索化
if(!p->firstchild ) /前驱线索/
{
p->LTag =Thread;
p->firstchild =pre;
}
if(!pre->nextsibling ) /后继线索/
{
pre->RTag =Thread;
pre->nextsibling =p;
}
pre=p;//保持pre指向p
InThreading(p->nextsibling );//右子树线索化
}
}
CTree InOrderThreading(CTree Thrt,CTree ct)
{//中序遍历二叉树ct，并将其中序线索化，Thrt指向头结点
Thrt=(CTree)malloc(sizeof(CTNode));
if(!Thrt)exit(0);
Thrt->LTag =Link;//建立头结点
Thrt->RTag =Thread;
Thrt->nextsibling =Thrt;//右指针回指
if(!ct)
Thrt->firstchild =Thrt;
else
{
Thrt->firstchild =ct;
pre=Thrt;
InThreading(ct);//中序遍历进行中序遍历线索化
pre->nextsibling =Thrt;//最后一个结点线索化
pre->RTag =Thread;
(Thrt)->nextsibling =pre;
}
return Thrt;
}

int print(int e)
{//输出结点
printf("%3d",e);return 1;
}
/中序遍历线索化二叉树/
int InOrderTraverse(CTree ct,int(visit)(int e))/中序遍历线索化二叉树/
{//ct指向头结点，头结点的做指针firstchild指向根结点，中序遍历二叉树
CTree p;
p=ct->firstchild ;//p指向根结点
while(p!=ct)//空树或遍历结束时，p==ct
{
while(p->LTag ==Link)p=p->firstchild ;
if(!visit(p->data )) return 0; //打印
while(p->RTag ==Thread&&p->nextsibling !=ct)
{
p=p->nextsibling ;visit(p->data); //访问后继结点
}
p=p->nextsibling ;
}
return 1;
}

首先，不知道你理解线索化二次树的概念吗？
如果你理解，我下面的解释对你而言很简单：
你可以考虑有左孩子的分支结点，因为该节点左孩子指针存储左子树，所以无法存储前驱线索（左线索），那是否，可以通过该分支结点得到它的前驱结点呢？
答案是否定的！因为如果该分支结点是左子树，在前驱是它的双亲结点；如果是右子树，则前驱在它的左兄弟子树上。二叉树采用二次链表实现，没法访问一个结点的双亲结点，当然也不可能访问它的左兄弟。它只能访问自个的直系后裔结点。这是由于二叉树的二叉链表存储本身决定的。

后序：FDBGHECA

线索化：

画得不太好：后序线索化就是将后序序列中节点的前驱和后继关系用线标出来而已，途中的线都是双向的，除了指向F的线条，因为F没有前驱。

线索二叉树就是
使用的对象：树节点中没有使用的n-1个空指针（n个树节点，空指针永远都是n+1个，自己推下）。
运行的原则：某种深度遍历顺序——先序，中序，后序
过程：按照中序（当然也可以是其他的遍历）的前驱后继关系，若p的左子树为空，则左子树指向p的中序前驱，若p的右子树为空，则p的右子树节点指向p的后继，若是子树都有，就不用捣腾了。第一个节点的左子树为空（此节点一定是叶节点，而且没前驱，所以是空），最后一个节点的右子树也是空。
数据结构：在树节点的结构是（data，lchild，rchild）线索树的节点是（data，lchild，rchild，ltag，rtag），tag为1表示线索数的节点，为0标识树节点。
目的：方便找到树在某种遍历的条件下前驱和后继。不是用来遍历的哈
注意的点：只用中序线索树可以很完美的达到这个效果，前序线索树在计算前驱的时候会牵扯到自己的父节点，就要使用栈来找，这样和遍历查找没区别，同理，后序线索树找后继会比较麻烦。
话说，要点基本就这样了。
细节的点，比如说为什么n+1啊，为什么前序后序不完美啊，这些一边就考个知道，而且推理是很快的，所以呢，考试的话，就照着我说的这几个点就ok了，主要是要会画，还有就是中序查找的实现。
中序实现给你一个要点：
找前驱：向左找第一个rtag为1的就是它的前驱了。
因为在中序中，所有的内节点（非叶节点）的前驱和后继必然是一个叶节点。
要是记不住算法，记住这点临场写也够了，前提是老兄您在之前弄明白我的要点的意义。

---