sy6_3.c

数据结构实验与学习指导

/* sy6_3.c */
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
#define MAXSIZE 20
typedef struct  ThreadNode {
    char cdata;
    struct ThreadNode *lchild,*rchild;
    unsigned Ltag,Rtag;
   }ThrNode;
ThrNode *bt,*p, *pre=NULL,*pre1; 
ThrNode *Create_BiTree2()
{   ThrNode *t;
    char c;
    c=getchar();
    if(c=='#')   return(NULL);
    else{
        t=(ThrNode *)malloc(sizeof(ThrNode));
        t->cdata=c;
        t->Ltag=t->Rtag=0;
        t->lchild=Create_BiTree2();
        t->rchild=Create_BiTree2();
        }
           return(t);
    }/* Create_BiTree2*/
void  InOrderThr(ThrNode *t)    /*中序线索二叉树t */
{  if ( t )
  { InOrderThr (t->lchild );    /*线索化左子树 */
     if (t ->lchild==NULL)
      {  t->Ltag=1;
         t->lchild=pre;
      }
  if (pre->rchild==NULL)    /*建立pre结点的后继线索*/
    {  pre->Rtag=1;
       pre->rchild=t;
    }
   pre=t;
   InOrderThr( t->rchild);   /*线索化右子树*/
 }
} /* InOrderThr */
void Crt_InOrderThr( ThrNode *t)
  { pre=NULL;
    InOrderThr(t);
    pre->Rtag=1;
  }/* Crt_InOrderThr */
ThrNode  Thr_search(ThrNode *t,char c)
{  /*在线索二叉树中查找等于c的结点*/
   p=t ;
   if(p!=NULL)
    { while(p->lchild!=NULL)
          p=p->lchild ;
      if(p->cdata==c)
        { printf("\n这是第一个结点!");
          p=NULL;
          return(*p);  /*中序序列第一个结点*/
        }
     while(p->rchild!=NULL)
      {
        if (p->Rtag==1)
             p=p->rchild;  /*右标志为1，则右指针域所指向的结点便是它的后继结点 */
       else
         { p=p->rchild;      /*右标志为0，表明该结点有右子树*/
           while(p->Ltag!=1)
           p=p->lchild;  /*应沿其右子树的左指针链向下查找某结点的左标志为1的结点*/
          }
     if(p->cdata==c)
        { printf("\n这个结点是:");
          printf("%c",p->cdata);
          return(*p);           }
        }/* while (p->rchild!=NULL) */
    } /*if*/
  }/* InVisitThr */
void InVisitThr(ThrNode *t)      /*中序遍历线索二叉树t*/
    {  p=t ;
       if(p!=NULL)
         { while(p->lchild!=NULL)
            p=p->lchild ;
            printf("%c",p->cdata);           /*中序序列第一个结点*/
            while(p->rchild!=NULL)
             {  if (p->Rtag==1)
                 p=p->rchild; /*右标志为1，则右指针域所指向的结点便是它的后继结点 */
               else
                 { p=p->rchild;  /*右标志为0，表明该结点有右子树*/
            while(p->Ltag!=1)
             p=p->lchild; /*应沿其右子树的左指针链向下查找某结点的左标志为1的结点*/
    }
    printf("%c",p->cdata);
   }/* while (p->rchild!=NULL) */
  } /*if*/
}/* InVisitThr */
ThrNode  InPreNode(ThrNode *bt,ThrNode  *p)
   {  /*在中序线索二叉树上寻找结点p的中序前驱结点*/
      ThrNode  *pre;
      if (p->Ltag ==1)
          pre=p->lchild;
      else
      { pre=p->lchild;
         while (pre->Rtag==0)
           pre=pre->rchild; /*对于左子树的右分支进行遍历*/
       }
     printf("\n前驱结点是:");
     printf("%c",pre->cdata);
     return(*pre);
  }/* InPreNode*/
void main()
{
  char ch;
  printf("请输入树的结点信息:\n");
  bt=Create_BiTree2();
  getchar();
  printf("创建中序线索二叉树!\n");
  InOrderThr(bt) ;
  printf("对中序线索二叉树进行中序遍历:\n");
  InVisitThr(bt);
  printf("\n在中序线索二叉树中查找p结点的前驱结点");
  printf("\n输入p所指结点的信息:");
  ch=getchar();
  getchar();
  *p=Thr_search(bt,ch) ;
   if(p)
     {*pre1=InPreNode( bt,p);
       printf("\n查找到的前驱结点是:\n");
      printf("%c",pre1->cdata);
     }
   else  printf("\n该结点不存在前驱结点！");
   getchar();
 }