#include "stdio.h"
#include "malloc.h"
#include "windows.h"
#define maxsize 20                           //規定樹中結點的最大數目
typedef struct node{                         //定義數據結構
	int ltag,rtag;                           //表示child域指示該結點是否孩子  
	char data;                               //記錄結點的數據
	struct node *lchild,*rchild;             //記錄左右孩子的指針
}Bithptr;

 Bithptr *Q[maxsize];                         //建隊，保存已輸入的結點的地址
 Bithptr *CreatTree(){                        //建樹函數，返回根指針
	char ch;
	int front,rear;
	Bithptr *T,*s;
	T=NULL;
	front=1;rear=0;                          //置空二叉樹
	printf("***********************************\n"); 
        printf("*                                 *\n");
        printf("* 課程設計題目：線索二叉樹的運算。*\n");
        printf("*                                 *\n");
        printf("***********************************\n");                        
	printf("創建二叉樹，請依次輸入，@表示虛結點，以#結束\n");
	ch=getchar();                            //輸入第一個字符
	while(ch!='#')                           //判斷是否為結束字符
	{
		s=NULL;
		if(ch!='@')                          //判斷是否為虛結點
		{
			s=(Bithptr *)malloc(sizeof(Bithptr));
			s->data=ch;
			s->lchild=NULL;
			s->rchild=NULL;
			s->rtag=0;
			s->ltag=0;
		}
		rear++;             
		Q[rear]=s;                            //將結點地址加入隊列中
		if(rear==1)T=s;                       //輸入為第一個結點為根結點
		else 
		{
			if(s!=NULL&&Q[front]!=NULL)       //孩子和雙親結點均不是虛結點
				if(rear%2==0)
					 Q[front]->lchild=s;
			    else Q[front]->rchild=s;
			if(rear%2==1)front++;
		}
		ch=getchar();
	}
	return T;
}
void Inorder(Bithptr *T)                      //中序遍歷
{
	if(T)
	{
		if(T->ltag!=1)Inorder(T->lchild);
		printf("→%c",T->data);
		if(T->rtag!=1)Inorder(T->rchild);
	}
}


