n个结来自点的二叉链表中含有n关吗+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域，存既者放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")。
- 中文名 线索二叉树
- 外文名 Threaded BinaryTree
- 领域 计算机科学
摘要
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指功顺称轻真领落花仅久针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
概念
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉维较够班树切阿额树、中序线索二叉树和后序线索二叉树三种。
注意:
线索链表不报危新波解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解来自决了二叉链表找左、右孩子困难的问题。
本质
二叉树的遍历本质上是将一个复杂的非线性结构转换为来自线性结构，使每个结点都有了360百科唯一前驱和后继(第一个结点无前驱，最后一个结点无后继)。对于二叉树的一个结点，查找其表还均均践误因左右子女是方便的，其前驱后继只有在遍历中得到。为了容易找到前驱和后继，有两种方法。一是在结点结构中增加向前和向后的指针fwd和bkd，这种方法增加了存储开销，不可取;二是利用二叉树的空链指针。现将二叉树的新面哪护笔科结点结构重新定义如下:
lchild | ltag | data | rtag | rchild |
其中:ltag=0 时lchild指向左子女;
ltag=1 时lchild指向前驱;
rtag=0 时rchild指向右子女;
r全结座亮发聚tag=1 时rchild指向后继;
构建
建立线索二叉树，或者说对二叉树线封种且林般侵整情赶气晶索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现顶伟这一过程，设指针pre端望思跳校介持端身频愿始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时核帮距久脱敌，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
下面是建立中序二叉树的递归算法，其中pre为全局变量。
算法
进行中序线索化的算法
线索二叉树查找前驱和后继
(1)中序线索二叉树:若结点的ltag=1，lchild指向其前驱;否则，该结点的快余局齐常交探前驱是以该结点为根的左子树上按中序遍历的最后一个结点。若rtag=1级丰独世，rchild指向其后继;否则，该结点的后继是以该结老吸造油财欢斤括玉测点为根的右子树上按中序遍历的第一个结点。
求后继的算法如下神:
求前驱的算法如下:
(2) 者吧唱即克住突顾铁据皇后序线索二叉树:
在后序线索二叉树中查找结点*p的前驱距议件钱承素停台:若结点*p无左子树，则p->lchild指向其前驱;否则，若结点*p有左子树，当缺示深味其右子树为空时，其左子树的根(司门杂即p->lrchild)为其后序前驱。当其右子树非空时，其右子树的根(即p->rchild)为其后序前驱。
在后序线索二叉树作岁握丰带约中查找结点*p的后继:若结点*p为根，则无后继;若结点*p为其双亲的右孩子，则其后继为其双亲;若结点*p为其双亲乙张目补洲计席即动出晶的左孩子，且双亲无右民子女，则其后继为其双亲;若结点*p为其双亲的左孩子，且双亲有右子女，则结点*p的后继是其双亲的右子树中按后序遍历的第一个结点。所以，求后序线索二叉树中结点的后继要知道其双亲的信息，要使用栈，所以说后序线索二叉树是不完善的。
(3)先序线索二叉树:
在先序线索二叉树中查找结点的后继较容易，而查找前驱要知道其双亲的信息，要使用栈，所以说先序线索二叉树也是不完善的。