第五章 树和二叉树.

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

1 第五章 树和二叉树

2 5.1 树的基本概念

3 5.1.1 树的定义 1．树的定义 树(Tree)是n(n≥0)个有限数据元素的集合。 当n = 0时，称这棵树为空树。在一棵非空树T中：
树的定义 1．树的定义 树(Tree)是n(n≥0)个有限数据元素的集合。 当n = 0时，称这棵树为空树。在一棵非空树T中： (1) 有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 (2) 若n > 1，除根结点之外的其余数据元素被分成m(m > 0)个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。树的结构定义是一个递归的定义

4 根 A B C D E F G H I J K L M 有子树的树 子树

5 2. 树的特点 (1) 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 (2) 树中所有结点可以有零个或多个后继结点。

6 对比树型结构和线性结构的结构特点

7 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
线性结构 树型结构 根结点 (无前驱) 第一个数据元素 (无前驱) 多个叶子结点 (无后继) 最后一个数据元素 (无后继) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 其它数据元素 (一个前驱、 一个后继) 其它数据元素 (一个前驱、 多个后继)

8 3. 树的抽象数据类型定义 上述树的结构定义加上树的一组基本操作构成了树的抽象数据类型 ADT Tree{ 数据对象：D = { Di | 1≤i≤n, n≥0, Di∈ElemType} 数据关系：对于一棵树关系R满足下列二元关系：T = (D，R)，其中，D为树T中结点的集合，R为树中结点之间关系的集合。 基本操作： Root(T)；Value(T，cur_e)； }ADT Tree

9 5.1.2 树的基本术语

10 结点: 数据元素+若干指向子树的分支 结点的度: 分支的个数 树的度: 树中各结点的度的最大值 叶子结点: 度为零的结点 分支结点:
D 分支结点: 度大于零的结点 孩子结点、双亲结点、 兄弟结点、堂兄弟结点、 祖先结点、子孙结点 H I J M

11 结点的子树的 称为该结点的孩子，相应地，该结点称为孩子的双亲。双亲在同一层的结点互为堂兄弟。
A B C D E F G H I J K L M 结点的子树的 称为该结点的孩子，相应地，该结点称为孩子的双亲。双亲在同一层的结点互为堂兄弟。 例如，B,C,D为A的子树的根，则B,C,D是A的孩子，而A则是B,C,D的双亲。 同一个双亲的孩子之间互称兄弟。将这些关系进一步推广，结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。如B的子孙为E、F、K和L 。

12 从根开始定义,根为第一层,根的孩子为第二层。
结点的层次: A B C D E F G H I J M K L 从根开始定义,根为第一层,根的孩子为第二层。 树的深度： 树中叶子结点所在的最大层次

13 有序树 无序树： 子树之间不存在确定的次序关系。 A B C A C B
树中结点的各子树从左至右是有次序的（不能互换）。最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子。 无序树： 子树之间不存在确定的次序关系。

14 root F A B E F K L C G D H I J M 森林： 是 m（m≥0）棵互不相交的树的集合

15 任何一棵非空树的逻辑结构： 是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林

16 叶子：K，L，F，G，M，I，J 结点A的孩子：B，C，D 结点B的孩子：E，F 结点I的双亲：D 结点L的双亲：E 结点A的层次：1
H I J K L M 结点A的层次：1 结点M的层次：4 结点A的度：3 结点B的度：2 结点M的度：0 树的深度：4 树的度：3 结点F，G为堂兄弟 结点A是结点F，G共同的祖先 结点B，C，D为兄弟 结点K，L为兄弟

17 5.2 二叉树

18 1．二叉树的定义 A B C D E F G H K E F 根结点 右子树 左子树
二叉树是另一种树型结构，其特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)。 二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 根结点 右子树 A B C D E F G H K E F 左子树

19 二叉树的五种基本形态： 只含根结点 空树 左右子树均不为空树 N 右子树为空树 左子树为空树 N N N L R L R

