第六章 树和二叉树.

Presentation on theme: "第六章 树和二叉树."— Presentation transcript:

1 第六章 树和二叉树

2 6.1 树的结构定义和基本操作 树是n(n>=0)个结点的有限集。在一颗非空树中： 1）有且仅有一个特定的称为根(root)的结点；
6.1 树的结构定义和基本操作 树是n(n>=0)个结点的有限集。在一颗非空树中： 1）有且仅有一个特定的称为根(root)的结点； 2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2,…,Tm，其中每个集合本身又是一颗树，并且称为根的子树(subtree)。 A B D E F C G H I J K L M

3 (A(B(E(K,L),F),C(G),D(H(M),I,J)))
树的四种表示方法 1）树型 2）广义表 3）嵌套集合表 ）凹入表示法 A B D C E F G H I J K L M K L G F M I J A B D H C E 1）树型表示法 (A(B(E(K,L),F),C(G),D(H(M),I,J))) 2)广义表表示法 3）嵌套集合

4 4) 凹入表表示法 A B E K L F C G D H M I J

5 树结构中的基本术语 1. 结点的度：结点具有的子树数称为该结点的度(Degree)。 叶子结点：度为0的结点，即没有子树的结点。
分支结点：度大于零的结点。 内部结点：除根结点外的分支结点。 树的度：一棵树中各个结点度数的最大值。 2. 儿子结点和父亲结点：一个结点的子树的根称为该结点的儿子结点； 反之，该结点则称为其孩子结点的父亲结点。 兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。

6 3.路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
子孙结点：一个结点的子树中所有结点均称之为该结点的子孙结点。 祖先结点：反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。 4.树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。

7 5.有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。
6. 森林：n个树的集合叫森林(Forest)。 树形结构的逻辑特征 可用树中结点之间的父子关系来描述： 树中任一结点都可以有零个或多个直接后继结点（即儿子结点），但至多只能有一个直接前趋结点（即父亲结点）。树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。

8 6.2 二叉树 二叉树是n个结点的有限集合（n≥0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 a b c d e f g

9 二叉树有五种基本形态 (a) 空二叉树 (b) 仅有一个根结点的二叉树 (c) 右子树为空的二叉树 (d)左子树为空的二叉树 (e)左、右子树均非空的二叉树

10 二叉树与度为二的有序树的区别：二叉树的子树有左 右之分，而度为二的有序树当某个结点只有一个子结点时 是没有先后之分的。

11 20+21+…+2k - 1=2k-1 二叉树的性质 性质1 在二叉树的第i层上至多有2i-1个结点。 (可由数学归纳法证明 )
证明: 设第i层的结点数为xi（1≤i≤k），深度为k的二叉树的结点数为M，xi最多为2i-1，则有： 20+21+…+2k - 1=2k-1

12 性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:
证明 : 设n为二叉树的结点总数，n1为二叉树中度为1的结点数，则有： n＝n0＋n1＋n2 (1) 在二叉树中，除根结点外，其余结点都有唯一的一个进入分支。设B为二叉树中的分支数，那么有： B＝n－ (2)

13 这些分支是由度为1和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出两个分支，所以有：
B＝n1＋2n2 (3) 由（2）、（3）得n= n1＋2n (4) 由(1)、(4)得 n0＝n2＋1

14 满二叉树 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 或者：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。

15 完全二叉树 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

16 性质4 具有n个结点的完全二叉树的深度k为 证明 ： 根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有 2k－1－1<n≤2k-1 即 k－1≤n<2k 对不等式取对数，有 k－1≤log2n<k 由于k是整数，所以有 k＝

17 性质5 对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点，有：
（1）如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝=1，则序号为i的结点是根结点，无双亲结点。 （2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，则序号为i的结点无左孩子。 （3）如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。

18 此外，若对二叉树的根结点从0开始编号，则相应的i号结点的双亲结点的编号为（i－1）/2，左孩子的编号为2i＋1，右孩子的编号为2i＋2。

