#include
     
      using namespace std;enum PointerTag{                 THREAD,                 LINK};template
      
       struct BinaryTreeNodeThd{                BinaryTreeNodeThd( const T & x)                                :_data( x)                                ,_left( NULL)                                ,_right( NULL)                                ,_parent( NULL)                                ,_leftTag( LINK)                                ,_rightTag( LINK)                {}                 T _data;                 BinaryTreeNodeThd
       
        * _left;                 BinaryTreeNodeThd
        
         * _right;                 BinaryTreeNodeThd
         
          * _parent;                 PointerTag _leftTag;           //左孩子线索标志                 PointerTag _rightTag;          //右孩子线索标志};template
          
           struct BinaryTreeThd{public:                BinaryTreeThd< T>()                                :_root( NULL)                {}                BinaryTreeThd< T>(const T* a,size_t size)                {                                 size_t index=0;                                _root=_CreateTree( a,index,size );                }                 //中序线索化                 void InOrderThreading()                {                                 BinaryTreeNodeThd
           
            * prev=NULL;                                _InOrderThreading(_root,prev);                }                 //前序线索化                 void PreOrderThreading()                {                                 BinaryTreeNodeThd
            
             * prev=NULL;                                _PreOrderThreading(_root,prev);                }                 //后序线索化                 void PostOrderThreading()                {                                 BinaryTreeNodeThd
             
              * prev=NULL;                                _PostOrderThreading(_root,prev);                }                 //中序线索化的遍历                 void InOrderThd()                {                                 BinaryTreeNodeThd
              
               * cur=_root;                                 while(cur)                                {                                                 while(cur&&(cur->_leftTag!=THREAD ))   //找到最左节点                                                {                                                                cur=cur->_left;                                                }                                                cout<
               
                _data<< " ";    //输出最左节点                                                 while(cur->_rightTag!=LINK )   //找后继节点                                                {                                                                cur=cur->_right;                                                                cout<
                
                 _data<< " ";                                                }                                                cur=cur->_right;                                }                                cout<
                 
                  * cur=_root;                                 while(cur)                                {                                                 while(cur&&cur->_leftTag==LINK )                                                {                                                                cout<
                  
                   _data<< " ";                                                                cur=cur->_left;                                                }                                                cout<
                   
                    _data<< " ";                                                cur=cur->_right;                                }                                cout<
                    
                     _left==NULL &&_root->_right==NULL)    //只有一个节点的情况                                                cout<<_root->_data<
                     
                      
                       * cur=_root->_left;                                 BinaryTreeNodeThd
                       
                        * prev=NULL;                                 while(cur)                                {                                                 while(cur&&cur->_leftTag==LINK )                                                                cur=cur->_left;                                                 while(cur&&cur->_rightTag==THREAD )                                                {                                                                cout<
                        
                         _data<< " ";                                                                prev=cur;                                                                cur=cur->_right;                                                }                                                 if(cur==_root)                                                {                                                                cout<<_root->_data<< " ";                                                                 break;                                                }                                                 while(cur&&cur->_rightTag==LINK &&cur->_right==prev)                                                {                                                                cout<
                         
                          _data<< " ";                                                                prev=cur;                                                                cur=cur->_parent;                                                }                                                 if(cur&&cur->_rightTag==LINK )                                                                cur=cur->_right;                                }                                cout<
                          
                           
                            * _CreateTree(const T* a,size_t& index,size_t size)    //递归创建树                {                                 BinaryTreeNodeThd
                            
                             * root=NULL;                                 if((index 
                             
                              
                               (a[index]);                                                root->_left=_CreateTree( a,++index ,size);                                                 if(root->_left)                                                                root->_left->_parent=root;                                                root->_right=_CreateTree( a,++index ,size);                                                 if(root->_right)                                                                root->_right->_parent=root;                                }                                 return root;                }                 //中序线索化内部函数                 void _InOrderThreading(BinaryTreeNodeThd 
                               
                                * cur,BinaryTreeNodeThd 
                                
                                 *& 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 ;     //prev要动起来                                _InOrderThreading( cur->_right,prev );                }                 //前序线索化的内部函数                 void _PreOrderThreading(BinaryTreeNodeThd 
                                 
                                  * cur,BinaryTreeNodeThd 
                                  
                                   *& 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 ;      //prev要动起来                                 if(cur ->_leftTag==LINK)                                                _PreOrderThreading( cur->_left,prev );                                 if(cur ->_rightTag==LINK)                                                _PreOrderThreading( cur->_right,prev );                }                 //后序线索化的内部函数                 void _PostOrderThreading(BinaryTreeNodeThd 
                                   
                                    * cur,BinaryTreeNodeThd 
                                    
                                     *& prev)                {                                 if(cur ==NULL)                                                 return;                                _PostOrderThreading( cur->_left,prev );                                _PostOrderThreading( 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 ;    //prev要动起来                }protected:                 BinaryTreeNodeThd
                                     
                                      * _root;};void test(){                 int array1[10]={1,2,3,'#' ,'#',4,'#','#',5,6};                 //int array1[1]={1};                 BinaryTreeThd
                                      
                                        btt1(array1,10);                btt1.InOrderThreading();                btt1.InOrderThd();       //3 2 4 1 6 5                 /*btt1.PreOrderThreading();                btt1.PreOrderThd();    */     //1 2 3 4 5 6                 /*btt1.PostOrderThreading();                 btt1.PostOrderThd();  */       //3 4 2 6 5 1                 int array2[15]={1,2,'#' ,3,'#','#',4,5, '#',6,'#' ,7,'#','#',8};                 BinaryTreeThd
                                       
                                         btt2(array2,15);                btt2.InOrderThreading();                btt2.InOrderThd();      //2 3 1 5 6 7 4 8                 //btt2.PreOrderThreading();       //1 2 3 4 5 6 7 8                 //btt2.PreOrderThd();                 /*btt2.PostOrderThreading();                btt2.PostOrderThd();  */      //3 2 7 6 5 8 4 1}int main(){                test();                system( "pause");                 return 0;}