易涛－0604012007－线索二叉树的运算.c

线索二叉的运算包括线索二叉树的建立

#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请继续选择:");		
	}
	}
}