19 6.2.3二叉树的存储结构 1、顺序存储结构 所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。

20

21 即将bt定义为含有MAX_TREE_SIZE个TElemType类型元素的一维数组。
若是非完全二叉树，则用空结点存放。 二叉树的顺序存储表示可描述为： #define MAX_TREE_SIZE /*二叉树的最大结点数*/ typedef TElemType SqBiTree[MAX_TREE_SIZE] SqBiTree bt; 即将bt定义为含有MAX_TREE_SIZE个TElemType类型元素的一维数组。

22 2、链式存储结构 所谓二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。 （1）二叉链表存储 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为：

23 其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。

24 二叉树的二叉链表存储表示可描述为： typedef struct BiTNode{ TElemType data; struct BiTNode *lchild;*rchild; /*左右孩子指针*/ } BiTNode , *BiTree;

25 （2）三叉链表存储 每个结点由四个域组成，具体结构为： 其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点 。

26 6.3遍历二叉树和线索二叉树 遍历二叉树 二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
由二叉树的定义可知，一棵由根结点、左子树和右子树三部分组成；用L、D、R分别表示遍历左子树、遍历根和遍历右子树，则二叉树的遍历有：DLR、LDR、LRD（限定先左后右） DLR：先序遍历 LDR：中序遍历 LRD：后序遍历

27 先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树；