Bithptr *pre=NULL;
void  PreThread(Bithptr *root)                 //中序線索化算法，函數實現
{
	Bithptr *p;
	p=root;
    if(p){
	   	PreThread(p->lchild);//線索化左子樹              
		if(pre&&pre->rtag==1)pre->rchild=p;    //前驅結點后繼線索化
        if(p->lchild==NULL)                    
		{
			p->ltag=1;
			p->lchild=pre;
		}
		if(p->rchild==NULL)                   //后繼結點前驅線索化
			p->rtag=1;
		pre=p;
		PreThread(p->rchild);
	}
}
void PrintIndex(Bithptr *t)                       //輸出線索
{
	Bithptr *f;
	f=t;
	if(f)
	{
		if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)   printf("【%c】",f->data);                         //如果是第一個結點
		if(f->ltag==1&&f->lchild!=NULL)               printf("%c→【%c】",f->lchild->data,f->data);     //如果此結點有前驅就輸出前驅和此結點
			 if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)   printf("→%c",f->rchild->data);            //如果此結點有前驅也有后繼，就輸出后繼
		else if(f->rtag==1&&f->rchild!=NULL)          printf("【%c】→%c",f->data,f->rchild->data);//如果沒有前驅，就輸出此結點和后繼
		printf("\n");
		if(f->ltag!=1)PrintIndex(f->lchild);
		if(f->rtag!=1)PrintIndex(f->rchild);
	}
}		    
Bithptr *SearchChild(Bithptr *point,char findnode)            //查找孩子結點函數
{
       Bithptr *point1,*point2;
       if(point!=NULL)
       {
          if(point->data==findnode)   return point;
          else 
			  if(point->ltag!=1)  { point1=SearchChild(point->lchild,findnode); if(point1!=NULL)return point1;}        
              if(point->rtag!=1)  { point2=SearchChild(point->rchild,findnode); if(point2!=NULL)return point2;}                  
              return NULL;			  		  
       }
       else 
           return NULL;
} 
Bithptr *SearchPre(Bithptr *point,Bithptr *child)            //查找父親結點函數
{
       Bithptr *point1,*point2;
       if(point!=NULL)
       {
          if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child))   return point;//找到則返回
          else 
			  if(point->ltag!=1) 
			  {
				  point1=SearchPre(point->lchild,child);
				  if(point1!=NULL)
					  return point1;
			  }        
              if(point->rtag!=1) 
			  {
				  point2=SearchPre(point->rchild,child);
				  if(point2!=NULL)
					  return point2;
			  }                  
              return NULL;			  		  
       }
       else 
           return NULL;
}
void Insert(Bithptr *root)
{
	char ch;
	char c;
	Bithptr *p1,*child,*p2;
	printf("請輸入要插入的結點的信息:");
    scanf("%c",&c);
	scanf("%c",&c);
    p1=(Bithptr *)malloc(sizeof(Bithptr));        //插入的結點信息
	p1->data=c;
	p1->lchild=NULL;
	p1->rchild=NULL;
	p1->rtag=0;
	p1->ltag=0;
	printf("輸入查找的結點信息:");
    scanf("%c",&ch);
	scanf("%c",&ch);
	child=SearchChild(root,ch);                      //查孩子結點的地址
	if(child==NULL){
		printf("沒有找到結點\n");
		system("pause");
		return ;
	}
	else printf("發現結點%c\n",child->data);
	if(child->ltag==0)                     //當孩子結點有左孩子的時候
	{
		p2=child;
		child=child->lchild;
		while(child->rchild&&child->rtag==0)              //找到左子樹下，最右結點
			child=child->rchild;
		p1->rchild=child->rchild;         //后繼化 
		p1->rtag=1;
		child->rtag=0;
		child->rchild=p1;                 //連接		                   
		p1->lchild=child;                 //前驅化
		p1->ltag=1;
	} 
	else                              //當孩子結點沒有左孩子的時候
	{
		p1->lchild=child->lchild;    //前驅化
		child->ltag=0;
		p1->ltag=1;
		child->lchild=p1;
		p1->rchild=child;
		p1->rtag=1;
	}
	printf("\n\t插入結點操作已經完成，并同時完成了線索化的恢復\n");
}


