二叉树是一种非线性结构，遍历二叉树需要通过递归或者用栈辅助实现非递归的遍历。

用二叉树作为压缩存储结构时，取到一个结点，只能获取节点的左孩子和右孩子，不能直接得到结点的任一遍历序列的前驱或者后继。为了实现这种遍历，偶们利用二叉树中指向左右子树的空指针来存放结点的前驱和后继。

线索化二叉树思路：

当某一结点的左结点或结右点存在NULL时，则该结点的为空的子结点需要线索化。

在进行线索化时，结点的前驱指向前一个访问过的结点，故定义一个指针prev来保存前一个结点；结点的后继偶们并不知道，则对于未来的事情并不知道，偶们可以在未来对该结点的后继进行线索化，使prev的后继指向cur。

前序遍历二叉树------根->左->右（1,2,3,4,5,6）

template<classT>voidBinaryTreeThd<T>::PrevOrderThreading()//前序线索化二叉树{Node*prev=NULL;_PrevOrderThreading(_root,prev);}template<classT>voidBinaryTreeThd<T>::_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);}}

中序遍历二叉树------左->根->右（3,2,4,1,6,5）

递归实现：

template<classT>voidBinaryTreeThd<T>::InOrderThreading()//中序线索化二叉树{//递归实现中序线索化Node*prev=NULL;//线索化的前一个结点_InOrederThreading(_root,prev);}template<classT>voidBinaryTreeThd<T>::_InOrederThreading(Node*cur,Node*&prev)//中序线索化二叉树{if(cur==NULL){return;}_InOrederThreading(cur->_left,prev);//递归出cur->_left为空if(cur->_left==NULL){cur->_leftTag=THREAD;cur->_left=prev;//当前结点的前驱指向前一个结点}//对先前的结点后继进行线索化，在cur指向下一个结点即后继时，将先前节点的后继指向cur//到未来的结点进行先前结点后继的线索化if(prev&&prev->_right==NULL){cur->_rightTag=THREAD;prev->_right=cur;}prev=cur;_InOrederThreading(cur->_right,prev);//递归出cur->_right为空}

非递归实现（利用栈）：

template<classT>voidBinaryTreeThd<T>::InOrderThreading_NonR()//中序线索化二叉树--非递归{//栈实现中序线索化stack<Node*>s;Node*prev=NULL;Node*cur=_root;if(cur==NULL){return;}while(cur||!s.empty()){while(cur)//找到最左结点,入栈{s.push(cur);cur=cur->_left;}//cur不为空进栈，cur为空说明cur已经线索化了cur=s.top();//循环进入使cur为栈顶元素并判断是否需要线索化if(cur->_left==NULL){cur->_leftTag=THREAD;cur->_left=prev;}s.pop();//弹出栈顶元素，使栈顶保存需要线索化的cur的后继prev=cur;if(cur->_right==NULL&&!s.empty()){cur->_rightTag=THREAD;cur->_right=s.top();cur=NULL;//设置cur为空，防止死循环（2）}else{cur=cur->_right;//线索化跳到右子树进行}}}

后序遍历二叉树------左->右->根（3,4,2,6,5,1）

template<classT>voidBinaryTreeThd<T>::PastOrderThreading()//后序线索化二叉树{Node*prev=NULL;_PastOrderThreading(_root,prev);}template<classT>voidBinaryTreeThd<T>::_PastOrderThreading(Node*cur,Node*&prev)//后序线索化二叉树{if(cur==NULL){return;}_PastOrderThreading(cur->_left,prev);//最左结点_PastOrderThreading(cur->_right,prev);//最右结点if(cur->_left==NULL)//线索化前驱{cur->_leftTag=THREAD;cur->_left=prev;}if(prev&&prev->_right==NULL)//线索化后继{prev->_rightTag=THREAD;prev->_right=cur;}prev=cur;}