28 算法6.1 二叉树先序遍历递归算法 void PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) {// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数， // 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。 if (T) { //修改课本 P109 Visit(T->data); PreOrderTraverse(T->lchild, Visit); PreOrderTraverse(T->rchild, Visit); } } // PreOrderTraverse

29 进行先序、中序和后序遍历都是从根结点A开始的，且在遍历过程中经过结点的路线是一样的，只是访问的时机不同而已。

30 二叉树遍历的非递归实现 中序遍历二叉树的非递归实现 算法6.2的思路： （1）指向根结点的指针进栈；
（2）栈顶的指针若非空则其左孩子指针进栈；直到栈顶指针为空； （3）弹出栈顶空指针，若栈非空，再弹出栈顶指针并访问该指针指向的结点；该指针指向结点的右孩子指针入栈； （4）继续第（2）步的操作，直到栈为空。

31 算法6.2中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) { InitStack(S); Push(S, T); // 根指针进栈 while (!StackEmpty(S)) { // 向左走到尽头 while (GetTop(S, p) && p) Push(S, p->lchild); Pop(S, p); // 空指针退栈 if (!StackEmpty(S)) { // 访问结点，向右一步 Pop(S, p); if (!Visit(p->data)) return ERROR; Push(S, p->rchild); } return OK; } // InOrderTraverse

32 中序遍历二叉树的非递归实现 算法6.3的思路： （1）指向根结点的指针非空则进栈； （2）栈顶的指针的左孩子指针非空则进栈；直到栈顶指针左孩子指针为空； （3）若栈非空，弹出栈顶指针并访问该指针指向的结点；该指针指向结点的右孩子指针若非空则入栈； （4）继续第（2）步的操作，直到栈为空。 与算法6.2没有质的区别，只是6.3在指针非空入栈，6.2是入栈后判断其是否非空

33 算法6.3中序遍历二叉树T的非递归算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) { InitStack(S); p = T; while (p || !StackEmpty(S)) {// 非空指针进栈，继续左进 if (p) { Push(S, p); p = p->lchild; } else { // 指针退栈，访问其所指结点，再向右进 Pop(S, p); if (!Visit(p->data)) return ERROR; p = p->rchild; } return OK; } // InOrderTraverse

34 算法6.4 按先序次序输入二叉树中结点的值构造二叉链表表示的二叉树T，空格字符表示空树
BiTree CreateBiTree(BiTree &T) { scanf("%c",&ch); if (ch==' ') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data = ch; // 生成根结点 CreateBiTree(T->lchild); // 构造左子树 CreateBiTree(T->rchild); // 构造右子树 } return T; } // CreateBiTree

35 层次遍历思路 所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

36 （1）访问该元素所指结点； （2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。 此过程不断进行，当队列为空时，二叉树的层次遍历结束。

37 层次遍历二叉树 void LevelOrder（BiTree bt）
{ BiTree Queue[MAXNODE]; //一维数组用以实现队列 int front,rear; //分别表示当前对首元素和队尾元素在数组中的位置 if (bt = = NULL) return; front= -1; rear=0; queue[rear]= bt; while(front!=rear) {front++; Visite ( queue[front]->data ); /*访问队首结点的数据域*/ if (queue[front]->lchild!=NULL) /*将队首结点的左孩子结点入队列*/ { rear++; queue[rear]= queue[front]->lchild; } if (queue[front]->rchild!=NULL) /*将队首结点的右孩子结点入队列*/ queue[rear]=queue[front]->rchild; } }

38 由遍历序列恢复二叉树 已知结点的先序序列和中序序列，确定这棵二叉树。 二叉树的先序遍历是先访问根结点，其次再按先序遍历方式遍历根结点的左子树，最后按先序遍历方式遍历根结点的右子树。在先序序列中，第一个结点一定是二叉树的根结点。另一方面，中序遍历是先遍历左子树，然后访问根结点，最后再遍历右子树。根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。

39 根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。

40 已知一棵二叉树的先序序列与中序序列分别为：
A B C D E F G H I B C A E D G H F I 试恢复该二叉树。

41 同样的道理，由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。因为，依据后序遍历和中序遍历的定义，后序序列的最后一个结点，就如同先序序列的第一个结点一样，可将中序序列分成两个子序列，分别为这个结点的左子树的中序序列和右子树的中序序列，再拿出后序序列的倒数第二个结点，并继续分割中序序列 。

42 线索二叉树 在具有N个结点的二叉树中，有N+1个是空指针域，用空指针域存放结点的前驱和结点的后继；即用左指针域存放其前驱，用右指针域存放其后继。再增加两个标志，用以区别是孩子指针还是前驱或后继指针。 结点的结构为： lchild LTag data RTag rchild

43 LTag: 0: lchild域为结点左孩子的指针；
1：则为其前驱的指针。 RTag: 0: rchild域为结点右孩子的指针； 1：则为其后继的指针。

44 指向前驱和后继的指针叫线索。具有线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称线索化。
中序线索树

45 二叉树的二叉线索存储表示 typedef enum PointerTag{Link,Thread}; typedef struct BiThrNode { TElemType data; PointerTag LTag,RTag; struct BiThrNode *lchild,*rchild; }BiThrNode , *BiThrTree ;

46 线索化的思路： 对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。

47 算法6.6 将二叉树中序线索化 Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{ // 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。 if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW); Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点 Thrt->rchild = Thrt; // 右指针回指 if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指 else { Thrt->lchild = T; pre = Thrt; InThreading(T); // 算法6.7：中序遍历进行中序线索化 pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化 Thrt->rchild = pre; } return OK; } // InOrderThreading

48 算法6.7 void InThreading(BiThrTree p) { if (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的前驱 InThreading(p->rchild); // 右子树线索化 } } // InThreading

49 查找结点*P的中序后继结点 （1）如果该结点的右标志为1，那么其右指针域所指向的结点便是它的后继结点； （2）如果该结点的右标志为0，表明该结点有右孩子，根据中序遍历的定义，它的后继结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链向下查找，当某结点的左标志为1时，它就是所要找的后继结点。

50 查找结点*P的中序前驱结点 寻找其中序的前驱结点，有以下两种情况： （1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点； （2）如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。

51 中序遍历线索二叉树 (从根结点开始) 算法6.5 Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType)) { // // T指向头结点。 BiThrTree p; p = T->lchild; // p指向根结点 while (p != T) // 空树或遍历结束时，p==T { while (p->LTag==Link) p = p->lchild;//找最左的结点 Visit(p->data); // 访问其左子树为空的结点 while (p->RTag==Thread && p->rchild!=T) { p = p->rchild; Visit(p->data); }// 访问后继结点 p = p->rchild; // p进至其右子树根 } return OK; } // InOrderTraverse_Thr

52 6.4树和森林 6.4.1树的存储结构 1.双亲表示法 树的双亲表示存储结构（参考书P135,图6.13）
#define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data; int parent; //双亲位置域 } typedef struct PTNode nodes[MAX_TREE_SIZE]; int r,n; //根的位置和结点数 }Ptree;

53 2.孩子表示法（实际上是第七章的图的表示方法）
一、每个结点有多个指针域，其中每个指针指向一棵子树的根结点。（参考书P136上图） 二、把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作为存储结构，则n个结点有n个孩子链表。（参考书P137,图6.14a）

54 树的孩子链表存储表示 typedef struct CTNode { //孩子结点 int child; struct CTNode *next; } *ChildPtr; typedef struct { TElemType data; ChildPtr firstchild; //孩子链表头指针 } CTBox; typedef struct CTBox nodes[MAX_TREE_SIZE]; int n,r }Ctree;

55 3.孩子兄弟表示法 又称二叉树表示法，或二叉链表表示法。即以二叉链表作为树的存储结构。 链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 typedef struct CSNode { ElemType data; struct CSNode *firstchild,*nextsibling; }CSNode,*CSTree; 参考书P137,图6.15

56 6.4.2森林与二叉树的转换 要把普通树转换为二叉树，就必须找到一种结点与结点之间至多用两个量说明的关系 ：树中每个结点最多只有一个最左边的儿子结点和一个右邻的兄弟结点 。 按照这种关系可以把普通树转换成相应的二叉树，具体方法如下： 1) 在所有兄弟结点之间加一连线； 2) 对每个结点，除了保留与其最左儿子结点的连线外，去掉该结点与其它儿子结点的连线。

57 图中所示的树经过变换，可得下面的形式。

58 得到的已是一棵二叉树，若按顺时针方向将它旋转就更清楚地变为下面所示的二叉树。

59 由于树根没有兄弟，所以树转换为二叉树后，二叉树的根结点的右子树必为空。

60 森林与二叉树的转换 一、森林转换成二叉树 如果F={T1,T2,…,Tm}是森林，则按如下规则转换成一棵二叉树B=(root,LB,RB) 1、若F为空，即m=0，则B为空树； 2、若F非空，即m<>0，则B的根root即为森林中第一棵树的根ROOT(T1)；B的左子树LB是从T1中根结点的子树森林 转换而成的二叉树;其右子树RB是从森林 转换而成的二叉树。

61 二、二叉树转换成森林 如果B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林F={T1,T2,…,Tm}： 1）若B为空，则F为空； 2）若B非空，则F中第一棵树T1的根ROOT（T1）即为二叉树B的根root; T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林 是由B的右子树RB转换而成的森林。

62 6.4.3 树和森林的遍历 遍历树的两种方法： 一、先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；
二、后根遍历：先依次后根遍历每棵子树，然后访问根结点； 举任意一个例子

63 森林的两种遍历方法： (1) 先根次序遍历的规则： 若森林F为空, 返回； 否则 访问F的第一棵树的根结点； 先根次序遍历第一棵树的子树森林； 先根次序遍历其它树组成的森林。 （2) 中根次序遍历的规则：（实际就是后根遍历每棵树） 若森林F为空，返回； 中根次序遍历第一棵树的子树森林； 中根次序序遍历其它树组成的森林。

64 6.6哈夫曼树及其应用 哈夫曼树基本术语： 1) 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
2) 路径长度：路径上的分支数称为这两点之间的路径长度。 3) 树的路径长度：树的路径长度是从树的根到每一结点的路径长度之和，一般记作pl。 在结点数目相同的二叉树中，完全二叉树或满二叉树的路径长度最短。

65 PL= =10 PL= =11

66 4) 结点的权：在许多实际应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。
5) 带权路径长度：从树的根结点到该结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度。 树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为： 其中n表示叶子结点个数，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。

