哈夫曼编码译码器.doc

文档介绍：哈夫曼编码/译码器二叉排序树的实现二〇一四年六月二叉排序树的实现一、内容用顺序和二叉链表作存储结构1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;2)对二叉排序树T作中序遍历,输出结果;3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”;软件综合课程设计二、程序代码#include<>#include<>#defineMAX64//规定树中结点的最大数目typedefstructnode{//定义数据结构intltag,rtag;//表示child域指示该结点是否孩子chardata;//记录结点的数据structnode*lchild;//记录左右孩子的指针structnode*rchild;}TBtree;TBtree*Que[MAX];//建队,保存已输入的结点的地址TBtree*CreatTree(){//建树函数,返回根指针charch;intfront,rear;TBtree*T,*s;T=NULL;front=1;rear=0;//置空二叉树printf("进行初始化,创建二叉树(按满二叉树序号顺序输入,中间的虚节点用\"@\"表示,\"#\"结束)\n");ch=getchar();//输入第一个字符while(ch!='#')//判断是否为结束字符{s=NULL;if(ch!='@')//判断是否为虚结点{s=(TBtree*)malloc(sizeof(TBtree));s->data=ch;s->lchild=NULL;s->rchild=NULL;s->rtag=0;s->ltag=0;}rear++;Que[rear]=s;//将结点地址加入队列中if(rear==1)T=s;//输入为第一个结点为根结点else{if(s!=NULL&&Que[front]!=NULL)//孩子和双亲结点均不是虚结点{if(rear%2==0)Que[front]->lchild=s;elseQue[front]->rchild=s;}if(rear%2==1)front++;}ch=getchar();}returnT;}voidInorder(TBtree*T)//中序遍历{if(T!=NULL){if(T->ltag!=1)Inorder(T->lchild);printf("%c→",T->data);if(T->rtag!=1)Inorder(T->rchild);}}TBtree*pre=NULL;voidPreThread(TBtree*root)//中序线索化算法,函数实现{TBtree*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);}}voidPrintIndex(TBtree*t)//输出线索{TBtree*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);//如果此结点有前驱也有后继,就输出后继elseif(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);}}TBtree*SearchChild(TBtree*point,charfindnode)//查找孩子结点函数{TBtree*point1,*point2;if(point!=NULL){if(point->data==findnode)returnpoint;elseif(point->ltag!=1){point1=SearchC