以下是插入和删除
#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");
}
2009-10-29 21:17