67 wpl=36 给定一组n个实数，以它们作为各个叶子结点的权，可构成不同的有n个叶子结点的二叉树，这些二叉树的带权路径长度wpl可能不同。
给定四个数7，5，2，4作为叶子结点的权，可构成几种不同的二叉树。 wpl=36

68 wpl=35 wpl=46

69 哈夫曼树 哈夫曼树又称为最优二叉树； 定义：设有n个权值{w1，w2，…，wn}，在这些权值为各个叶子结点的权所构成的二叉树中，带权路径长度WPL最小的二叉树叫做哈夫曼树。 哈夫曼(Huffman)于1952年提出了得到这种树的算法，因此相应的算法称为哈夫曼算法。

70 哈夫曼算法 将n个权值{w1，w2，…，wn}按递增次序排列；
设其顺序为w1，w2，…，wn，取出最小的两个w1和w2，分别作为根结点的左、右儿子结点的权组成一个二叉树，并认为其根结点的权w12=w1+w2； 将w12按其数值大小插入到w3至wn之间，使数值仍保持为递增的次序； 再取出最小的两个作为根的左、右儿子的权组成二叉树，也令根的权等于此两数值之和，并同样将此根结点按权值大小插入到剩下的数据中，保持数值的递增次序。 如此重复进行下去，直到构成一棵二叉树为止，即得到哈夫曼树。

