哈夫曼树的总结点数与叶节点数的关系
哈夫曼树的总结点个数(多于 1 时)不能为偶数。
数据结构，设哈夫曼树的叶子结点总数为m，则结点总数为多少，这个题目怎么解
哈夫曼树是二叉树，且结点的度只有两种，一种是度为0的叶子节点，另一种则是度为2的内部结点，不存在度为1 的结点，根据二叉树的性质（好像是性质3）度为0的结点和度为2 的结点的关系:n0=n2+1很容易算出；叶子结点总数为m的哈夫曼树的总结点数为：2m-1
如果给定权值总数有N个，则其哈夫曼树的结点总数为多少
给值总数有N个，则其哈夫曼结点总数为2*N-1； 给定n个权值作为n的叶子结点，构造一棵二叉若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
2006个节点的二叉树的深度为多少
有10个叶子节点的哈夫曼树的总结点数为多少个
21题 答案是D。
哈夫曼树只有度为0和2的结点，设度为0的结点个数为x，度为2的结点个数为y，则x+y=2y+1，所以x-1=y，x即为13，也就是叶子结点，所以总结点个数为13+12=25.22题 答案是B。
三种遍历方式叶子结点的相对位置保持不变。
23题 无答案。
这四种排序方法都是不稳定的。
24题 答案是A。
关键路径的定义。
25题 答案是B。
若处理冲突时采用拉链法，则结点中会包含指针。
26题 答案是C。
折半查找的要求。
27题 答案暂定为AB。
C是绝对不行的，至于D原因不清楚。
28题 答案是D。
只有存取，没有增加删除时，使用顺序表效率最高。
29题 答案是C。
带头结点的链队列，初始为空的条件是front和rear相等并指向头结点，入队rear变化，出队front变化。
30题 答案暂定为A。
完全二叉树的最后一层可以是满的，即满二叉树。
哈夫曼树的构造
第一步：排序 2 4 5 9第二步：挑出2个最小的 2 4 为叶子构造出 62 4第三步：判断 6 不大于 5或9（叶子中最小的2个）=》 同方向生长，得出： 11 6 52 4第四步：继续生长 20 11 9 6 5 2 4权值为 2*3+4*3+5*2+9*1=37也可以20+11+6=37例题：6、13、18、30、7、16排序 6 7 13 16 18 30 13 6 7 26 26大于16或18 =》分支生长 13 13 6 7 26 34 13 13 16 18 6 7此时最小的2个数为 26 30 得出 56 34 26 30 16 18 13 136 7最后得出 90 56 34 26 30 16 18 13 13 6 7 权值 21990+56+26+13+34 or 6*4+7*4+13*3+30*2+16*2+18*2
哈夫曼树的结点总个数一定是偶数吗
6.12的程序 *\\\/ \\\/\\\/------------------- 公用的常量和类型 ----------------------------#include#include #include #include \\\/\\\/函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 #define UINT_MAX 1000 typedef int Status; \\\/* c6-7.h 哈夫曼树和哈夫曼编码的存储表示 *\\\/ typedef struct HTNode { char leaf; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; \\\/* 动态分配数组存储哈夫曼编码表 *\\\/typedef char **HuffmanCode; \\\/* 动态分配数组存储哈夫曼编码表 *\\\/typedef struct Node{ char leaf; unsigned int weight; struct Node * next;}LeafNode,*LeafLink;typedef struct { LeafLink head; unsigned len;}LeafLinkList; int min1(HuffmanTree t,int i) { \\\/* 函数void select()调用 *\\\/ int j,flag; unsigned int k=UINT_MAX; \\\/* 取k为不小于可能的值 *\\\/ for(j=1;j<=i;j++) if(t[j].weight*s2) { j=*s1; *s1=*s2; *s2=j; } } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, LeafLinkList L) \\\/* 算法6.12 *\\\/ { \\\/* w存放n个字符的权值(权值均需大于0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC*\\\/ int m,i,s1,s2,start; int n=L.len; unsigned c,f; LeafLink ptr; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; printf(表长为%d\\\哈夫曼树含节点数为%d\\\ ,n,m); HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); \\\/* 0号单元未用 *\\\/ ptr=L.head->next; for(p=HT+1,i=1;i<=n;++i,++p,ptr=ptr->next) { (*p).leaf=ptr->leaf; printf(%d\\\,(*p).leaf); (*p).weight=ptr->weight; printf(%d\\\ ,(*p).weight); (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(;i<=m;++i,++p) { (*p).parent=0; (*p).leaf=0; } for(i=n+1;i<=m;++i) \\\/* 建哈夫曼树 *\\\/ { \\\/* 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 *\\\/ select(HT,i-1,&s1,&s2); HT[s1].parent=HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } \\\/* 从叶子到根逆向求每个字符的哈夫曼编码 *\\\/ HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); \\\/* 分配n个字符编码的头指针向量([0]不用) *\\\/ cd=(char*)malloc(n*sizeof(char)); \\\/* 分配求编码的工作空间 *\\\/ cd[n-1]='\\\\0'; \\\/* 编码结束符 *\\\/ for(i=1;i<=n;i++) { \\\/* 逐个字符求哈夫曼编码 *\\\/ start=n-1; \\\/* 编码结束符位置 *\\\/ for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) \\\/* 从叶子到根逆向求编码 *\\\/ if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); \\\/* 为第i个字符编码分配空间 *\\\/ strcpy(HC[i],&cd[start]); \\\/* 从cd复制编码(串)到HC *\\\/ } free(cd); \\\/* 释放工作空间 *\\\/ for(i=1;i<=n;i++) { printf(%c编码为%s:\\\ ,HT[i].leaf,HC[i]); } }void InitLeafList(LeafLinkList &L){ L.head=(LeafLink)malloc(sizeof(LeafLink)); L.head->next=NULL; L.len=0;}void PrintList(LeafLinkList L){ LeafLink p; p=L.head->next; printf(打印链表\\\ ); printf(表长为%d\\\ ,L.len); while(p!=NULL) { printf(%c or %d,%u\\\,p->leaf,p->leaf,p->weight); printf(打印一个节点\\\ ); p=p->next; } printf(打印结束\\\ ); printf(\\\ );}void EnLeafList(LeafLinkList &L,char ch){ LeafLink p,pre,temp; int flag=0; pre=p=L.head; printf(%d即为%c******\\\ \\\ ,ch,ch); if(p->next==NULL) \\\/\\\/p->next=NULL则为第一次插入操作 { printf(第一次插入\\\ ); temp=(LeafLink)malloc(sizeof(LeafNode)); temp->leaf=ch; temp->weight=1; temp->next=NULL; p->next=temp; L.len++; } else {p=p->next; while(p!=NULL) { if(ch==p->leaf) { p->weight++; printf(加权\\\ ); p=NULL; flag=1; } \\\/\\\/权重加一 else if(chleaf) \\\/\\\/插入 { printf(插入A\\\ ); temp=(LeafLink)malloc(sizeof(LeafNode)); temp->leaf=ch; temp->weight=1; temp->next=p; pre->next=temp; L.len++; flag=1; p=NULL; } else \\\/\\\/继续寻找插入点 { pre=p; p=p->next; } } if(p==NULL&&flag!=1) \\\/\\\/若p=NULL则插到链尾 { printf(插入B\\\ ); temp=(LeafLink)malloc(sizeof(LeafNode)); temp->leaf=ch; temp->weight=1; temp->next=NULL; pre->next=temp; L.len++; } }}void EnCoding(){ FILE *fp,*fr,*fc; HuffmanTree HT; HuffmanCode HC; int i,n; LeafLinkList L; InitLeafList(L); char filename[15]; char ch; printf(请输入文件名:\\\ ); scanf(%s,filename); if( !(fp=fopen(filename,r)) ) { printf(打开文件失败，请输入正确的文件名!! ); exit(0); } ch=getchar(); \\\/\\\/接收执行scanf语句时最后输入的回车符 printf(文件已经打开\\\ ); while(!feof(fp)) { ch=fgetc(fp); if(ch==-1) { printf(结束统计\\\ ); } else { EnLeafList(L,ch); } } PrintList(L); HuffmanCoding(HT,HC, L); n=L.len; for(i=1;i<=n;i++) { puts(HC[i]); } char TreeName[15]; printf(把哈夫曼树存入文件，请输入文件名:\\\ ); scanf(%s,TreeName); if( !(fr=fopen(TreeName,wb)) ) { printf(打开文件失败，请输入正确的文件名!! ); exit(0); } ch=getchar(); \\\/\\\/接收执行scanf语句时最后输入的回车符 printf(文件已经打开\\\ ); \\\/\\\/把哈夫曼树存入文件 printf(%d\\\ ,n); printf(把树的长度先存入\\\ ); putw(n,fr); \\\/\\\/把树的长度先存入 for(i=1;i<=2*n-1;i++) if(fwrite(&HT[i],sizeof(struct HTNode),1,fr)!=1) printf(文件写入出错\\\ ); fclose(fr); printf(打印原来的树\\\ ); for(i=1;i<=2*n-1;i++) printf(%c %u %u %u %u\\\ ,HT[i].leaf ,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild ); fclose(fr); printf(把编码结果存入文件，请输入文件名:\\\ ); char CodeFileName[15]; scanf(%s,CodeFileName); if( !(fc=fopen(CodeFileName,wb)) ) { printf(打开文件失败，请输入正确的文件名!! ); exit(0); } ch=getchar(); \\\/\\\/接收执行scanf语句时最后输入的回车符 printf(待编码的文件位置指针重新指向开始位置\\\ ); printf(对待编码文件进行编码，编码同步显示，并将结果存入指定的文件\\\ ); rewind(fp); while(!feof(fp)) { ch=fgetc(fp); printf(%c\\\ ,ch); if(ch==-1) { printf(结束编码\\\ ); } else { for(int tap=0,i=1;tap==0&&i<=n;) \\\/\\\/查找，该叶子对应的编码串 { if(ch==HT[i].leaf) \\\/\\\/找到，打印出对应的编码，并存入文件 { printf(%s\\\ ,HC[i]); fputs(HC[i],fc); \\\/\\\/将编码字符串存入文件 tap=1; } else { i++; } } } } fclose(fp); \\\/\\\/关闭文件 fclose(fc); \\\/\\\/关闭文件} int decode(FILE *fc,HuffmanTree HT,int n){ while(!feof(fc)) { char ch=fgetc(fc); if(ch=='0') { n=HT[n].lchild; if(HT[n].leaf!=0) { printf(%c,HT[n].leaf); return OK; } else { decode(fc,HT,n); return OK; } } else if(ch=='1') { n=HT[n].rchild; if(HT[n].leaf!=0) { printf(%c,HT[n].leaf); return OK; } else { decode(fc,HT,n); return OK; } } else return OK; } return ERROR;}void Decoding() \\\/\\\/解码文件，并将结果显示出来{ FILE *fc,*fr; char CodeFileName[15],ch,TreeName[15]; int i; printf(解码文件，请输入文件名(如*.dat):\\\ ); scanf(%s,CodeFileName); if( !(fc=fopen(CodeFileName,r)) ) { printf(打开文件失败，请输入正确的文件名!! ); exit(0); } ch=getchar(); \\\/\\\/接收执行scanf语句时最后输入的回车符 printf(存放编码结果文件已经打开\\\ ); \\\/\\\/读入哈夫曼树 HuffmanTree HT; printf(取出对应的哈夫曼树文件，请输入文件名,\\\ ); scanf(%s,TreeName); if( !(fr=fopen(TreeName,rb)) ) \\\/\\\/打开存放哈夫曼树的文件 { printf(打开文件失败，请输入正确的文件名!! ); exit(0); } int n=getw(fr); \\\/\\\/将叶子数目取出 printf(叶子数目%d\\\ ,n); HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode)); \\\/* 然后分配空间，0号单元未用 *\\\/ for(i=1;i<=2*n-1;i++) if(fread(&HT[i],sizeof(struct HTNode),1,fr)!=1) printf(文件读出出错\\\ ); int length=2*n-1; \\\/\\\/总长度 printf(总结点数目为：%d\\\ ,n); printf(该文件译码后得到的源文件为：\\\ ); printf(**************************************\\\ ); while(!feof(fc)) { decode(fc,HT,length); } printf(**************************************\\\ ); printf(\\\ \\\ );}int PreOrderPrint(HuffmanTree HT,int n,int count){ if(HT[n].lchild) { for(int i=0;i
