二叉树的线索化

6.4 线索化二叉树从前面的讨论可知，遍历二叉树就是将非线性结构的二叉树线性化，即按一定规则将二叉树中的结点排列成一个线性序列依次访问。

如图6.20(a)所示的二叉树，经中序遍历得到线性序列：BADEC，经前序遍历得到线性序列：ABCDE，经后序遍历得到线性序列：BEDCA。

在这些线性序列中，二叉树中的每个结点（除第一个和最后一个外）有且仅有唯一的一个前趋和唯一的一个后继，很容易找到各个结点的直接前驱和直接后继。

但当以二叉链表作为二叉树的存储结构时，只能找到结点的左、右孩子，而不能直接找到前驱和后继，只有在遍历的动态过程中得到这些信息。

如果将这些信息在第一次遍历时保存起来，在需要再次对二叉树进行“遍历”时就可以将二叉树视为线性结构进行访问，从而简化遍历操作。

那么，如何存储遍历中得到的结点前驱和后继的信息呢？一个简单的办法是在每个结点上增加两个指针域fwd和bkwd，分别指向存储遍历中得到的结点前驱和后继。

fwd L child data R child bkwd这是采用多重链表来表示二叉树。

这种方法虽简单易行，但这种结构的存储密度将大大降低，浪费存储空间。

另一种方法，是利用原有链域L child 和R child的空链域。

在n个结点的二叉链表中有2n个孩子链域，其中仅有n-1个链域是用来指示结点的左右孩子，而另外n+1个链域是空链域。

现在把这些空链域利用起来，使其指向结点的前驱或后继；对那些原来就不为空的链域，则仍然指向左或右孩子。

如果把指向前驱和后继的指针称为线索（Thread），那么，如何区分指向左、右孩子的指针和指向前驱、后继的线索呢？在原结点结构上增加标志域定义为：0 Lchild为左指针，指向左孩子0 Rchild为右指针，指向右孩子ltag＝rtag＝1 Lchild为左线索，指向前驱 1 Rchild为右线索，指向后继以这种结点构成的二叉链表作为二叉树的存储结构，叫做线索链表，其C语言类型说明如下：Typedef struct ThreadTNode{enum{0，1} ltag, rtag;Elem Type data;Struct ThreadTNode *Lchild, *Rchild;}ThreadTNode, *ThreadTree;为了节省内存空间，我们用C语言的位段方法将结点中的左标志域和右标志域与数据域合并在一个存储单元中（即各用一位表示左标志和右标志，其余各位表示结点值）。

实验八线索二叉树的创建和遍历1.实验目的（1）掌握二叉树的线索链表存储结构。

（2）能够实现二叉树的线索链表的创建、遍历等基本操作。

2.实验内容编程实现二叉树的线索链表存储表示的基本操作，包括线索二叉树的创建与遍历。

3.实验要求（1）根据实验内容编写程序，上机调试并获得运行结果（2）撰写实验报告4.准备工作本次实验将会构造此二叉树，并会对此二叉树进行遍历5.关键步骤与算法(1)构造线索二叉树算法步骤；若某节点的左孩子节点指针域（lchild）为空，就可以利用它来指出该节点在某种遍历序列中的直接前驱的存储地址；若某节点的右孩子指针域（rchild）为空，就可以利用它来指出该节点在某种遍历序列中的直接后继的存储地址。

那些非空的指针域仍存放指向该节点左、右孩子节点的指针域。

这样，就得到了一棵线索二叉树。

