データ構造_ツリー_二叉木の手がかり化_C++実装

"head.h"

#include<iostream>
#define LINK 0//      ：  
#define THREAD 1//      ：  
using namespace std;
///////////////////////       
class BitNode
{
public:
    BitNode();
    char ch;
    BitNode *lchild,*rchild;
    int LTag,RTag;
};
///////////////////////           
BitNode::BitNode()
{
    lchild=rchild=NULL;
    LTag=RTag=LINK;
}
///////////////////////////////BiTree_Thread 
class BiTree_Thread
{
public:
    BiTree_Thread();
    void PreOrderCreatBiTree();
    void InOrderTraverse_Thread();
private:
    void ReMove();
    void InOrderThreading();
    void InThreading(BitNode *&);
    void Creat(BitNode *&);
    void ReMoveBiTree(BitNode *&);
    BitNode *root,*pre,*p,*start;
    char ch;
};
///////////////////////////////BiTree_Thread      
BiTree_Thread::BiTree_Thread()
{
    root=pre=p=start=NULL;
}
/////////////////////////////////////////           
void BiTree_Thread::PreOrderCreatBiTree()
{
    cout<<"PreOrderCreatBiTree Called !"<<endl<<endl;
    cout<<"Please Input The BiTree In PreOrder :"<<endl<<endl;
    ReMove();//      
    Creat(root);//    
    cin.clear();//  cin     
}
//////////////////////////////////////         
void BiTree_Thread::Creat(BitNode *&t)
{
    if(cin>>ch)
    {
        if(ch!='#')
        {
            t=new BitNode;//     
			t->ch=ch;
            Creat(t->lchild);//        
            Creat(t->rchild);//        
        }
        else
            t=NULL;
    }
}
/////////////////////////////////////////////////              
void BiTree_Thread::InOrderTraverse_Thread()
{
    cout<<"InOrderTraverse_Thread Called !"<<endl<<endl;
    if(root==NULL)//   
    {
        cout<<"BiTree Is Empty !"<<endl<<endl;
        PreOrderCreatBiTree();//       
    }
	if(start==NULL)//      
		InOrderThreading();//     
    p=start->lchild;//p  root  
    while(p!=start)//     
    {
        while(p->LTag==LINK)//           
        {
            p=p->lchild;//      
        }
        cout<<p->ch<<endl;//    
		while(p->RTag==THREAD&&p->rchild!=start)//           
        {
            p=p->rchild;//     
            cout<<p->ch<<endl;//   
        }
        p=p->rchild;//     
    }
}
//////////////////////////////////////        
void BiTree_Thread::InOrderThreading()
{
    start=new BitNode;//                      
    start->LTag=LINK;//       
    start->RTag=THREAD;//         
    start->rchild=start;//            
    if(root==NULL)//         
    {
        start->lchild=start;//     
    }
    else//  
    {
        start->lchild=root;//            
        pre=start;//   pre     
        InThreading(root);//         
        pre->RTag=THREAD;//            
        pre->rchild=start;
        start->rchild=pre;
    }
}
//////////////////////////////////////////         
void BiTree_Thread::InThreading(BitNode *&p)
{
    if(p)//     
    {
        InThreading(p->lchild);//       
        if(p->lchild==NULL)//  p        
        {
            p->LTag=THREAD;
            p->lchild=pre;
        }
        if(pre->rchild==NULL)//  pre        
        {
            pre->RTag=THREAD;
            pre->rchild=p;
        }
		pre=p;//pre  p
        InThreading(p->rchild);//       
    }
}
/////////////////////////////////////////         
void BiTree_Thread::ReMove()
{
    if(root!=NULL)//     
    {
        ReMoveBiTree(root);//     
        if(start!=NULL)//        
        {
            delete start;//  start  
			start=NULL;// start NULL
        }
		root=NULL;// root NULL
    }
}
////////////////////////////////////////////         
void BiTree_Thread::ReMoveBiTree(BitNode *&t)
{
	if(t!=NULL)//             
	{
		if(t->LTag!=THREAD)//            
			ReMoveBiTree(t->lchild);//        
		if(t->RTag!=THREAD)//            
			ReMoveBiTree(t->rchild);//        
		delete t;//    
	}
}

"main.cpp"

#include<iostream>
#include"head.h"
using namespace std;

int main()
{
    BiTree_Thread t;
    char choice;
    while(1)
    {
        cout<<"Your Choice , Please ?"<<endl<<endl
        <<"1 . PreOrderCreatBiTree"<<endl
        <<"2 . InOrderTraverse_Thread"<<endl
        <<"9 . Quit"<<endl<<endl;
        cin>>choice;
        switch(choice)
        {
            case '1':
                 t.PreOrderCreatBiTree();
                 break;
            case '2':
                 t.InOrderTraverse_Thread();
                 break;
            case '9':
                 return 0;
                 break;
            default:
                    cout<<"No Such Choice !"<<endl<<endl;
                    break;
        }
    }
    return 0;
}