《赫夫曼树的构造讲义》由会员分享，可在线阅读，更多相关《赫夫曼树的构造讲义（28页珍藏版）》请在金锄头文库上搜索。
1、 第31页（共31页）一、调试成功程序及说明1、题目：赫夫曼树实现算法思想：假设每种字符在电文中出现的次数为wi，其编码长度为li,电文中只有n中字符，则电文总长为：wili。对应到二叉树上，若置wi为叶子结点的权，li恰为从古恩结点到叶子结点的路径长度。则wili恰为二叉树上带权路径的长度。源程序：/-赫夫曼树和赫夫曼编码的存储表示-#include #include #include using namespace std;#define NUM 10typedef struct unsigned int weight; /权值unsigned int parent; /父母unsigne
2、d int lchild; /左孩子unsigned int rchild; /右孩子HTNode,*HuffmanTree; /动态分配存储赫夫曼树typedef char *HuffmanCode; /动态分配赫夫曼编码表void Select(const HuffmanTree HT, const int n, int &s1, int &s2) /选择权parent为0且权值最小的两个结点，返回位置s1,s2int i;for (i =0 ; i parent = 0)s1 = s2 = i; break;i+;for (i; i parent = 0)if (HT + i)-weig
3、ht weight )s1 = i;else if(HT + s1)-weight weight & (HT + i)-weight weight)s2 = i;if (s1 = s2)for (i = 0; i parent = 0 & s1 != i)s2 = i;break;i+;for (i; i parent=0 & (HT + s2)-weight(HT + i)-weight & s1 != i)s2 = i;return ;void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC,const int *w,const int n)/
4、w存放n格字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCif (n = 1) return; int m; m = 2 * n - 1; /赫夫曼树结点个数int p; /叶子结点位置int i; /双亲位置int s1;int s2;HT = new HTNodem; /构造数组for (p = 0; p weight = *(w + p);(HT + p)-lchild = 0;(HT + p)-rchild = 0;(HT + p)-parent = 0;for (p; p weight = 0;(HT + p)-lchild = 0;(HT + p)-rchild
5、 = 0;(HT + p)-parent = 0;for (i = n; i m; i+) /建赫夫曼树 /在HT0i-1选择parent为0且weight最小的两个结点,起序号分别为s1和s2.Select(HT, i , s1, s2);HTs1.parent = i;HTs2.parent = i;HTi.lchild = s1;HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;/-从叶子到根逆向求每个字符的赫夫曼编码-HC = new char*n; /分配n个字符编码的头指针向量char *cd; cd = new char
6、n; /分配求编码的工作空间cdn - 1 = 0;int start; /编码结束位置int f; /父母结点位置int c; /结点位置/逐个字符求赫夫曼编码for (i = 0; i n; i+) start = n - 1; /编码结束符位置for (c = i, f = HTi.parent; f != 0; c = f, f = HTf.parent) /从根节点逆向求编码if (HTf.lchild = c)start-;cdstart = 0;elsestart-;cdstart = 1;HCi = new charn - start; /为第i个字符编码分配空间strcpy(
7、HCi, cd+start); /从cd赋值编码（串）到HCdeletecd;/end HuffmanCodingint main()HuffmanTree ht; /赫夫曼树HuffmanCode hc; /赫夫曼编码表int weightNUM = 5,29,7,8,14,23,3,11,30,55;int m = 2 * NUM - 1; /树结点个数int i;HuffmanCoding(ht, hc, weight, NUM);cout 输出赫夫曼树对应的表格： endl;cout setw(8) weight setw(8) parent setw(8) lchild setw(8
8、) rchild endl;for (i = 0; i m; i+)cout setw(8) hti.weight setw(8) hti.parent setw(8) hti.lchild setw(8) hti.rchild endl;cout 赫夫曼编码表格: endl;for (i = 0; i NUM; i+)cout *(hc + i) endl;cout endl;system(pause);return 0; 运行结果：2、题目：求孩子兄弟树的深度算法思想：使用递归的方法，每个根的深度等于它的子树的深度加1，而同一层中最大深度则将兄弟结点中的所有深度进行比较，取最大值即可源程序
9、：#include #include using namespace std;#define OK 1#define SIZE 20#define Nil #/-树的孩子兄弟存储表示-typedef char ElemType;typedef struct CSNodeElemType data; /结点元素struct CSNode *firstchild; /第一个孩子struct CSNode *nextsibling; /连接的兄弟CSNode,*CSTree,*pCSTree;/-辅助队列与操作-typedef CSTree QElemType;typedef struct QNod
10、e QElemType data;QNode *next;QNode, *QueuePtr;typedef struct QueuePtr front; /队头指针QueuePtr rear; /队尾指针LinkQueue;/ - 基本操作函数 -/构造一个空队列Qvoid InitQueue(LinkQueue &Q) Q.front = Q.rear = new QNode; /分配存储空间if (!Q.front) /存储空间分配失败cout 存储空间申请失败！ next = NULL;/InitQueue/销毁队列void DestroyQueue(LinkQueue &Q) while (Q.front != NULL)Q.rear = Q.front-next;delete Q.front;Q.front = Q.rear;return;/DestroyQueue/若队列为空队列，返回TRUE,否则返回FALSEbool QueueEmpty(LinkQueue Q) if (Q.front = Q.rear) return true;else return false; /QueueEmpty/用e返回队列的头元素void GetHead(LinkQueue Q, QElemType &e) e = Q.front-next-data;/GetHead
