当以二叉树作为存储结构时，只能找到节点的左右孩子信息，不能直接得到结点在任一序列中的前驱和后继信息，只有在遍历过程中才能得到这种信息。我们知道，在n个结点的二叉链表栈必定存在n+1个空链域，因此，可以利用这些空链域来存放这些结点信息。所以作如下规定：若结点右左子树，则其lchild域指向其左孩子，否则令lchild域指向其前驱；若结点有右子树，其rchild域指向其右孩子，否则指向其后继。以这种结构构成的二叉链表叫做线索链表。

前序线索化：

源代码：

#define_CRT_SECURE_NO_WARNINGS1#include<iostream>usingnamespacestd;enumPointerTag{THREAD,LINK,};template<classT>structBinaryTreeNodeThd{T_data;BinaryTreeNodeThd<T>*_left;BinaryTreeNodeThd<T>*_right;PointerTag_leftTag;PointerTag_rightTag;BinaryTreeNodeThd(constT&data)//线索化：利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息:_data(data),_left(NULL),_right(NULL),_leftTag(LINK),_rightTag(LINK){}};template<classT>classBinaryTreeThd{typedefBinaryTreeNodeThd<T>Node;private:Node*_root;public:BinaryTreeThd():_root(NULL){}BinaryTreeThd(constT*a,size_tsize,size_tindex,constT&invalid){_root=_CreateBinaryTreeThd(a,size,index,invalid);}//中序线索化voidInorderThreading(){Node*prev=NULL;_InorderThreading(_root,prev);}//先序线索化voidPrevtorderThreading(){Node*prev=NULL;_PrevorderThreading(_root,prev);}//中序线索化遍历void_InorderThd(){Node*cur=_root;while(cur){//访问最左边的叶子节点while(cur->_leftTag==LINK){cur=cur->_left;}cout<<cur->_data<<"";while(cur->_rightTag==THREAD){cur=cur->_right;cout<<cur->_data<<"";}//访问右子树cur=cur->_right;}}//先序线索化遍历二叉树void_Prevorderthd(){Node*cur=_root;if(cur==NULL){return;}while(cur){//输出左边的节点while(cur->_leftTag==LINK){cout<<cur->_data<<"";cur=cur->_left;}cout<<cur->_data<<"";//转移到右边的节点cur=cur->_right;/*while(cur->_rightTag==THREAD){cur=cur->_right;cout<<cur->_data<<"";}*/}}protected://Node*_CreateBinaryTreeThd(constT*a,size_tsize,size_t&index,constT&invalid){Node*root=NULL;if(index<size&&a[index]!=invalid){root=newNode(a[index]);root->_left=_CreateBinaryTreeThd(a,size,++index,invalid);root->_right=_CreateBinaryTreeThd(a,size,++index,invalid);}returnroot;}//中序线索化子树void_InorderThreading(Node*cur,Node*&prev){if(cur==NULL){return;}//递归遍历左子树_InorderThreading(cur->_left,prev);if(cur->_left==NULL){cur->_leftTag=THREAD;cur->_left=prev;}if(prev&&prev->_right==NULL){prev->_rightTag=THREAD;prev->_right=cur;}prev=cur;//递归遍历右子树_InorderThreading(cur->_right,prev);}//先序线索化子树void_PrevorderThreading(Node*cur,Node*&prev){if(cur==NULL)return;//置前线索化if(cur->_left==NULL){cur->_leftTag=THREAD;cur->_left=prev;}//置后线索化if(prev&&prev->_right==NULL){prev->_rightTag=THREAD;prev->_right=cur;}prev=cur;if(cur->_leftTag==LINK){_PrevorderThreading(cur->_left,prev);}if(cur->_rightTag==LINK){_PrevorderThreading(cur->_right,prev);}}};

测试代码：

voidtest(){inta1[10]={1,2,3,'#','#',4,'#','#',5,6};inta2[15]={1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};BinaryTreeThd<int>btt1(a1,10,0,'#');BinaryTreeThd<int>btt2(a2,15,0,'#');cout<<"中序线索化遍历二叉树：";btt1.InorderThreading();btt1._InorderThd();cout<<endl;btt2.InorderThreading();btt2._InorderThd();cout<<endl;cout<<"先序线索化遍历二叉树：";btt1.PrevtorderThreading();btt1._Prevorderthd();cout<<endl;btt2.PrevtorderThreading();btt2._Prevorderthd();cout<<endl;}