Bithptr * DeleteNode(Bithptr *t)
{
	Bithptr *child,*pre,*s,*q;
	char ch;
	printf("輸入查找的結點信息:");
    ch=getchar();
	ch=getchar();
	child=SearchChild(t,ch);                                //查找該結點的孩子結點
	printf("發現結點:%c\n",child->data);
	printf("ltag=%d,rtag=%d\n",child->ltag,child->rtag);
	if(NULL==child)
	{
		printf("沒有找到結點:");
		return t;
	}
	if(child!=t)
	{
	pre=SearchPre(t,child);
	printf("發現結點:%c\n",pre->data);
	}
	else                                                                             //當是頭結點的時候
		if(child->ltag==1&&child->rtag==1)  //沒有左右孩子
			t=NULL;
		else if(t->ltag==1&&t->rtag!=1)     //有右孩子沒有左孩子
		{
			t=child->rchild;
			child->rchild->lchild=NULL;
			free(child);
			return t;
		}else 
			if(t->ltag!=1&&t->rtag==1)     //有左孩子沒有右孩子
			{
				t=child->lchild;
				child->lchild->rchild=NULL;
				free(child);
				return t;
			}else
				if(t->ltag!=1&&t->rtag!=1)  //有左孩子也有右孩子
				{
					t=child->lchild;
					s=child->lchild;
					while(s->rchild&&s->rtag!=1) //查找孩子左子樹的最右下結點
						s=s->rchild;
					q=child->rchild;
					while(q->lchild&&q->ltag!=1) //查找孩子右子樹的最左下結點
						q=q->lchild;
					s->rchild=child->rchild;     //連接
					s->rtag=0;
					q->lchild=s;
					free(child);
					return t;
				}
				
    if(child==pre->lchild||child==pre)                                              //是父親結點的左孩子
	{
		if(1==child->ltag&&1==child->rtag)//孩子結點無左右
		{
			pre->lchild=child->lchild;
			pre->ltag=1;
			if(child->lchild!=NULL)
				if(child->lchild->rtag==1)child->lchild->rchild=pre;
			free(child);
		}
		else  if(1!=child->ltag&&1==child->rtag)//孩子結點有左無右
		{
		   	pre->lchild=child->lchild;
		    s=child->lchild;
		    while(s->rchild)  //查找左子樹的最右下結點
			s=s->rchild;
		   	s->rchild=child->rchild;
			free(child);
		}
		else  if(1==child->ltag&&1!=child->rtag)//孩子結點有右無左
		{ 
			pre->lchild=child->rchild;
			s=child->rchild;
			while(s->lchild)
				s=s->lchild;
			s->lchild=child->lchild;
			if(child->lchild!=NULL)
			     if(child->lchild->rtag==1)child->lchild->rchild=pre;
			free(child);
		 }
	     else if(1!=child->ltag&&1!=child->rtag)//孩子結點左右都有
		 {
			pre->lchild=child->lchild;
			s=child->rchild;
			while(s->lchild&&s->ltag!=1)        //找到右子樹的最左下結點
				s=s->lchild;
			q=child->lchild;
			while(q->rchild&&q->rtag!=1)        //找到左子樹下最右下結點
				q=q->rchild;
			q->rchild=child->rchild;            //將孩子結點的右子樹接到左子樹下最右下結點
			q->rtag=0;
			s->lchild=q;
			free(child);
		 }
	}else {
    if(child==pre->rchild)                                                           //是父親結點的右孩子
	{
		if(1==child->ltag&&1==child->rtag)//孩子結點無左右
		{
			pre->rchild=child->rchild;
			pre->rtag=1;
			if(child->rchild!=NULL)
				if(child->rchild->ltag==1)child->rchild->lchild=pre;
			free(child);
		}
		else if(1!=child->ltag&&1==child->rtag)//孩子結點有左無右
		{
			pre->rchild=child->lchild;
			s=child->lchild;
			while(s->rchild)
				s=s->rchild;
			s->rchild=child->rchild;
			if(child->rchild!=NULL)
				if(child->rchild->ltag==1)child->rchild->lchild=pre;
			free(child);
		}
		else if(1==child->ltag&&1!=child->rtag)//孩子結點有右無左
		{ 
			pre->rchild=child->rchild;
			s=child->rchild;
			while(s->lchild)
				s=s->lchild;
			s->lchild=child->lchild;
			free(child);
		}
		else if(1!=child->ltag&&1!=child->rtag)  //孩子結點左右都有
		{
			pre->rchild=child->rchild;
			s=child->rchild;
			while(s->lchild&&s->ltag!=1)        //找到右子樹的最左下結點
				s=s->lchild;
			q=child->lchild;
			while(q->rchild&&q->rtag!=1)        //找到左子樹下最右下結點
				q=q->rchild;
			s->lchild=child->lchild;            //將孩子結點的左子樹接到右子樹下最左下結點
			s->ltag=0;
			q->rchild=s;
			free(child);
		}
	}
	}		
	printf("\n\t刪除結點操作已經完成，并同時完成了線索化的恢復\n");
	return t;
}

void main()
{

	Bithptr *T;	
	int i;
	T=CreatTree();
	printf("\n");
	i=1;
	while(i)
	{
    
	printf("\t1 中序輸出二叉樹\n");
	printf("\t2 進行二叉樹線索化\n");
	printf("\t3 進行插入操作\n");
	printf("\t4 進入刪除操作\n");
	printf("\t5 輸出線索二叉樹\n");
	printf("\t0 退出\n");
	printf("\t  請選擇:");
	scanf("%d",&i);
	printf("\n");
	switch(i)
	{
	case 1:Inorder(T);
		   printf("\n");
		   break;
	case 2:PreThread(T);
		   printf("\t已經實現二叉樹的線索化，(可選擇'5'察看線索)\n");
	       printf("\n");
		   break;
	case 3:Insert(T);printf("\n");break;
	case 4:T=DeleteNode(T);printf("\n");break;
	case 5:PrintIndex(T);break;
	case 0:exit(1);
	default:printf("error\n\t請繼續選擇:");		
	}
	}
}