20 2．二叉树的抽象数据类型定义 ADT BinaryTree{ 数据对象：具有相同特性的数据元素的集合 数据关系：是一棵每个结点至多只有两棵子树，有左右之分，次序不能颠倒的树。 基本操作： Root(T)；Value(T，e)；Parent(T，e)； LeftChild(T，e)； RightChild(T，e)； LeftSibling(T，e)； }ADT BiTree

21 二叉树的主要基本操作： 查 找 类 插 入 类 删 除 类

22 5.2.2 二叉树的特性

23 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1) 性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1） 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式： n0 = n2+1

24 性质 4 ： 具有 n 个结点的完全二叉树的深度为  log2n +1
性质 5 ： 完全二叉树中，双亲与左右子树之间编号的关系 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 i/2 的结点为其双亲结点; (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

25 两类特殊的二叉树： 1、满二叉树： 指的是深度为k且含有2k-1个结点的二叉树。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 对满二叉树的结点 进行连续编号： 约定编号从根结点起，自上而下，自左至右。

26 2、完全二叉树： 指的是深度为k的，有n个结点的二叉树。当且仅当树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 1 2 3 4 5 6 7 8 9 10 12 特点： （1）叶子结点只可能在层次最大的两层上出现； （2）对任一结点，若其右分支下的子孙的最大层次 为l, 则其左分支下的子孙的最大层次必为l或l+1.

27 判断是否为完全二叉树: 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 4 5 6 7 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6

28 性质 4 ： 具有 n 个结点的完全二叉树的深度为  log2n +1
性质 5 ： 完全二叉树中，双亲与左右子树之间编号的关系 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 i/2 的结点为其双亲结点; (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

29 5.2.3 二叉树的存储结构 1、 二叉树的顺序 存储表示 2、二叉树的链式 存储表示

30 1、 二叉树的顺序存储表示 所谓二叉树的顺序存储，就是用一组地址连续的存储单元依次按照从上至下、从左到右的顺序存储二叉树中的结点。
对于完全二叉树和满二叉树，树中结点的序号可以唯一地反映结点之间的逻辑关系。

31 采用顺序存储方式时，完全二叉树中结点的数据在一维数组中的存储按照满二叉树的编号对应数组下标的标号进行存储，即将编号为i的结点存储在一维数组下标为i-1的分量中，此时二叉树中结点间的存储位置关系能够反映它们之间的逻辑关系，这样既能最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的相对位置，以及结点之间的关系。下图给出了（b）完全二叉树的顺序存储示意。

32 对于一般的二叉树，如果按从上至下、从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。下面给出了一棵一般二叉树改造后的完全二叉树型态及其顺序存储状态示意图。

33 例:用一维数组存储二叉树 A B C D E F 2 5 1 14 3 7 结点按照满二叉树的编号来存储。 A B D 0 C E F 二叉树看做满二叉树的一部分，将该结点为6个的二叉树放在含14个分量的一维数组中存储，将根结点A编号为1，放在一维数组下标为0的第一个分量中，B编号为2放在下标为1的分量中，不存在此结点时，用“0”填充。

34 2、 二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType
SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt;

35 注意： 这种存储方法适用于满二叉树，对于任意二叉树表示左右子树，浪费了许多存储空间，不用这种方法。

36 3、二叉树的链式存储表示 结点指针个数的不同有以下几种存储方法： 1) 二叉链表 2) 三叉链表

