以下是插入和删除
#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");
}
为什么这个用了4个头文件了？？？？
