二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。

#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{public:BinaryTreeThd(constT*array,size_tsize,constT&invalid){size_tindex=0;_root=_CreateTree(array,size,index,invalid);}~BinaryTreeThd(){_DestroyTree(_root);_root=NULL;}voidInOrderThreading(){BinaryTreeNodeThd<T>*prev=NULL;_InOrderThreading(_root,prev);}voidPreOrderThreading(){BinaryTreeNodeThd<T>*prev=NULL;_PreOrderThreading(_root,prev);}voidPostOrderThreading(){BinaryTreeNodeThd<T>*prev=NULL;_PostOrderThreading(_root,prev);}voidPreOrderThd(){BinaryTreeNodeThd<T>*cur=_root;while(cur){while(cur&&LINK==cur->_leftTag){cout<<cur->_data<<"";cur=cur->_left;}cout<<cur->_data<<"";cur=cur->_right;}cout<<endl;}voidInOrderThd(){BinaryTreeNodeThd<T>*cur=_root;while(cur){while(cur&&LINK==cur->_leftTag){cur=cur->_left;}cout<<cur->_data<<"";while(THREAD==cur->_rightTag){cur=cur->_right;cout<<cur->_data<<"";}cur=cur->_right;}cout<<endl;}protected:BinaryTreeNodeThd<T>*_CreateTree(constT*array,size_tsize,size_t&index,constT&invalid){BinaryTreeNodeThd<T>*root=NULL;if(index<size&&array[index]!=invalid){root=newBinaryTreeNodeThd<T>(array[index]);root->_left=_CreateTree(array,size,++index,invalid);root->_right=_CreateTree(array,size,++index,invalid);}returnroot;}void_DestroyTree(BinaryTreeNodeThd<T>*root){if(NULL==root)return;if(LINK==root->_leftTag)_DestroyTree(root->_left);if(LINK==root->_rightTag)_DestroyTree(root->_right);deleteroot;}void_PreOrderThreading(BinaryTreeNodeThd<T>*cur,BinaryTreeNodeThd<T>*&prev){if(NULL==cur)return;if(NULL==cur->_left){cur->_leftTag=THREAD;cur->_left=prev;}if(prev&&NULL==prev->_right){prev->_rightTag=THREAD;prev->_right=cur;}prev=cur;if(cur->_leftTag==LINK)_PreOrderThreading(cur->_left,prev);if(cur->_rightTag==LINK)_PreOrderThreading(cur->_right,prev);}void_InOrderThreading(BinaryTreeNodeThd<T>*cur,BinaryTreeNodeThd<T>*&prev){if(NULL==cur)return;_InOrderThreading(cur->_left,prev);if(NULL==cur->_left){cur->_leftTag=THREAD;cur->_left=prev;}if(prev&&NULL==prev->_right){prev->_rightTag=THREAD;prev->_right=cur;}prev=cur;_InOrderThreading(cur->_right,prev);}void_PostOrderThreading(BinaryTreeNodeThd<T>*cur,BinaryTreeNodeThd<T>*&prev){if(NULL==cur)return;_PostOrderThreading(cur->_left,prev);_PostOrderThreading(cur->_right,prev);if(cur->_left==NULL){cur->_leftTag=THREAD;cur->_left=prev;}if(prev&&NULL==prev->_right){prev->_rightTag=THREAD;prev->_right=cur;}prev=cur;}protected:BinaryTreeNodeThd<T>*_root;};voidTest(){inta[]={1,2,3,'#','#',4,'#','#',5,6};BinaryTreeThd<int>t1(a,sizeof(a)/sizeof(a[0]),'#');t1.PreOrderThreading();t1.PreOrderThd();BinaryTreeThd<int>t2(a,sizeof(a)/sizeof(a[0]),'#');t2.InOrderThreading();t2.InOrderThd();inta1[]={1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};BinaryTreeThd<int>t3(a1,sizeof(a1)/sizeof(a1[0]),'#');t3.PreOrderThreading();t3.PreOrderThd();}intmain(){Test();return0;}