37 1). 二叉链表 结点结构: lchild data rchild typedef struct BiTNode { // 结点结构
TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;

38 整个二叉树用指向根结点的指针BiTree表示
结点结构: lchild data rchild A D E B C F 

39 2．三叉链表 结点结构: parent lchild data rchild C 语言的类型描述如下: TElemType data;
typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree;

40 TriTree parent lchild data rchild 结点结构:  A D E B C F 

41 5.3 二叉树的遍历和 线索二叉树

42 二叉树的遍历方法 遍历的定义 (1) 遍历：在实际应用问题中，常常需要按一定顺序对二叉树中的每个结点逐个进行访问，查找具有某一特点的结点，然后对这些满足条件的结点进行处理，在数据结构中称为遍历。 (2) 二叉树的遍历：顺着某一条路径访问二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。

43 “遍历”是任何类型均有的操作 （1）线性结构 只有一条搜索路径，不需要另加讨论。 （2）非线性结构
（因为每个结点均只有一个后继） （2）非线性结构 二叉树，每个结点有两个后继，存在按什么样的搜索路径进行遍历的问题。

44 2. 对二叉树进行遍历的方法 1) 根据二叉树的定义进行遍历的方法 由二叉树的定义可知，二叉树由三个基本单元组成：根结点、左子树和右子树。因此，对这三部分依次遍历，就遍历了整个二叉树。 由此可见，对二叉树的遍历可以有三条搜索路径： 先序(根)遍历二叉树、 中序(根)遍历二叉树、 后序(根)遍历二叉树。

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

