节点：enumLinkType{THREAD,LINK};template<classT>structThredBinaryNode{ThredBinaryNode*_left;ThredBinaryNode*_right;LinkType_left_tag;LinkType_right_tag;T_data;ThredBinaryNode(Tdata):_data(data),_left(NULL),_right(NULL),_left_tag(LINK),_right_tag(LINK){};};线索化二叉树为：template<classT>classBinaryTreeThred{typedefThredBinaryNode<T>Node;public:BinaryTreeThred(constT*a,size_tsize,constT&valiue){size_tindex=0;_root=_CreatTree(a,size,index,valiue);}private:Node*_root;};构造函数：Node*_CreatTree(constT*a,size_tsize,size_t&index,constT&valiue){Node*root=NULL;if(index<size&&a[index]!=valiue){root=newNode(a[index]);root->_left=_CreatTree(a,size,++index,valiue);root->_right=_CreatTree(a,size,++index,valiue);}returnroot;}中序线索化递归：void_InThred(Node*cur,Node*&prev)//递归线索化{if(cur!=NULL){_InThred(cur->_left,prev);if(cur->_left==NULL){cur->_left_tag=THREAD;cur->_left=prev;}if(prev!=NULL&&prev->_right==NULL){prev->_right_tag=THREAD;prev->_right=cur;}prev=cur;_InThred(cur->_right,prev);}};中序线索非递归：voidInThred_Nor()//非递归{stack<Node*>s;Node*prev=NULL;Node*cur=_root;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;};Node*tmp=s.top();s.pop();if(tmp->_left==NULL){tmp->_left=prev;tmp->_left_tag=THREAD;}prev=tmp;if(prev->_right==NULL&&!s.empty()){tmp->_right=s.top();tmp->_right_tag=THREAD;}else{cur=tmp->_right;}}}前序线化非递归：voidBinaryTreeThred<T>::PreThread()//前序线索化非递归{Node*pre=NULL;Node*cur=_root;stack<Node*>s;s.push(cur);while(cur||!s.empty()){Node*tmp=NULL;if(!s.empty()){tmp=s.top();}else{return;}s.pop();if(tmp->_right){s.push(tmp->_right);}if(tmp->_left){s.push(tmp->_left);}else//tmp->left==null{tmp->_left_tag=THREAD;tmp->_left=pre;}if(pre!=NULL&&pre->_right==NULL){pre->_right_tag=THREAD;pre->_right=tmp;}pre=tmp;}}后序列线索话非递归：voidBinaryTreeThred<T>::PostThread()//后续{Node*cur=_root;stack<Node*>s;Node*prev=NULL;while(cur||!s.empty()){while(cur){s.push(cur);cur=cur->_left;//3}Node*tmp=s.top();if(tmp->_right==NULL||tmp->_right==prev){if(tmp->_left==NULL){tmp->_left_tag=THREAD;tmp->_left=prev;}if(prev!=NULL&&prev->_right==NULL){prev->_right_tag=THREAD;prev->_right=tmp;}s.pop();prev=tmp;}else{cur=tmp->_right;}}}