全部答案

2018-04-25 01:15:21

•   #include 
  #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("建立一棵二叉树，请输入结点信息:
  ");
   printf("请输入新的结点信息，@为空结点，#为结束标志:");
   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  ;
   }getchar();
   printf("请输入新的结点信息，@为空结点，#为结束标志:");
   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("
  ");
   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("没有找到结点
  ");
   system("pause");
   return ;
   }
   else printf("发现结点%c
  ",child->data);
   if(child->ltag==0) //当孩子结点有左孩子的时候
   {
   p2=child;
   child=child->lchild;
   while(child->rchild&&child->rtag==0) //找到左子树下，最右结点
   child=child->rchild;
   printf("发现结点%c
  ",child->data);
   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("	插入结点操作已经完成，并同时完成了线索化的恢复
  ");
  }。

  全部
  

  小***

  2018-04-25 01:15:21

  18 13 评论

  分享
  提交评论