算法如下；1.//按先序遍历序列输入树中各节点的值，构造线索二叉树2.BiThrTree* CreateBiThrTree()3.{4. BiThrTree *s;5. DataType ch;6. scanf("%c",&ch);7.8.if(ch == '#')9. exit(0);10.if(ch == '@')11. s = NULL;12.else if (ch=='\n')13. getchar();14.15.else16. {17. s = (BiThrTree *)malloc(sizeof(BiThrTree));18.if(!s)19. exit(ERROR);20. s->data = ch;21. s->lflag = 0;22. s->rflag = 0;23. s->lchild = CreateBiThrTree();24. s->rchild = CreateBiThrTree();25. }26.return s;27.}(2) 将二叉树中序线索化现将树递归到左子树然后再判断这个树的左右子树是否为空，如果为空则把它们的标志设为1，代表线索，首先设一个current代表前驱结点，然后判断它是否为空，如果为空则进行下一次递归，如果不为空，则判断左标志和右标志如果左标志为线索，则让前驱节点的右孩子指向当前节点，如果右标志为1，则让当前节点的左孩子指向前驱结点算法如下；1.void InThreading(BiThrTree *t)2.{3.if(t != NULL)//先判断树为不为空，如果为空，则不执行函数4. {5. InThreading(t->lchild);//递归调用左子树进行线索化6.if(t->lchild == NULL)7. t->lflag = 1;8.if(t->rchild == NULL)9. t->rflag = 1;10.//以上两步是判断这个结点的左右结点是否为空，若为空，把他们对应的flag标上111.if(current != NULL)//因为要用到current所以要判断一下，且current只有当t回到倒数第二个结点时，才会不为NULL12. {13.if(current->rflag == 1)14. current->rchild = t;//前驱结点的右孩子指针指向当前节点t15.if(t->lflag == 1)16. t->lchild = current;//现结点t的左孩子指针指向前驱结点17. }18. current = t;//让前驱结点为t为下一次执行函数做准备19. InThreading(t->rchild);//递归调用右子树进行线索化20. }21.}6．源代码1.#include<malloc.h>2.#include<stdio.h>3.#include<stdlib.h>4.#include<io.h>5.#define ERROR -16.7.typedef char DataType;8.typedef struct BiThrNode//二叉树的二叉链表的存储结构9.{10. DataType data;11.struct BiThrNode *lchild,*rchild;12.int lflag,rflag;//左右标志，值为0表示指针，值为1表示线索13.}BiThrTree;14.BiThrTree *current = NULL;15.//检查if的==16.//按先序遍历序列输入树中各节点的值，构造线索二叉树17.BiThrTree* CreateBiThrTree()18.{19. BiThrTree *s;20. DataType ch;21. scanf("%c",&ch);22.23.if(ch == '#')24. exit(0);25.if(ch == '@')26. s = NULL;27.else if (ch=='\n')28. getchar();29.30.else31. {32. s = (BiThrTree *)malloc(sizeof(BiThrTree));33.if(!s)34. exit(ERROR);35. s->data = ch;36. s->lflag = 0;37. s->rflag = 0;38. s->lchild = CreateBiThrTree();39. s->rchild = CreateBiThrTree();40. }41.return s;42.}43.//将二叉树前序线索化（递归）44.void PreThreading(BiThrTree *t)45.{46.if(t != NULL)//先判断树为不为空，如果为空，则不执行函数47. {48.if(t->lchild == NULL)49. t->lflag = 1;50.if(t->rchild == NULL)51. t->rflag = 1;52.//以上两步是判断这个结点的左右结点是否为空，若为空，把他们对应的flag标上153.if(current != NULL)//因为要用到current所以要判断一下，且current只有当t回到倒数第二个结点时，才会不为NULL54. {55.if(current->rflag == 1)56. current->rchild = t;//前驱结点的右孩子指针指向当前节点t57.if(t->lflag == 1)58. t->lchild = current;//现结点t的左孩子指针指向前驱结点59. }60. current = t;//让前驱结点为t为下一次执行函数做准备61.if(t->lflag == 0)62. PreThreading(t->lchild);//递归调用右子树进行线索化63.if(t->rflag == 0)64. PreThreading(t->rchild);65. }66.}67.//遍历前序线索二叉树68.void PreVisitThrtree(BiThrTree *t)69.{70.while(t != NULL)//大循环71. {72.while(t->lflag == 0)73. {74. printf("%c\t",t->data);75. t = t->lchild;76. }77. printf("%c\t",t->data);78. t = t->rchild;79. }80.}81.82.//检查if的==83.//将二叉树中序线索化（递归）84.void InThreading(BiThrTree *t)85.{86.if(t != NULL)//先判断树为不为空，如果为空，则不执行函数87. {88. InThreading(t->lchild);//递归调用左子树进行线索化89.if(t->lchild == NULL)90. t->lflag = 1;91.if(t->rchild == NULL)92. t->rflag = 1;93.//以上两步是判断这个结点的左右结点是否为空，若为空，把他们对应的flag标上194.if(current != NULL)//因为要用到current所以要判断一下，且current只有当t回到倒数第二个结点时，才会不为NULL95. {96.if(current->rflag == 1)97. current->rchild = t;//前驱结点的右孩子指针指向当前节点t98.if(t->lflag == 1)99. t->lchild = current;//现结点t的左孩子指针指向前驱结点100. }101. current = t;//让前驱结点为t为下一次执行函数做准备102. InThreading(t->rchild);//递归调用右子树进行线索化103. }104.}105.//检查if的==106.//遍历中序线索二叉树107.void InVisitThrtree(BiThrTree *t)108.{109.while(t != NULL)//大循环110. {111.while(t->lflag == 0)//小循环1;此循环第一次进行时首先要去找到最左节点112. t = t->lchild;113.if(t == NULL)114. exit(ERROR);115. printf("%c\t",t->data);116.while(t->rflag == 1 && t->rchild != NULL)//小循环2117. {118. t = t->rchild;119. printf("%c\t",t->data);120. }121. t = t->rchild;122./*123.两种情况：124. 1.如果t的右子树为空则t直接指向t的中序后继结点.125. 2.如果t的右子树不为空，即t->rflag为0，那么退出这个小循环2回到大循环中，再到小循环1中去找t的右子树的最左下的结点.126. */127. }128.}129.130.//将二叉树后序线索化（递归）131.void PostThreading(BiThrTree *t)132.{133.if(t != NULL)//先判断树为不为空，如果为空，则不执行函数134. {135. PreThreading(t->lchild);136. PreThreading(t->rchild);137.if(t->lchild == NULL)138. t->lflag = 1;139.if(t->rchild == NULL)140. t->rflag = 1;141.//以上两步是判断这个结点的左右结点是否为空，若为空，把他们对应的flag标上1142.if(current != NULL)//因为要用到current所以要判断一下，且current只有当t回到倒数第二个结点时，才会不为NULL143. {144.if(current->rflag == 1)145. current->rchild = t;//前驱结点的右孩子指针指向当前节点t146.if(t->lflag == 1)147. t->lchild = current;//现结点t的左孩子指针指向前驱结点148. }149. current = t;//让前驱结点为t为下一次执行函数做准备150. }151.}152.//遍历后序线索二叉树153.void PostVisitThrtree(BiThrTree *t)154.{155.if(t)156. {157.while(t->lchild != NULL && t->lflag == 0)158. {159. t = t->lchild;//先遍历到最左边的节点160. }161. }162.}163.//主函数164.void main()165.{166. BiThrTree *t,*s;167. printf("\t\t请按先序序列输入二叉树(如：ABC@@DE@G@@F@@@#)\n\t\t");168. t = CreateBiThrTree();169. InThreading(t);170. printf("\t\t按中序遍历输出线索二叉树：\n\t\t");171. InVisitThrtree(t);172. printf("\n");173.//getchar();174.//getchar();175. fflush(stdin);//这个操作必须要进行，或者是进行上面注释的那两步操作，要不然176. printf("\t\t请按先序序列输入二叉树(如：ABC@@DE@G@@F@@@#)\n\t\t");177. s = CreateBiThrTree();178. PreThreading(s);179. printf("\t\t按前序遍历输出线索二叉树：\n\t\t");180. PreVisitThrtree(s);181.}7.测试图8.实验总结然对于这一节，主要是讨论线索二叉树的建立以及遍历，对于二叉树的建立，主要有五个部分构成，分别是data，lchild，rchild，lflag，rflag，而它与二叉树不同的地方就是多了lflag和rflag的判断，当当前节点的左节点为空时一定会指向它的前驱结点，当前驱节点的右节点为空时，让前驱结点的右指针域指向当前节点，这就是线索化，而对于前序中序后序的线索化本质都是一样的。

