前序线索化:

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;_PrevOrderThreading(cur->_left,prev);_PrevOrderThreading(cur->right,prev);}



前序遍历：

voidPrevOrderThd(){Node*cur=_root;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<<"";//}//if(cur->_leftTag==LINK)//{//cur=cur->_left;//}//else//{//cur=cur->_right;//}}}


中序线索化：

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);}



中序遍历：

voidInOrderThd(){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_PostOrderThreading(Node*root,Node*&prev){if(root==NULL){return;}_PostOrderThreading(root->_LChild,prev);_PostOrderThreading(root->_RChild,prev);if(root->_LChild==NULL){root->_LTag=THREAD;root->_LChild=prev;}if(prev->_RChild==NULL){prev->_RTag=THREAD;prev->_RChild=root;}prev=root;}



后序遍历：

采用三叉链或写一个查找根节点的方法