71 哈夫曼算法过程 给定4个数：7，5，2，4。

72

73

74 赫夫曼树 和赫夫曼编码的存储表示 typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*Huffmantree;//动态分配数组存储赫夫曼树 typedef char **Huffmancode;

75 哈夫曼编码 哈夫曼编码（Haffman coding）是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，其压缩效率取决于被压缩数据的特征。 通常我们将压缩过程称为编码，解压缩过程称为解码，利用哈夫曼树构造的用于通信的二进制编码称为哈夫曼编码。 前缀编码:指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

76 设计电文总长度最短的二进制前缀编码即为以n种字符出现频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便称为哈夫曼编码

77 a b c d f e g 2 3 5 10 7 8 15 20 35 55

78 哈夫曼编码是由一串‘0’和‘1’组成的编码。 二叉树的左分支表示‘0’，右分支表示‘1’。则叶子结点的哈夫曼编码是从根到叶子的路经。
a b c d f e g 2 3 5 10 7 8 15 20 35 55 1 结点a的编码为：100 结点b的编码为：010 结点c的编码为：0110 结点d的编码为：0111 结点e的编码为：101 结点f的编码为：00 结点g的编码为：11

79 求赫夫曼编码的算法如算法6.12

80 HuffmanTree HT[m] 13 12 11 9 10 8 5 4 7 6 1 2 3 55 35 20 15 weight lchild parent rchild 为了运算直观从第一个结点开始存储

81 哈夫曼编码算法 g 1 f e d c b a bits

82 哈夫曼解码的算法 decode(tree) hufmtree tree[ ];
{ int i,j,c,p,b; int endflag=-1; i=m; /*从根结点开始往下搜索*/ scanf(“%d”,&b); /*读入一个二进制码*/ while (b!=endflag) { if (b= =0) i=tree[i].lchild; else i=tree[i].rchild; if (tree[i].lchild= =0) /*tree[i] 是叶子结点*/ { putchar(tree[i].ch); i=m; } scanf(“%d”,&b); } if (tree[i].lchild!=0) //电文读完但没到叶子结点 printf(“\nERROR\n”); 哈夫曼解码的算法

83 Huffman tree[m] 7 5 2 3 8 10 20 15 35 55 1 6 11 4 9 12 13 a b c d e f
7 5 2 3 8 10 20 15 35 55 1 6 11 4 9 12 13 a b c d e f g \0 weight lchild rchild parent ch 为了运算直观从第一个结点开始存储