数据结构第六篇1.ppt

6.6 哈夫曼树（Huffman）及其应用 1）最优树的定义 2）如何构造最优树 3）哈夫曼树的应用 void InThreading(BiThrTree p) { if (p) { // 对以p为根的非空二叉树进行线索化 InThreading(p-lchild); //线索化左子树 if (!p-lchild) // 建前驱线索 { p-LTag = Thread; p-lchild = pre; } if (!pre-rchild) // 建后继线索 { pre-RTag = Thread; pre-rchild = p; } pre = p;// 保持 pre 指向 p 的前驱（p变成刚刚访问过的结点） InThreading(p-rchild); // 右子树线索化 } // if } // InThreading 6.4.1 树的存储结构 1、双亲表示法 2、孩子链表表示法 3、树的二叉链表(孩子-兄弟)存储表示法 6.4 树和森林 A B C D E F G r=0 n=7 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data parent 1、双亲表示法(顺序存储） typedef struct PTNode {//结点结构: TElemType data; int parent; // 双亲位置域 } PTNode; #define MAX_TREE_SIZE 100 data parent 结点结构: //------------树的双亲表存储表示-------------- typedef struct { //树结构 PTNode nodes[MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree; 孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树的 根。 结点同构：结点的指针个数相等，为树的度d data child1 child2 …… childd data degree child1 child2 …... childd 可以证明： 在有n个结点，度为d的树中有n*(d-1)+1个空链域。 结点不同构： A B C D E F G r=0 n=7 data firstchild 0 A 1 B 2 C 3 D 4 E 5 F 6 G 6 4 5 1 2 3 2、孩子表示法: 孩子结点结构: child nextchild 双亲结点结构: data firstchild A B C D E F G r=0 n=7 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 4 6 4 5 1 2 3 data parent firstchild 双亲结点结构: typedef struct CTNode { //孩子结点结构 int child; struct CTNode *nextchild; } *ChildPtr; typedef struct { //双亲结点结构 TElemType data; ChildPtr firstchild; // 孩子链表头指针 } CTBox; typedef struct { //树结构 CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree; A B C D E F G A B C E D F G 3、树的二叉链表 (孩子-兄弟）存储表示法 root A B C E D F G typedef st