二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。

而线索二叉树利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息

结点信息如下

enumPointerTag{THREAD,LINK};template<classT>structBinaryTreeNodeThd{T_data;//数据BinaryTreeNodeThd<T>*_left;//左孩子BinaryTreeNodeThd<T>*_right;//右孩子PointerTag_leftTag;//左孩子线索标志PointerTag_rightTag;//右孩子线索标志};

其前序结构如下

其中序结构如下

程序实现：

#include<iostream>usingnamespacestd;enumPointerTag{THREAD,LINK};template<classT>structBinaryTreeNodeThd{T_data;//数据BinaryTreeNodeThd<T>*_left;//左孩子BinaryTreeNodeThd<T>*_right;//右孩子PointerTag_leftTag;//左孩子线索标志PointerTag_rightTag;//右孩子线索标志BinaryTreeNodeThd(constT&x):_data(x),_left(NULL),_right(NULL),_leftTag(LINK),_rightTag(LINK){}};template<classT>classBinaryTreeThd{typedefBinaryTreeNodeThd<T>Node;public:BinaryTreeThd():_root(NULL){}BinaryTreeThd(constT*a,size_tsize,constT&invalid){size_tindex=0;_root=_CreateTree(a,size,index,invalid);}voidInOrderThreading()//中序线索化{Node*prev=NULL;_InOrderThreading(_root,prev);}voidPrevOderThreading()//前序线索化{Node*prev=NULL;_PrevOderThreading(_root,prev);}voidInOrderThd()//中序遍历{_InOrderThd(_root);}voidPrevOrderThd()//前序遍历{_PrevOrderThd(_root);}protected:Node*_CreateTree(constT*a,size_tsize,size_t&index,constT&invalid){Node*_root=NULL;if(index<size&&a[index]!=invalid){_root=newNode(a[index]);_root->_left=_CreateTree(a,size,++index,invalid);_root->_right=_CreateTree(a,size,++index,invalid);}return_root;}void_PrevOderThreading(Node*root,Node*&prev)//前序线索化{if(root==NULL)return;if(root->_left==NULL){root->_leftTag=THREAD;root->_left=prev;}if(prev&&prev->_right==NULL){prev->_rightTag=THREAD;prev->_right=root;}prev=root;if(root->_leftTag==LINK)//递归{_PrevOderThreading(root->_left,prev);//线索化左子树}if(root->_rightTag==LINK){_PrevOderThreading(root->_right,prev);//线索化右子树}}void_PrevOrderThd(Node*root){Node*cur=root;while(cur){while(cur->_leftTag==LINK){cout<<cur->_data<<"";cur=cur->_left;}cout<<cur->_data<<"";cur=cur->_right;}}/*方法二void_PrevOrderThd(Node*root){Node*cur=root;while(cur){while(cur->_leftTag==LINK){cout<<cur->_data<<"";cur=cur->_left;}cout<<cur->_data<<"";while(cur->_rightTag==THREAD){cur=cur->_right;cout<<cur->_data<<"";}if(cur->_leftTag==LINK){cur=cur->_left;}else{cur=cur->_right;}}}*/void_InOrderThreading(Node*_root,Node*&prev)//中序线索化{if(_root==NULL){return;}if(_root->_leftTag==LINK)_InOrderThreading(_root->_left,prev);//线索化if(_root->_left==NULL)//左孩子为空{_root->_leftTag=THREAD;_root->_left=prev;}if(prev!=NULL&&prev->_right==NULL)//前驱的右孩子为空{prev->_rightTag=THREAD;prev->_right=_root;}prev=_root;if(_root->_rightTag==LINK)//线索化右孩子_InOrderThreading(_root->_right,prev);}void_InOrderThd(Node*_root)//中序遍历{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;}cout<<endl;}protected:Node*_root;};

测试

intmain(){inta1[10]={1,2,3,'#','#',4,'#','#',5,6};BinaryTreeThd<int>t1(a1,10,'#');cout<<endl<<"中序遍历：";t1.InOrderThreading();t1.InOrderThd();cout<<"前序遍历"<<endl;BinaryTreeThd<int>t2(a1,10,'#');t2.PrevOderThreading();t2.PrevOrderThd();getchar();return0;}