计算机考研专业课复习科目包括数据结构、操作系统、计算机组成原理、计算机网络四门课程。其中数据结构这一科目兼具理论与实践，要求同学们在复习过程中不仅要对教材的基本概念进行记忆，同时还要结合知识点掌握相应的实际操作知识。为帮助同学们在计算机专业课复习上卓有成效，中公考研将为同学们整理全面的考点梳理，今天为大家带来的是数据结构的相关内容，请同学们适当参考，结合自身实际在全面复习的基础上进行重点理解记忆。

　　线索化分成前序线索化、中序线索化、后序线索化，他们的区别在于每个结点的前驱和后继的不同，各种不同的遍历得到不同的前驱和后继。如果考手画线索化二叉树，则三种都有可能，如果考算法描述，那么就只能考中序线索化二叉树了(其它两个的比较繁琐)。

　　LchildLtagdataRtagRchild

　　我们讨论建立中序线索二叉树。

　　算法思路：利用中序递归遍历算法，即：

　　1、线索化根的左子树 2、线索化当前结点 3、线索化根的右子树。

　　其中pre为外部指针(初值=NULL)，在算法运行中，pre为当前搜索结点的前驱指针。

　　算法描述：

　　typedef struct Bnode

　　{ int Ltag,Rtag; //左右特征位//

　　datatype data;

　　struct Bnode *Lchild,*Rchild ;

　　}BTnode , *BTptr;

　　总控函数:中序线索化二叉树另外加了一个结点(相当于循环链表的头结点)。

　　Status InorderTheaing(BinThrtree& Thrt,BiThrTree T)

　　{

　　if(!(Thr=(BinThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);

　　Thrt->LTag=Link;Thrt->RTag=Threak;

　　Thrt->rchild=Thrt;//相当于空的循环链表，先将尾指针指向头结点。

　　if(!T) Thrt->lchild=Thrt;//空树那么整个也是空的了，只有一个附加的头结点了

　　else

　　{

　　Thrt->lchild=T;

　　pre=Thrt;//因为pre始终是当前结点的前驱结点，那么初始值就应该是头结点

　　Inthreadbt(T);将整个树线索化

　　pre->RTag=Thread;//当整个树都线索化了那么，pre肯定指向最后一个结点了

　　pre->rchhild=Thrt;//所以pre的后继应该是头结点

　　}

　　return OK;

　　}

　　void Inthreadbt (BTptr T) //中序线索二叉树//

　　{

　　if (T)

　　{

　　Inthreadbt(T->Lchild);//线索化左子树//

　　visit(T); 改成 if(T->Lchild==NULL)

　　{

　　T->Ltag=Thread;

　　T->Lchild=pre;

　　}

　　if(pre ->rchild= =NULL)

　　{ pre->RTag=Thread;

　　pre->Rchild=T;

　　}

　　pre=T;

　　Inthreadbt(T->Rchild); //线索化右子树//

　　}

　　}