哈夫曼编码译码器详解.doc

哈夫曼编码/译码器二叉排序树的实现 二〇一四 年 六 月 二叉排序树的实现? 用顺序和二叉链表作存储结构?? 以回车(\n)为输入结束标志,输入数列L，生成一棵二叉排?序树T； 对二叉排序树T作中序遍历，输出结果； 输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”；#include stdio.h #include stdlib.h #define MAX 64 //规定树中结点的最大数目 typedefstruct node{ //定义数据结构 intltag,rtag; //表示child域指示该结点是否孩子 char data; //记录结点的数据 struct node *lchild; //记录左右孩子的指针 struct node *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!=NULLQue[front]!=NULL) //孩子和双亲结点均不是虚结点 { if(rear%2==0) Que[front]-lchild=s; else Que[front]-rchild=s; } if(rear%2==1)front++; } ch=getchar(); } return T; } void Inorder(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; void PreThread(TBtree *root) //中序线索化算法，函数实现 { TBtree *p; p=root; if(p) { PreThread(p-lchild);//线索化左子树 if(prepre-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(TBtree *t) //输出线索 { TBtree *f; f=t; if(f) {