46 算法5.1 void PreOrderTraverse (BiTree T, void( *visit)(TElemType &e)) { // 先序遍历二叉树 if (T) { visit(T->data); // 访问结点 PreOrder(T->lchild, visit); // 先序遍历左子树 PreOrder(T->rchild, visit);// 先序遍历右子树 }

47 中（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。

48 算法5. 2 void InOrderTraverse(BiTree T, void(
算法5.2 void InOrderTraverse(BiTree T, void( *visit)(TElemType &e)) { //中序遍历二叉树 if (T) { InOrderTraverse (T->lchild, visit);// 中序遍历左子树 visit(T->data)； // 访问根结点 InOrderTraverse (T->rchild, visit); // 中序遍历右子树 } }

49 后（根）序的遍历算法： 若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。

50 算法5. 3 void PostOrderTraverse(BiTree T, void(
算法5.3 void PostOrderTraverse(BiTree T, void( *visit)(TElemType &e)) { //后序遍历二叉树 if (T) { PostOrderTraverse (T->lchild, visit); // 后序遍历左子树 PostOrderTraverse (T->rchild, visit);// 后序遍历右子树 visit(T->data)； // 访问根结点 } }

51 下面通过例5.1讲解对二叉树进行先序、后序遍历的具体做法。
例5.1案例：邮递员为A—K家送报，每家都要送到。对于每一家都先往左拐，后向右拐，即先左后右，每家都路过三次，其中只有一次能送报。 （1）先序遍历：第一次经过时访问 即先访问结点再遍历它的左右子树 （2）中序遍历：第二次经过时访问 即先遍历左子树再访问结点最后遍 历右子树 （3）后序遍历：第三次经过时访问 即遍历完左右子树后访问结点

52 A 先序序列： B E A B C D E F G H K C F D G H K

53 A 中序序列： B E B D C A E H G K F C F D G H K

54 A 后序序列： B E D C B H K G F E A C F D G H K

55 用二叉链表表示以上的遍历，用C语言描述，分为：
算法的递归描述 *算法的非递归描述

56 “遍历”是二叉树各种操作的基础,可以在遍历过程中对结点进行各种操作。 如:对已知树可求结点的双亲,结点的孩子结点,判定结点所在的层次。 也可在遍历过程中生成结点,建立二叉树的存储结构.

57 5.3.2 遍历的应用举例 A B C D A B C D ^ ^ ^ ^ ^ 例:按下列次序顺序读入字符可建立相应的二叉链表: T A B

58 由遍历序列构造二叉树 由遍历序列构造二叉树是对已知的一棵二叉树进行恢复的一个过程，有以下两种恢复方法： (1) 由二叉树的先序序列和中序序列唯一确定一棵二叉树。 (2) 由二叉树的后序序列和中序序列唯一确定一棵二叉树。

59 下面通过一个例子，来给出二叉树的先序序列和中序序列构造唯一的一棵二叉树的实现算法。 例5
下面通过一个例子，来给出二叉树的先序序列和中序序列构造唯一的一棵二叉树的实现算法。 例5.3 已知一棵二叉树的先序序列与中序序列分别为 A B C D E F G H I B C A E D G H F I 试恢复该二叉树，并用C语言描述该过程。

60 算法的思想是： 先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；再在先序序列中确定左、右子树的先序序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树，这是一个递归过程。

61

62 Status CreateBiTree(BiTree &T) {
scanf(&ch); if (ch==' ') T = NULL; else { if (!(T = BiTNode*)malloc(sizeof(BitNode)))) exit(OVERFLOW); T->data = ch; // 生成根结点 CreateBiTree(T->lchild); // 构造左子树，返回指向左指针域的指针 CreateBiTree(T->rchild); // 构造右子树，返回指向右指针域的指针 } return OK; } // CreateBiTree

63 5.3.4 线索二叉树

64 1. 线索二叉树的定义 遍历二叉树的结果是，求得结点的一个线性序列，遍历可以看作是对二叉树进行线性化的操作。在得到的线性序列中，每一个结点都有一个前驱和后继，将其放入存贮结构中。 A 先序序列: A B C D E F G H K B E 中序序列: B D C A H G K F E F C G 后序序列: D C B H K G F E A D H K

65 存贮结构中指向线性序列中 “前驱”和 “后继” 的指针信息，称作“线索”，前驱和后继的信息是在遍历过程中得到的。
A B C D E F G H K 二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而结点的任一序列的前驱与后继信息, 只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域; ^ B E ^ C ^ ^ D ^

66 lchild ltag data rtag rchild 其中: lchild 域指示结点的左孩子 ltag={ 1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag={ 1 rchild 域指示结点的后驱 以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。

67 typedef enum { Link, Thread } PointerThr;
2.二叉树的二叉线索存储表示: typedef enum { Link, Thread } PointerThr; // Link==0:指针，Thread==1:线索 typedef struct BiThrNod { TElemType data; struct BiThrNode *lchild, *rchild; // 左右指针 PointerThr LTag, RTag; // 左右标志 } BiThrNode, *BiThrTree;

68 中序线索化二叉树： B D C A E H G K F 0 A 0 前驱 后继 1 B 0 1 E 0 0 C 1 0 F 1 1 D 1

69 令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点;
模仿线性表的存储结构,在二叉树的线索链表上也添加一个头结点, 令其lchild域的指针指向二叉树的根结点,其rchild域的指针指向中序遍历时访问的最后一个结点; 同时,令二叉树中序序列中的第一个结点lchild域指针的和最后一个结点rchild域的指针均指向头结点; 就像为二叉树建立了一个双向线索链表,就好比人在一个圆圈上走路.

70 中序线索化二叉树： 头结点 建立一个双向循环链表，具有所有遍历所需的信息，遍历时不需要栈。 1 1 前驱 0 A 0 后继 1 B 0
前驱 0 A 0 后继 建立一个双向循环链表，具有所有遍历所需的信息，遍历时不需要栈。 1 B 0 1 E 0 0 C 1 0 F 1 1 D 1 0 G 0 1 H 1 1 K 1

71 3、如何建立线索链表？P84 在中序遍历过程中修改结点的 左、右指针域，以保存当前访问结 点的“前驱”和“后继”信息。

72 树和森林

73 树的存储结构 1、双亲表示法 2、孩子链表表示法 3、树的二叉链表(孩子-兄弟） 存储表示法

74 1、双亲表示法: 结点结构: data parent 这种存储结构利用了每个结点（除根以外）只有惟一的双亲的性质。
以一组连续空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。 结点结构: data parent

75 data parent 0 A 1 B 2 C 3 D 4 E 5 F 6 G 5 A B C D E F G

76 typedef struct PTNode {
#define MAX_TREE_SIZE 100 结点结构: data parent typedef struct PTNode { ElemType data; int parent; // 双亲位置域 } PTNode; Typedef struct{ //树结构 PTNode nodes[MAX_TREE_SIZE]; int r,n; //根的位置和结点数 }PTree;

77 2、孩子链表表示法: child nextchild
把每个结点的孩子结点排列起来，看成是一个线性表，以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。 而n个头指针又组成一个线性表，为了便于查找，采用顺序存储结构。 孩子结点结构: child nextchild

78 A B C D E F G 0 A 1 B 2 C 3 D 4 E 5 F 6 G -1 2 4 data firstchild 1 2 3
-1 2 4

79 typedef struct CTNode { int child; struct CTNode *nextchild;
孩子结点结构: child nextchild typedef struct CTNode { int child; struct CTNode *nextchild; } *ChildPtr;

80 结点结构: typedef struct { TElemType data; ChildPtr firstchild; // 孩子链的头指针 } CTBox;

81 结点结构: 4、树的二叉链表 (孩子-兄弟）存储表示法 称二叉树表示法或二叉链表表示法。即以二叉链表作树的存储结构。
链表中结点的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为 firstchild域和nextsibling域。 结点结构: firstchild data nextsibling

82 root root A B C D E F G A B C E D F G A B C E D F G

83 typedef struct CSNode{ Elem data; struct CSNode
结点结构: firstchild data nextsibling typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;

84 5.4.2 树与二叉树的转换 将一棵树转换为二叉树的方法是：树中的每一个结点都是左手拉它的第一个孩子，右手拉该结点的兄弟，
树与二叉树的转换 对于一棵无序树，树中结点的各孩子的次序是无关紧要的，而二叉树中结点的左、右孩子结点是有区别的。为了避免发生混淆，约定树中每一个结点的孩子结点按从左到右的次序顺序编号。如图5.23所示的一棵树，根结点A有B、C、D三个孩子，可以认为结点B为A的第一个孩子结点，结点C为A的第二个孩子结点, 结点D为A的第三个孩子结点。 将一棵树转换为二叉树的方法是：树中的每一个结点都是左手拉它的第一个孩子，右手拉该结点的兄弟，

85

86 5.4.3 森林与二叉树的转换 森林转换为二叉树的方法如下： (1) 将森林中的每棵树转换成相应的二叉树。
森林与二叉树的转换 森林转换为二叉树的方法如下： (1) 将森林中的每棵树转换成相应的二叉树。 (2) 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。

87

88

89 由此，树和森林的各种操作均可与二叉树的各种操作相对应。

90 5.4.4 树和森林的遍历

91 1、树的遍历 2、森林的遍历

92 1.树的遍历可有2条搜索路径: 先根(次序)遍历: 后根(次序)遍历: 按层次遍历: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。
若树不空，则先依次后根遍历各棵子树，然后访问根结点。 按层次遍历: 若树不空，则自上而下自左至右访问树中每个结点。

93 先根遍历时顶点的访问次序： A B C D E F G H I J K A B E F C D G H I J K 后根遍历时顶点的访问次序： E F B C I J K H G D A 层次遍历时顶点的访问次序： A B C D E F G H I J K

94 B C D E F G H I J K 森林 可以分解成三部分： 1。森林中第一棵树的根结点； 2。森林中第一棵树的子树森林； 3。森林中其它树构成的森林。

95 2.森林的遍历 若森林不空，则 先序遍历 访问森林中第一棵树的根结点; 先序遍历森林中第一棵树的子树森林;
先序遍历森林中(除第一棵树之外)其 余树构成的森林。 先序遍历 即：依次从左至右对森林中的每一棵树进行先根遍历。

96 中序遍历森林中(除第一棵树之外)其 余树构成的森林。
若森林不空，则 中序遍历森林中第一棵树的子树森林; 访问森林中第一棵树的根结点; 中序遍历森林中(除第一棵树之外)其 余树构成的森林。 即：依次从左至右对森林中的每一棵树进行后根遍历。

97 树的遍历和二叉树遍历的对应关系 ？ 树 森林 二叉树 先根遍历 先序遍历 先序遍历 后根遍历 中序遍历 中序遍历

98 5.5 赫 夫 曼 树 与 赫 夫 曼 编 码

99 哈夫曼树的基本概念 1. 哈夫曼(Huffman)树的概念 哈夫曼(Huffman)树，也称最优树，是一类带权路径长度最短的树，有着广泛应用。

100 路径：从树中一个结点到另一个结点之间的分支构成这两个结点的路径.
路径长度:路径上的分支数目 d c a b 树的路径长度： 从树根到每一结点的路径长度之和。

101 树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 (对所有叶子结点) d c a b 2 4 7 5

102 例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树.
给定一组具有确定权值的叶子结点，可以构造出不同的带权二叉树。 例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树. a b c d 7 5 2 4 d c a b 2 4 7 5 WPL=7*2+5*2+2*2+4*2=36 a b c d 7 5 2 4 WPL=7*3+5*3+2*1+4*2=46 WPL=7*1+5*2+2*3+4*3=35

103 最优二叉树（Huffman树）的定义： 设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，必存在一棵其带权路径长度最小的树，称为“最优二叉树”，或“赫夫曼树”

104 5.5.2 哈夫曼树的构造方法 (赫夫曼算法) 以二叉树为例:
哈夫曼树的构造方法 (赫夫曼算法) 以二叉树为例: 根据给定的 n 个权值 {w1, w2, …, wn}，构造 n 棵二叉树的集合F = {T1, T2, … , Tn}，其中每棵二叉树中均只含一个带权值为 wi 的根结点,其左、右子树为空树; (1) 例如: 已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 9 7

105 在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
(2) 9 例如: 已知权值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 7 5 2

106 从F中删去根结点的权值为最小的两棵二叉树，同时加入刚生成的新树;
(3) 9 5 6 2 7 6 9 7 5 2 7

107 重复 (2) 和 (3) 两步，直至 F 中只含一棵树为止。
(4) 5 2 7 6 9 13 9 7 5 2 7 6

108 29 1 9 7 16 13 1 1 5 2 7 6 1 00 01 11 100 101

109 例 a 7 b 5 c 2 d 4 a 7 b 5 c 2 d 4 6 a 7 b 5 c 2 d 4 6 11 18 a 7 b 5 c 2 d 4 6 11

110 例 w={5, 29, 7, 8, 14, 23, 3, 11} 29 14 8 7 15 11 3 5 19 23 42 5 14 29 7 8 23 3 11 14 29 7 8 23 11 3 5 11 3 5 8 19 23 42 29 14 7 15 58 8 7 15 14 29 23 3 5 11 11 3 5 8 19 14 29 23 7 15 11 3 5 8 19 23 42 29 14 7 15 58 100 11 3 5 8 19 29 23 14 7 15

111 5.5.3 huffman编码 主要用途是实现数据压缩。 设给出一段报文： CAST CAST SAT AT A TASA
字符集合是 { C, A, S, T }，各个字符出现的频度(次数)是 W＝{ 2, 7, 4, 5 }。 若给每个字符以等长编码 A : 00 T : C : S : 11 则总编码长度为 ( ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 因各字符出现的概率为{ 2/18, 7/18, 4/18, 5/18 }。

112 化整为 { 2, 7, 4, 5 }，以它们为各叶结点上的权值，建立霍夫曼树。左分支赋 0，右分支赋 1，得霍夫曼编码(变长编码)。
A : 0 T : C : S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于 霍夫曼树的带权路径长 度WPL。 霍夫曼编码树

113 利用赫夫曼树编码，是一种最优前缀编码，即所传电文的总长度最短。
若要设计长短不等的编码，必须是任一个字符的编码都不是同一字符集中另一个字符的编码的前缀，这种编码叫前缀编码。

114 Huffman编码： 思想：根据字符出现频率编码，使电文总长最短 编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列

115 例 要传输的字符集 D={C,A,S,T, ; } 字符出现频率 w={2,4,2,3,3} T : 00 ; : 01 A : 10
6 4 2 8 14 T ; A 1 T : 00 ; : 01 A : 10 C : 110 S : 111

116 译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。

117 例 电文是{CAS;CAT;SAT;AT}编码为： 电文为“1101000”其译文是：
3 6 4 2 8 14 T ; A 1 T : 00 ; : 01 A : 10 C : 110 S : 111 例 电文是{CAS;CAT;SAT;AT}编码为： 电文为“ ”其译文是： CAT