트 리 - 단서 이 진 트 리 의 구축, 옮 겨 다 니 기 (앞 순서, 중간 순서, 뒤 순서)

코드 를 직접 올리다.
      

#include
#include
using namespace std;

#define OK 1
#define ERROR 0

typedef int Status;
typedef char TElemType;
/*
              
*/
typedef struct BiThrNode
{
	char data;//       
	int ltag, rtag;//      
	struct BiThrNode *lchild;//   
	struct BiThrNode *rchild;//   
}BiThrNode,*BiThrTree;
/*
             
*/
Status PrintElement(TElemType e)
{
	cout << e;
	return OK;
}


/*
  p   Thrt      ，        
*/
BiThrTree parent(BiThrTree &Thrt, BiThrTree &p)
{
	BiThrTree temp=Thrt->lchild;

	if (p==Thrt->lchild)//p     ，        
	{
		return Thrt;
	}
	if (temp->lchild == p)
	{
		return temp;//            
	}
	else
	{
		temp = temp->lchild;
		while (temp->lchild != p&&temp->rchild != p)
		{
			/*
			        ，    
			         ，   
			     ，    
			*/
			if (temp->rtag == 0)
			{
				temp = temp->rchild;
			}
			else
			{
				temp = temp->lchild;
			}
		}
		return temp;
	}
}



/*
           ，                 
*/
Status CreateBiThrTree(BiThrTree &T)
{
	char ch;
	cin >> ch;
	if (ch == '#')
		T = NULL;
	else
	{
		if (!(T = (BiThrNode *)malloc(sizeof(BiThrNode))))
			exit(OVERFLOW);

		T->data = ch;
		T->ltag = 0;
		T->rtag = 0;
		CreateBiThrTree(T->lchild);
		CreateBiThrTree(T->rchild);
	}
	return OK;
}

/*
    T     ，      lchild     
	         T      ，           Visit

*/
Status InOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e))
{
	BiThrTree p = T->lchild;
	while (p&&(p != T))
	{
		while (p->ltag == 0)
		{			
			p = p->lchild;
		}
		Visit(p->data);
		while (p->rtag == 1 && p->rchild != T)
		{
			p = p->rchild;
			Visit(p->data);
		}
		p = p->rchild;
	}
	return OK;
}
/*
               (      ）
*/
Status PreOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e))
{
	BiThrTree p = T;
	while (p)
	{
		while (p->ltag == 0)
		{
			Visit(p->data);
			p = p->lchild;
		}		
		Visit(p->data);
		p = p->rchild;
	}
	return OK;
}
/*
               
*/
Status PostOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e))
{
	BiThrTree p = T->lchild;
	BiThrTree pre = T;

	//p          
	while (p->ltag == 0||p->rtag==0)
	{
		while(p->ltag==0)
			p = p->lchild;
		if (p->rtag == 0)
			p = p->rchild;
	}
	while (p != T) 
	{
		Visit(p->data);
		pre = parent(T, p);//        

		if (T == pre)//     T，   p    ，   
		{
			p = T;
		}
		//  p       ，        ，      
		else if(p==pre->rchild||pre->rtag==1)
		{
			p = pre;
		}
		else
		{
			// p       ，                   
			while (pre->rtag == 0)
			{
				pre = pre->rchild;
				while (pre->ltag == 0)
				{
					pre = pre->lchild;
				}
			}
			p = pre;
		}
	}
	
		
	
	
	return OK;
}
/*
              
*/
void InThreading(BiThrTree p,BiThrTree &pre)
{
	if (p)
	{
		InThreading(p->lchild,pre);//      
		if (!p->lchild)
		{
			p->ltag = 1;
			p->lchild = pre;
		}
		if ((!pre->rchild)&&pre->rchild==NULL)
		{
			pre->rtag = 1;
			pre->rchild = p;
		}
		pre = p;
		InThreading(p->rchild, pre);//      
	}
}
/*
               
*/
void preThreading(BiThrTree p, BiThrTree &pre)
{
	if (p)
	{
		if (p->lchild == NULL)
		{
			p->lchild = pre;
			p->ltag = 1;
		}
		if (pre != NULL&&pre->rchild == NULL)
		{
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		if (p->ltag == 0)
			preThreading(p->lchild, pre);
		if (p->rtag == 0)
			preThreading(p->rchild, pre);
	}
}

/*
               
*/
void postThreading(BiThrTree p, BiThrTree &pre)
{
	if (p)
	{
	postThreading(p->lchild, pre);
	postThreading(p->rchild, pre);
	if (p->lchild==NULL)
	{
		p->lchild = pre;
		p->ltag = 1;
	}
	if (pre != NULL&&pre->rchild == NULL)
	{
		pre->rchild = p;
		pre->rtag = 1;
	}
	pre = p;
   }
}


/*
          T，        ，Thrt     
*/
Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{
	//     
	if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
		exit(OVERFLOW);
	Thrt->ltag = 0;
	Thrt->rtag = 1;

	Thrt->rchild = Thrt;//     
	BiThrTree pre;
	if (!T)
		Thrt->lchild = Thrt;//      ，     
	else
	{
		Thrt->lchild = T;
		pre = Thrt;
		InThreading(T,pre);//           
		pre->rchild = Thrt;//         
		pre->rtag = 1;
		Thrt->rchild = pre;
	}
	return OK;
}

/*
          ，      ，     
*/
Status PostOrderThreading(BiThrTree &Thrt, BiThrTree T)
{
	//     
	if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
		exit(OVERFLOW);
	Thrt->ltag = 0;
	Thrt->rtag = 1;

	Thrt->rchild = Thrt;//     
	BiThrTree pre;

	if (!T)
		Thrt->lchild = Thrt;//      ，     
	else
	{
		Thrt->lchild = T;
		pre = NULL;
		postThreading(T, pre);//           
		pre->rchild = Thrt;
		pre->rtag = 1;
		Thrt->rchild = pre;//         
	}
	return OK;
}



void main()
{
	
	BiThrTree T1, Thrt1;
	cout << "       ，                 ：
";
	CreateBiThrTree(T1);
	if (InOrderThreading(Thrt1, T1) == OK)
		cout << "           ！
";
	cout << "         ，   ：
";
	InOrderTraverse_Thr(Thrt1, PrintElement);
	cout << endl;

	BiThrTree T2;
	 
	cout << "       ，                 ：
";
	CreateBiThrTree(T2);
	BiThrTree test1 = T2;
	preThreading(T2, test1);
	cout << "         ，   ：
";
	PreOrderTraverse_Thr(T2, PrintElement);
	cout << endl;
	
	BiThrTree T3,Thrt3;
	cout << "       ，                 ：
";
	CreateBiThrTree(T3);
	if (PostOrderThreading(Thrt3, T3) == OK)
		cout << "            ！
";
	cout << "         ，   ：
";
	PostOrderTraverse_Thr(Thrt3, PrintElement);
	cout << endl;

	system("pause");
}