6·4 线索二叉树1、线索二叉树的结点结构二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构，使每个结点都有了唯一前驱和后继（第一个结点无前驱，最后一个结点无后继）。

对于二叉树的一个结点，查找其左右子女是方便的，其前驱后继只有在遍历中得到。

为了容易找到前驱和后继，有两种方法。

一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取；二是利用二叉树的空链指针。

现将二叉树的结点结构重新定义如下：其中：ltag=0 时ltag=1 时lchild指向前驱；rtag=0 时rchild指向左子女；rtag=1 时rchild指向后继；以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，指向前驱和后继的指针叫线索，加上线索的二叉树叫线索二叉树，对二叉树进行某种形式遍历使其变为线索二叉树的过程叫线索化。

学习线索化时，有三点必须注意：一是何种“序”的线索化，是先序、中序还是后序；二是要“前驱”线索化、“后继”线索化还是“全”线索化（前驱后继都要）；三是只有空指针处才能加线索。

2、对二叉树进行中序线索化的算法bithptr *pre; /* 全程变量*/void INTHREAD(bithptr *p){if(p!=NULL){ INTHREAD(p->lchild); /* 左子树线索化*/if(p->lchild==NULL) { p->ltag=1;p->lchild=pre;}if(p->rchild==NULL) p->rtag=1;if(pre!=NULL && pre->rtag==1) pre->rchild=p;pre=p; /* 前驱指向当前结点*/INTHREAD(p->rchild); /* 右子树线索化*/}3、在线索二叉树上查找前驱和后继（1）中序线索二叉树：若结点的ltag=1，lchild指向其前驱；否则，该结点的前驱是以该结点为根的左子树上按中序遍历的最后一个结点。

简述二叉树的五种形态二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点。

根据节点的分布情况，二叉树可以分为五种形态，分别是满二叉树、完全二叉树、平衡二叉树、搜索二叉树和线索二叉树。

一、满二叉树满二叉树是指除了叶子节点外，每个节点都有两个子节点的二叉树。

也就是说，满二叉树的所有层都是满的，并且最后一层的叶子节点都靠左排列。

满二叉树的节点数可以通过公式计算得到，假设树的高度为h，则节点数为2^h - 1。

满二叉树的特点是结构简单，查找速度快。

在满二叉树中，任意两个节点的路径长度都相同。

二、完全二叉树完全二叉树是指除了最后一层之外，其他层都是满的，并且最后一层的叶子节点都靠左排列的二叉树。

完全二叉树的特点是节点数较少，结构相对简单。

完全二叉树通常用数组来表示，因为它的节点之间的关系可以通过数组的下标来表示。

在完全二叉树中，任意一个节点的左子节点的下标为2i，右子节点的下标为2i+1。

三、平衡二叉树平衡二叉树是指左右子树的高度差不超过1的二叉树。

平衡二叉树的特点是查找、插入和删除的时间复杂度都为O(logn)，其中n是节点的数量。

平衡二叉树的高度可以通过节点的平衡因子来计算，平衡因子定义为左子树的高度减去右子树的高度。

平衡因子的取值范围为-1、0和1，当平衡因子的绝对值大于1时，需要通过旋转操作来调整树的平衡性。

四、搜索二叉树搜索二叉树，也称为二叉搜索树或排序二叉树，是一种特殊的二叉树。

它的特点是对于树中的任意一个节点，其左子树中的所有节点都小于它，右子树中的所有节点都大于它。

搜索二叉树的中序遍历结果是一个递增的有序序列。

搜索二叉树的特点是可以快速地查找某个节点，时间复杂度为O(logn)，其中n是节点的数量。

但是，如果搜索二叉树不平衡，即左子树或右子树过深，则会导致查找的时间复杂度退化为O(n)。

五、线索二叉树线索二叉树是对二叉树进行了优化的数据结构，它通过添加指向前驱和后继节点的线索，使得遍历操作更加高效。

线索化⼆叉树详解线索化⼆叉树详解说明1. 线索化⼆叉树，由字⾯意思，就是将⼆叉树的节点拿线索连接起来2. 实质上，也就是将⼆叉树的叶⼦节点左右指针域彼此连接⼀个节点3. ⼆叉树的⾮叶⼦节点的左右指针域都各⾃连接了⼀个节点，但是叶⼦节点的左右指针域是空的，因此考虑将叶⼦节点的左右指针域按照某种遍历次序连接起来4. 按照⼆叉树的遍历⽅式，有前序中序后续三种遍历⽅式，因此可以形成三种链式结构5. 每个叶⼦节点前⼀个节点称为前驱节点，后⼀个节点称为后继节点，如果当前节点没有前驱或者后继节点，则直接置为空6. 以中序线索化⼆叉树为例，编写中序线索化⼆叉树的⽅法7. 先判断当前节点是否为空，如果为空，则直接返回8. 否则先向左递归线索化⼆叉树的左⼦树9. 然后再线索化当前节点，定义属性pre保存当前节点的前⼀个节点，因此当前节点的前⼀个节点置为pre10. 注意当前节点的后⼀个节点，需要⽤pre保存当前节点，然后遍历到后⼀个节点，然后⽤pre指向11. 注意第⼀个节点和最后⼀个节点12. 中序线索化如下，前序和后续类似源码及分析节点类//创建节点class HeroNode{//编号private int no;//姓名private String name;//左⼦树private HeroNode left;//右⼦树private HeroNode right;//线索化的前驱节点类型，是节点还是树，假定 0 为树， 1 为节点private int leftType;//线索化的后继节点类型private int rightType;public int getLeftType() {return leftType;}public void setLeftType(int leftType) {this.leftType = leftType;}public int getRightType() {return rightType;}public void setRightType(int rightType) {this.rightType = rightType;}//构造器，左⼦树和右⼦树默认为空public HeroNode(int no, String name) {this.no = no; = name;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) { = name;}public HeroNode getLeft() {return left;}public void setLeft(HeroNode left) {this.left = left;}public HeroNode getRight() {return right;}public void setRight(HeroNode right) {this.right = right;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +'}';}//删除节点/**** @param no 要删除的节点编号*/public void delNode(int no){//判断当前节点的左⼦树是否为空，如果不为空，再判断是否为要删除的节点if (this.left != null && this.left.no == no){this.left = null;}//判断当前节点的右⼦树是否为空，如果不为空，再判断是否为要删除的节点if (this.right != null && this.right.no == no){this.right = null;}//否则向左向右递归if (this.left != null){this.left.delNode(no);}if (this.right != null){this.right.delNode(no);}}//前序中序后序遍历主要区别在于⽗节点的输出位置不同，/*** 前序遍历先输出⽗节点信息，然后判断左⼦树是否为空，如果不为空，则递归前序遍历 * 然后再判断右⼦树是否为空，如果不为空，则递归遍历前序遍历*///前序遍历public void preOrder(){//先输⼊当前节点信息System.out.println(this);//然后判断当前节点的左⼦树是否为空if (this.left != null){this.left.preOrder();}//再判断当前节点的右⼦树是否为空if (this.right != null){this.right.preOrder();}}//中序遍历public void infixOrder(){//先判断当前节点的左⼦树是否为空if (this.left != null){this.left.infixOrder();}//再输出当前节点的信息System.out.println(this);//然后再判断当前节点的右⼦树是否为空if (this.right != null){this.right.infixOrder();}}//后序遍历public void postOrder(){//先判断当前节点的左⼦树是否为空if (this.left != null){this.left.postOrder();}//再判断当前节点的右⼦树是否为空if (this.right != null){this.right.postOrder();}//最后输出当前节点的信息System.out.println(this);}//前序查找/*** 前序遍历查找* @param no 要查找的节点编号* @return 返回查找的结果*/public HeroNode preOrderSearch(int no){//先判断当前节点是不是要查找的节点if (this.no == no){return this;}//如果当前节点不是要查找的节点，则判断左⼦树是否为空，若不为空，则递归前序查找 HeroNode resNode = null;if (this.left != null){resNode = this.left.preOrderSearch(no);}//如果在左⼦树找到，则直接返回if (resNode != null){return resNode;}//如果左⼦树也没有找到，则判断右⼦树是否为空，并递归if (this.right != null){resNode = this.right.preOrderSearch(no);}return resNode;}//中序查找/*** 中序遍历查找* @param no 要查找的节点编号* @return 返回查找的结果*/public HeroNode infixOrderSearch(int no){//先判断当前节点左⼦树是否为空，如果不为空则递归中序查找//定义变量保存查找的结果HeroNode resNode = null;if (this.left != null){resNode = this.left.preOrderSearch(no);}//如果查找到，则直接返回if (resNode != null){return resNode;}//如果没有找到，判断当前节点是不是要查找的节点if (this.no == no){return this;}//如果还没有找到，则判断右⼦树是否为空，不为空则递归中序查找if (this.right != null){resNode = this.right.infixOrderSearch(no);}return resNode;}//后序查找/*** 后续遍历查找* @param no 要查找的节点编号* @return 返回查找的结果*/public HeroNode postOrderSearch(int no){//判断当前节点的左⼦树是否为空，如果不为空，则递归后续查找HeroNode resNode = null;if (this.left != null){resNode = this.left.postOrderSearch(no);}if (resNode != null){return resNode;}if (this.right != null){resNode = this.right.postOrderSearch(no);}if (resNode != null){return resNode;}if (this.no == no){return this;}return resNode;}}线索化⼆叉树类//创建⼀颗线索化⼆叉树class ThreaderBinaryTree{//⼆叉树必有根节点private HeroNode root;//定义变量指向前驱节点,默认为空private HeroNode pre = null;public void setRoot(HeroNode root) {this.root = root;}//编写中序线索化⼆叉树的⽅法/**** @param node node为当前要中序线索化的节点*/public void infixThreadedBinaryTree(HeroNode node){//先判断当前节点是否为空if (node == null){return;}//如果不为空，先线索化左⼦树infixThreadedBinaryTree(node.getLeft());//再线索化当前节点//当前节点的前驱节点为pre,后继节点需要在下⼀个节点连通，因为是单向的 //设置当前节点的前驱节点，并设置前驱节点类型if (node.getLeft() == null){node.setLeft(pre);node.setLeftType(1);}//设置当前节点的后继节点及其类型if (pre != null && pre.getRight() == null){pre.setRight(node);pre.setRightType(1);}//让pre指向当前节点pre = node;//最后再线索化右⼦树infixThreadedBinaryTree(node.getRight());}//重载线索化的⽅法public void infixThreadedBinaryTree(){this.infixThreadedBinaryTree(root);}//删除节点/**** @param no 要删除的节点编号*/public void delNode(int no){//先判断⼆叉树是否为空if (this.root != null){//再判断当前root节点是不是要删除的节点if (this.root.getNo() == no){root = null;}else {this.root.delNode(no);}}else {System.out.println("⼆叉树为空，不能删除...");}}//前序遍历public void preOrder(){if (this.root != null){this.root.preOrder();}else {System.out.println("⼆叉树为空...");}}//中序遍历public void infixOrder(){if (this.root != null){this.root.infixOrder();}else {System.out.println("⼆叉树为空...");}}//后续遍历public void postOrder(){if (this.root != null){this.root.postOrder();}else {System.out.println("⼆叉树为空...");}}//前序查找public HeroNode preOrderSearch(int no){if (this.root != null){return this.root.preOrderSearch(no);}else {return null;}}//中序查找public HeroNode infixOrderSearch(int no){if (this.root != null){return this.root.infixOrderSearch(no);}else {return null;}}//后续查找public HeroNode postOrderSearch(int no){if (this.root != null){return this.root.postOrderSearch(no);}else {return null;}}}测试类public static void main(String[] args) {ThreaderBinaryTree threaderBinaryTree = new ThreaderBinaryTree(); HeroNode root = new HeroNode(1,"tom");HeroNode node2 = new HeroNode(3,"jack");HeroNode node3 = new HeroNode(6,"smith");HeroNode node4 = new HeroNode(8,"king");HeroNode node5 = new HeroNode(10,"mary");HeroNode node6 = new HeroNode(14,"dop");root.setLeft(node2);root.setRight(node3);node2.setLeft(node4);node2.setRight(node5);node3.setLeft(node6);threaderBinaryTree.setRoot(root);//进⾏线索化threaderBinaryTree.infixThreadedBinaryTree();//测试线索化的结果System.out.println("node5的前⼀个节点 = " + node5.getLeft());System.out.println("node5的后⼀个节点 = " + node5.getRight());}。

线索二叉树：遍历二叉树：实际上是对二叉树（非线性结构）进行的线性化操作，即以一定规则将二叉树中的结点排列成一个线性序列（先序序列、中序序列和后序序列）。

举例：图6.9所示的二叉树中的结点，按中序遍历可得到中序序列：a+b*c-d-e/f，其中‘c’的前驱为‘*’，后继为‘-’。

当以二叉链表作为二叉树的存储结构时，只能找到结点的左右孩子信息，而不能直接得到结点在任一线性序列中的前驱和后继信息，因为这种信息只有在遍历的动态过程中才能得到。

如何保存这种在遍历过程中得到的结点的前驱和后继信息呢？方法一：在二叉链表的每个结点上增加两个指针域fwd和bkwd，分别指向在依任一次序遍历时得到的前驱和后继信息。

（大大影响存储密度）方法二：利用二叉链表中的空链域来存放结点的前驱和后继信息。

（在有n个结点的二叉链表中必定存在n+1个空链域！）（不影响存储密度）为此，可以将二叉链表中的结点结构作如下修改：lchild LTag data RTag rchild其中：Ltag = 0 lchild域指示结点的左孩子1 lchild域指示结点的前驱Rtag = 0 rchild域指示结点的右孩子1 rchild域指示结点的后继我们把如此修改后的二叉链表称为二叉树的线索链表，其中指向结点前驱和后继的指针称为线索。

相应地，把添加线索后的二叉树称为线索二叉树(Threaded Binary Tree)。

对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

举例：图6.11(a)所示为中序线索二叉树，与其对应的中序线索链表如图 6.11(b)所示。

其中实线为指针（指向左、右子树），虚线为线索（指向前驱和后继）。

在线索树上进行遍历，只要找到序列中的第一个结点，然后依次找结点的后继直到其后继为空时而停止。

关键是如何在线索树中找结点的后继？二叉树的二叉线索存储表示：（p133-134）线索二叉树的遍历：（以中序线索二叉树为例，即中序遍历二叉线索树）算法6.5二叉树的线索化：（以中序线索化为例，即通过中序遍历建立中序线索链表）算法6.6，算法6.7。