后序线索二叉树的后序遍历

#include<stdio.h>
#include<malloc.h>
#include <iostream.h>
//线索三叉树
typedef enum PointerTag{Link,Thread}; 
typedef struct ThrNode
{
   int data;
   struct ThrNode *lchild;
   struct ThrNode *rchild;
   struct ThrNode *parent;
   PointerTag LTag,RTag;
   bool tag;
}thrnode;

thrnode* pre;
//构造三叉树
bool CreateThrTree(thrnode* &T,thrnode* p)
{   
	
	char ch;
	scanf("%c",&ch);
	if(ch=='m') 
	{
		T=NULL;
	}
	else
	{
		T=(thrnode*)malloc(sizeof(thrnode));
		T->data=ch;
		T->parent=p;
		T->LTag=Link;
		T->RTag=Link;
		T->tag=false;
		CreateThrTree(T->lchild,T);
		CreateThrTree(T->rchild,T);
	}

  return true;
}

//打印树
void PrintTree(thrnode* T)
{
  printf("%c",T->data);

}

// 建立线索
void InThreading(thrnode * p)
{
  if(p)
  {
     InThreading(p->lchild);
	 InThreading(p->rchild);
	 if(!p->lchild) 
	 {
	    p->lchild=pre;
	    p->LTag=Thread;
	 }
	 if(!pre->rchild)
	 {
	   pre->rchild=p;
	   pre->RTag=Thread;
	 }
    pre=p;
  }

}
//后序线索化
void PostOrderThreading(thrnode* &Thead)
{
   pre=Thead;
   InThreading(Thead->lchild);
   Thead->rchild=pre;
   Thead->RTag=Thread;
   if(!pre->rchild) 
   {
	   pre->rchild=Thead;
	   pre->RTag=Thread;
   }
  
}

//后序遍历
void PostOrderTraverse(thrnode* &T)
{
  thrnode *p=T->lchild; //p 指向根节点
  while(p!=T)
  {
	if(!p->lchild->tag && p->LTag==Link)
	{
	  while(p->LTag==Link) p=p->lchild;
    }
	if(!p->rchild->tag )
	{
    	if(p->RTag==Link) 
	  {
		  p=p->rchild; //带右子树
		 // cout<<(char)p->data;
	  }
	  else  //最左孩子无右子树 
	  {
		  PrintTree(p);
		  p->tag=true;
		//  cout<<(char)p->data;
		  while(p->RTag==Thread && p!=T)
		  {
		    p=p->rchild;
           if(p==T) break;  //节点是二叉树根，退出循环
		//	cout<<(char)p->data;
			PrintTree(p);
			p->tag=true;
            
		  }
		 if(p==T) break;  //节点是二叉树根，退出循环
	      p=p->parent;
		 
		  }//else...if
	}//endif
    
    if(p->LTag==Link && p->RTag==Link) //当前节点既有左孩子又有右孩子
		 {
	        if(p->lchild->tag && p->rchild->tag &&!p->tag) 
			{
		      PrintTree(p);
		      p->tag=true;
			  p=p->parent;
			}
			else if(!p->lchild->tag)
			{
			  p=p->lchild;
			}
			else
			{
			 p=p->rchild;
			
			}
		  }
		  else if(p->LTag==Link && p->RTag==Thread)//当前只有左孩子
		  {
			  if(p->lchild->tag)
			  {
		        PrintTree(p);
		     	p->tag=true;
				p=p->parent;
			  }
			  else
			  {
				  p=p->lchild;
			  
			  }
	
		  }
		  else if(p->RTag==Link && p->LTag==Thread) //当前只有右孩子
		  {
		    if(p->rchild->tag) 
			{
				PrintTree(p);
		    	p->tag=true;
				p=p->parent;
			     
			}
			else
			{
			  p=p->rchild;
			}
		  }
		 else
		  {
		    PrintTree(p);
			p->tag=true;
			p=p->rchild;
		  }
  }//end...while
  
}



//主函数
void main()
{
  thrnode *head=(thrnode*)malloc(sizeof(thrnode));
  head->data=0;
  head->parent=NULL;
  head->lchild=NULL;
  head->rchild=head;
  head->LTag=Link;
  head->RTag=Link;
  head->tag=false;
  if(CreateThrTree(head->lchild,head)) 
  {
	  PostOrderThreading(head);
	  PostOrderTraverse(head);
  }
}