数据结构与算法分析 C++

发布网友 发布时间：2022-05-23 22:57

我来回答

共3个回答

热心网友 时间：2023-05-18 08:21

你说的是中序线索二叉树的插入和删除

#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("请输入新的结点信息，@为空结点，#为结束标志：");
 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("\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;
  printf("发现结点%c\n",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("\t插入结点操作已经完成，并同时完成了线索化的恢复\n");
}

热心网友 时间：2023-05-18 08:22

中序线索二叉树的插入和删除

热心网友 时间：2023-05-18 08:22

说的是中序线索二叉树的插入和删除
#include <<a href="https://www.baidu.com/s?wd=stdio.h&tn=44039180_cpr&fenlei=mv6quAkxTZn0IZRqIHckPjm4nH00T1Y3PvFhnWFbmHuhny7Wm1IB0ZwV5Hcvrjm3rH6sPfKWUMw85HfYnjn4nH6sgvPsT6K1TL0qnfK1TL0z5HD0IgF_5y9YIZ0lQzqlpA-bmyt8mh7GuZR8mvqVQL7gPYpyq8Q1TdnHTkn1R4P1n1njfdrjf3P0" target="_blank" class="-highlight">stdio.h</a>>
#include "<a href="https://www.baidu.com/s?wd=malloc.h&tn=44039180_cpr&fenlei=mv6quAkxTZn0IZRqIHckPjm4nH00T1Y3PvFhnWFbmHuhny7Wm1IB0ZwV5Hcvrjm3rH6sPfKWUMw85HfYnjn4nH6sgvPsT6K1TL0qnfK1TL0z5HD0IgF_5y9YIZ0lQzqlpA-bmyt8mh7GuZR8mvqVQL7gPYpyq8Q1TdnHTkn1R4P1n1njfdrjf3P0" target="_blank" class="-highlight">malloc.h</a>"
#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("请输入新的结点信息，@为空结点，#为结束标志：");
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) //<a href="https://www.baidu.com/s?wd=%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86&tn=44039180_cpr&fenlei=mv6quAkxTZn0IZRqIHckPjm4nH00T1Y3PvFhnWFbmHuhny7Wm1IB0ZwV5Hcvrjm3rH6sPfKWUMw85HfYnjn4nH6sgvPsT6K1TL0qnfK1TL0z5HD0IgF_5y9YIZ0lQzqlpA-bmyt8mh7GuZR8mvqVQL7gPYpyq8Q1TdnHTkn1R4P1n1njfdrjf3P0" target="_blank" class="-highlight">中序遍历</a>
{
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;
printf("发现结点%c\n",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("\t插入结点操作已经完成，并同时完成了线索化的恢复\n");
}