二叉树 二叉树 遍历 递归.

Presentation on theme: "二叉树 二叉树 遍历 递归."— Presentation transcript:

1 二叉树 二叉树 遍历 递归

2 线性结构和非线性结构 线性结构： 结构中的数据元素之间存在一对一的关系。 我们前面学的数据结构(向量、列表、堆栈、队列等)都是线性结构。
非线性结构： 树形：结构中数据元素之间存在一对多的关系。 图形：结构中数据元素之间存在多对多的关系。

3 数据的逻辑结构——线性结构 A , B , C , ······· ，X ,Y , Z 学 生 成 绩 表 86 胡孝臣 9861103
学 生 成 绩 表 86 胡孝臣 95 刘忠赏 100 张卓 成绩 姓名 学号 第二章      数据结构与算法 2．1 概述 计算机加工处理的对象是数据，而数据之间有一定的内在联系，即数据具有一定的结构。因此我们要了解数据的逻辑关系、数据在计算机内的存储表示形式以及对数据施加的运算，才能在程序中对数据进行有效的处理。 数据结构是一门研究数据组织、存储和运算的一般方法的学科。 2．1．1 数据结构的基本概念 数据结构是描述一组数据元素及元素间的逻辑上的关系的。可以用集合论的方法给出数据结构的定义 数据结构可描述为 Group=（D，R） 下面用例子来解释数据结构的定义 （1）有且仅有一个开始结点(表头结点)，它没有直接前驱，只有一个直接后继; （2）有且仅有一个终端结点(表尾结点)，它没有直接后继，只有一个直接前驱; （3）其它结点都有且仅有一个直接前驱和直接后继； （4）元素之间为一对一的线性关系。

4 数据的逻辑结构——树形结构 全校学生档案管理的组织方式

5 数据的逻辑结构——图形结构 结点间的连结是任意的 1 4 2 3 2 1 3

6 树的概述 树形结构是一类非常重要的非线性结构，它可以很好地描述客观世界中广泛存在的具有分支关系或层次特性的对象。
因此在计算机领域里有着广泛应用。如： 操作系统中的文件管理 编译程序中的语法结构 数据库系统信息组织形式

7 数据的逻辑结构可描述为： Group=（D，R）
有限个数据元素的集合 A B C D E F G H J I 这些数据元素间关系的集合 D={A,B,C,D,E,F,G,H,I,J} R={(A,B),(A,C),(A,D),(B,E),(B,F),(D,G),(D,H),(F,I),(F,J)}

8 A B C D E F G H J I 树的定义1 树的逻辑结构可以这样描述：树是包含n(n>0)个结点的有穷集合K（ k0 、 k1 、...、kn-2 、 kn-1 ），且在K上定义了一个关系N，关系N满足以下条件： 有且仅有一个结点k0∈K，它对于关系N来说没有前驱结点。k0称作树的根。 除结点外k0 ， K中的每一个结点对于关系N来说都有且仅有一个直接前驱结点；有零个或多个直接后继结点。

9 A B C D E F G H J I 树的定义2 一颗大树分成几个大的分枝（称作子树），每个大分枝再分成几个小分枝，小分枝再分成更小的分枝，… ，每个分枝也都是一颗树，由此我们可以给出树的递归定义。 树的逻辑结构可以这样描述：树是包含n(n>0)个结点的有穷集合T，使得： 有一个特别标出的称作根的结点。 除根以外的其他结点被分成m （m≥0）个不相交的集合T1， T2 ，… ， Tm ，而且这些集合的每一个又都是树。树T1， T2 ，… ， Tm称作这个根的子树。

10 树的相关术语 度：一个结点的子树的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。 树中度为零的结点称为叶结点（或终端结点）。
A B C D E F G H J I 树的相关术语 度：一个结点的子树的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。 树中度为零的结点称为叶结点（或终端结点）。 树中度不为零的结点称为分枝结点（或非终端结点）。除根结点外的分枝结点统称为内部结点。

11 树的相关术语 结点的子树的根称为该结点的孩子结点，相应地，该结点称为孩子的双亲结点。
A B C D E F G H J I 树的相关术语 结点的子树的根称为该结点的孩子结点，相应地，该结点称为孩子的双亲结点。 如果存在树中的一个结点序列K1，K2，... ，Kj，使得结点Ki是结点Ki+1的双亲结点(1≤i≤j-1)，则称该结点序列是树中从结点K1到结点Kj的一条路径。我们把路径所经过的边(即连接两个结点的线段)的数目称作这条路径的长度。 如果在树中存在一条从结点K到结点M的路径，则称结点K是结点M的祖先结点，也称结点M是结点K的子孙结点。 注意，任一结点既是它自己的祖先也是它自己的子孙。

12 树的相关术语 树中一个结点的高度是指：从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。
A B C D E F G H J I 第2层 第0层 第1层 第3层 树的相关术语 树中一个结点的高度是指：从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。 从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的深度或层数。根结点的深度为0，其余结点的深度为其双亲结点的深度加1。深度相同的结点属于同一层。

13 树的相关术语 树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。
A B C D E F G H J I 树的相关术语 树的定义在某些结点之间确定了父子关系，我们又将这种关系延拓为祖先子孙关系。 但是树中的许多结点之间仍然没有这种关系。例如兄弟（同一个双亲的孩子称为兄弟）结点之间就没有祖先子孙关系。 如果我们在树的每一组兄弟结点之间定义一个从左到右的次序（即不能互换），则得到一棵有序树；否则称为无序树。 设结点n的所有儿子按其从左到右的次序排列为：n1，n2，… ，nk，则我们称n1是n的最左儿子，或简称左儿子，并称ni是ni-1的右邻兄弟，或简称右兄弟(i=2,3,..k)。

14 二叉树的定义 二叉树（BinaryTree）是n（n≥0）个结点的有限集合，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 A A A A B C B B （a）空二叉树 （b）根和空的左右子树 （c）根和非空左子树，空的右子树 （d）根和空的左子树，非空右子树 （e）根和非空的左右子树

15 二叉树不是树的特例 二叉树与无序树不同： 二叉树中，每个结点最多只能有两棵子树，且有左右之分。
树不能为空，但二叉树可以为空，因此二叉树并非是树的特殊情形，它们是两种不同的数据结构。 二叉树与度数为2的有序树不同： 在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。 而在二叉树中，即使是一个孩子也有左右之分。

16 二叉树的性质 性质1：二叉树第i层上的结点数目最多为2i（i≥0）。 性质2：深度为k的二叉树至多有2k+1-1个结点（k≥0）。 第0层
A B C D E F G 二叉树的性质 第1层 第2层 性质1：二叉树第i层上的结点数目最多为2i（i≥0）。 性质2：深度为k的二叉树至多有2k+1-1个结点（k≥0）。

17 满二叉树(FullBinaryTree)
一棵深度为k且有2k+1-1个结点的二又树称为满二叉树。 满二叉树的特点： （1） 每一层上的结点数都达到最大值。即对给定的深度，它是具有最多结点数的二叉树。 （2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 A B C D E F G

18 完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。 完全二叉树的特点： （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树就是一棵完全二叉树。 （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。

19 二叉树的实现（BinaryTree.java）
双亲 值 左 右 public class BinaryTree { protected Object val; protected BinaryTree parent; protected BinaryTree left, right; public static final BinaryTree EMPTY = new BinaryTree(); BinaryTree.EMPTY是一个哑元结点，当树为空时，可以调用其中的方法。

20 构造方法1：构造空二叉树 private BinaryTree() { val = null; parent = null;
left = right = this; } ^ val parent left right this 哑元结点Empty=

21 构造方法2：构造仅含根结点的二叉树 public BinaryTree(Object value) { val = value;
parent = null; left = right = EMPTY; } ^ value val parent left right this

22 构造方法3：构造其他二叉树 this this right left ^ value
public BinaryTree(Object value, BinaryTree left, BinaryTree right) { this(value); setLeft(left); setRight(right); } value2 value1 value this left right ^ value val parent left right this

23 setLeft()方法 B A E this this C newleft B E this C newleft ^ A

24 setLeft()方法 public void setLeft(BinaryTree newLeft) { if (isEmpty())
return; if (left.parent() == this) left.setParent(null); left = newLeft; left.setParent(this); } protected void setParent(BinaryTree newParent) { parent = newParent; }

25 setRight()方法 public void setRight(BinaryTree newRight) {
if (isEmpty()) return; if (right.parent() == this) right.setParent(null); right = newRight; right.setParent(this); } protected void setParent(BinaryTree newParent) { parent = newParent; }

26 存取函数 val parent left right public BinaryTree left() { return left; }
public BinaryTree right() return right; public BinaryTree parent() return parent; public Object value() return val; public void setValue(Object value) val = value; val parent left right

27 计算大小 A B C D E public boolean isEmpty() { return this == EMPTY; }
public int size() if (isEmpty()) return 0; else return left().size() + right().size() + 1; public BinaryTree root() if (parent() == null) return this; return parent().root(); A B C D E

28 计算高度、深度 A B C D E public int height() { if (isEmpty()) return -1; else
return 1+Math.max(left.height(),right.height()); } public int depth() if (parent() == null) return 0; return 1+parent.depth();

29 11.2 实例：家谱树（Pedigree.java）
val parent left right g ^ G 父子关系 母子关系 E F A B C D

30 练习，打印出整个家谱树中的所有女性亲属。
打印出G的所有直系女性亲属。 练习，打印出整个家谱树中的所有女性亲属。 import structure.*; public class Pedigree{ public static void main(String args[]){ BinaryTree a = new BinaryTree("A"); BinaryTree b = new BinaryTree("B"); BinaryTree e = new BinaryTree(“E",a,b); BinaryTree c = new BinaryTree("C"); BinaryTree d = new BinaryTree("D"); BinaryTree f = new BinaryTree("F",c,d); BinaryTree g = new BinaryTree("G",e,f); BinaryTree person = g; while (person.right() != BinaryTree.EMPTY) { person = person.right(); // right branch is mother System.out.println(person.value()); // value is name }

31 树创建好后，我们可以向树中加入分枝 B A C D ^ G E F 父子关系 母子关系 M N d g n

32 import structure.*; public class Pedigree{ public static void main(String args[]){ … … BinaryTree g = new BinaryTree("G",e,f); d.setLeft(new BinaryTree("M")); BinaryTree n = new BinaryTree("N"); d.setRight(n); BinaryTree person1 = g; while (person1.right() != BinaryTree.EMPTY) { person1 = person1.right(); // right branch is mother System.out.println(person1.value()); // value is name }

33 11.3 实例：符号树 Java语言包含有二元操作组成的数学表达式。如表达式：R = 1 + (L-1)*2，包含了4个操作符（=、+、-和*）和5个数值（R、1、L、1和2 ）。 我们可以用二叉树来表示Java中的数学表达式，这就是符号树。 表达式中的每个数值作为符号树的叶子结点，而操作符作为分枝结点。

34 表达式R = 1 + (L-1)*2的符号树 从优先级最高的叶子结点开始，按照操作符的优先级由高到低逐渐构建符号树的上层结点。 ＝ ＋ R

35 练习 画出表达式R = ((i+j+4) + (L-1))/3的符号树

36 11.6 二叉树的遍历 数据结构的迭代器可以遍历这个数据结构 对于线性的数据结构，我们的遍历很简单，例如单链表，向量等。
11.6 二叉树的遍历 二叉树的遍历指的是沿某条搜索路径访问二叉树，对二叉树中的每个结点访问一次且仅一次。这里的“访问”实际上指的是对结点进行某种操作。 数据结构的迭代器可以遍历这个数据结构 对于线性的数据结构，我们的遍历很简单，例如单链表，向量等。 对于二叉树这样的非线性的数据结构，我们的遍历就显得比较复杂。

37 遍历的种类 DLR LDR LRD DRL RDL RLD 先左后右 先右后左 1、前序遍历 2、中序遍历 3、后序遍历 非空二叉树
P3=6 3 4、层序遍历

38 二叉树的各种迭代器 public class BinaryTree{ … … public Iterator iterator() {
return inorderIterator(); } public AbstractIterator preorderIterator() return new BTPreorderIterator(this); public AbstractIterator inorderIterator() return new BTInorderIterator(this);

39 public AbstractIterator postorderIterator()
{ return new BTPostorderIterator(this); } public AbstractIterator levelorderIterator() return new BTLevelorderIterator(this); … …

40 1、先序遍历二叉树 先序遍历在访问某一结点的任何一个子孙结点之前，都要先访问这个结点，然后才能访问其左右子树。
public AbstructIterator preorderIterator() { return new BTPreorderIterator(this); } 迭代器的构造只有一个参数，就是树根。

41 基于单链表的堆栈 单链表堆栈的特性是：删除和添加操作都集中在单链表的表头（称作栈顶）。 push操作只需向表头（栈顶）添加一个元素即可。
pop操作只需将表头元素删除即可 栈顶 栈底

42 先序遍历的迭代器（BTPreorderIterator.java）
class BTPreorderIterator extends AbstractIterator{ protected BinaryTree root; protected Stack todo; public BTPreorderIterator( BinaryTree root) { todo = new stackList(); this.root = root; reset(); } public void reset() todo.clear(); if( root ! = null) todo.push(root);

43 public boolean hasNext()
{ return !todo.isEmpty(); } public Object get() return ((BinaryTree)todo.getFirst()).value(); public Object next() BinaryTree old = (BinaryTree)todo.pop(); Object result = old.value(); if( !old.right().isEmpty()) todo.push(old.right()); if(!old.left().isEmpty()) todo.push(old.left()); return result;

44 先序遍历迭代器举例 第1步：初始化先序遍历迭代器 A B C D E ^ 1 A ^ count head todo count head
^ count head todo 1 A ^

45 第2步：A出栈，遍历序列为A；C入栈，B入栈 A
D E B 2 count head todo C ^ 第3步：B出栈，遍历序列为AB；E入栈，D入栈 count head todo 3 D E C ^ 第4步：D出栈，遍历序列为ABD； count head todo 2 E C ^

46 迭代器中，二叉树的每一个结点都被压入和弹出堆栈一次，因此，先序遍历二叉树的代价是O(n)。
第5步：E出栈，遍历序列为ABDE； A B C D E count head todo 1 C ^ 第6步：C出栈，遍历序列为ABDEC； count head todo ^ 第7步：堆栈为空，遍历结束； 迭代器中，二叉树的每一个结点都被压入和弹出堆栈一次，因此，先序遍历二叉树的代价是O(n)。

47 递归 递归简单地说就是方法自己调用自己。 由于二叉树的概念是采用递归定义的，因此二叉树的遍历也应该可以采用递归来实现。
二叉树（BinaryTree）是n（n≥0）个结点的有限集合，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

48 先序遍历递归算法 A B D E C A 先序遍历的递归算法： 若二叉树为空二叉树，则算法结束； 否则 先访问根结点， B C
再先序遍历左子树 最后先序遍历右子树 A B D E C

49 2、中序遍历二叉树 D B E A C A 中序遍历的递归算法： 若二叉树为空二叉树，则算法结束； B C 否则 先中序遍历左子树
再访问根结点， 最后中序遍历右子树 D B E A C

50 3、后序遍历二叉树 D E B C A A 中序遍历的递归算法： 若二叉树为空二叉树，则算法结束； B C 否则 先后序遍历左子树
再后序遍历右子树 最后访问根结点， D E B C A

51 4、层序遍历二叉树 层序遍历：就是按照层的顺序遍历结点，首先是第0层（根结点所在地层），接着是第1层结点，一直到最后一层结点。
A B C D E 层序遍历：就是按照层的顺序遍历结点，首先是第0层（根结点所在地层），接着是第1层结点，一直到最后一层结点。 层序遍历需要借助队列才能实现。 A B C D E

52 遍历的总结 前序遍历序列：ABDEC 中序遍历序列： DBEAC 后序遍历序列： DEBCA 层序遍历序列： ABCDE A B C D E
前序遍历序列中的第一个元素一定是整个二叉树的根结点 后序遍历序列中的最后一个元素也一定是整个二叉树的根结点

53 思考题 先序 中序 后序 ABDCE BDAEC CBEDAFIGH CEDBIFHGA
已知一个二叉树的前序遍历序列和中序遍历序列，能否唯一决定一个二叉树？如果能，请画出这个二叉树，并给出它的后序遍历序列。 已知一个二叉树的后序遍历序列和中序遍历序列，能否唯一决定一个二叉树？如果能，请画出这个二叉树，并给出它的前序遍历序列。 已知一个二叉树的前序遍历序列和后序遍历序列，能否唯一决定一个二叉树？如果不能，请举例证明。 先序 中序 后序 ABDCE BDAEC CBEDAFIGH CEDBIFHGA

54 思考题解答 先序 中序 后序 ABDCE BDAEC A A （B,D） （E,C） （B,D） （E,C） B C A （B,D）

55 先序 中序 后序 CBEDAFIGH CEDBIFHGA

56 11.7 二叉树的特性及方法 求根结点root() 求深度depth() 求高度height () 求大小size()
11.7 二叉树的特性及方法 二叉树的定义是递归的，因此，很多的二叉树的实现都可以用递归来实现. A B C D E 求根结点root() 求深度depth() 求高度height () 求大小size()

57 判断一个树是否为满树 空二叉树是不是满树？ 左右子树的高度不一样是不是满树？ 左右子树的满能否决定整个树是满树？ A B C D E
public boolean isFull( ) { if ( isEmpty() ) return true; if(left().height()!= right().height()) return false; return left().isFull() && right().isFull(); }

58 满二叉树特性1 一棵深度为k（k>=0）且有2k+1-1个结点的二叉树称为满二叉树。
通过判断结点的数目也可以判断一个二叉树是否是满二叉树。 public boolean isFull(){ int h = depth(); int s = size(); return s == (1 << (h + 1)) -1; } 如果树的深度k大于100,则整数会溢出，

59 满二叉树特性2、3 一个高h（h>= 0）的满二叉树总共有2h个叶结点。 一个满二叉树的分支结点数量比叶结点少1。 A B C D E
F G

60 树的带权路径长度 1．树的路径长度：从树根到树中每一结点的路径长度之和。
2．树的带权路径长度(Weighted Path Length of Tree，简记为WPL) 结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。 结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。 树的带权路径长度：定义为树中所有叶结点的带权路径长度之和，通常记为：

61 wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。两者的乘积即为结点ki的带权路径长度。
A B K3 K1 K2 w1 l1 其中： n表示叶子结点的数目 wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。两者的乘积即为结点ki的带权路径长度。

62 霍夫曼树（或哈夫曼树，huffman tree）
在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为霍夫曼树。

63 【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树（还有许多棵），它们的带权路径长度分别为：
(a)WPL=7*2+5*2+2*2+4*2=36 (b)WPL=7*3+5*3+2*1+4*2=46 (c)WPL=7*1+5*2+2*3+4*3=35 其中(c)二叉树的WPL最小，可以验证，它就是霍夫曼树。

64 注意： 霍夫曼树中，权越大的叶子离根越近； 霍夫曼树的形态不唯一，但WPL一定是最小 。

65 霍夫曼算法 霍夫曼首先给出了对于给定的叶子数目及其权值构造霍夫曼树的方法，故称其为霍夫曼算法。其基本思想是：
根据给定的n个权值wl，w2，…，wn构成n棵二叉树的森林F={T1，T2，…，Tn}，其中每棵二叉树Ti中都只有一个权值为wi的根结点，其左右子树均空。（为方便在计算机上实现算法，一般还要求对Ti的权值Wi进行升序排列。） 在森林F中选出两棵根结点权值最小的树，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子，将这两个孩子的权值之和作为新树根的权值。 对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是霍夫曼树。 

66 举例 F= F= 构造叶结点的权为： 5 、 2、 7 、 3、5的霍夫曼树。并计算带权路径长度WPL。 初始化 第1次合并 2 3 5 7

67 2 3 5 7 F= 10 第2次合并 2 3 5 7 F= 10 12 第3次合并

68 F= 第4次合并 WPL=2×3＋3×3＋5×2＋5×2＋7×2＝49 所有分支结点权值之和：22＋10＋12＋5＝49
WPL= huffman树的所有分支结点权值之和

69 霍夫曼树小结 当有n个权值（相应的霍夫曼树中有n个叶子）时，共需合并多少次？ 答：n-1次
每合并一次，产生多少个分支结点？最后得到的霍夫曼树共有多少个结点？ 答：1个，2n-1个 霍夫曼树中有没有度为1的结点？ 答：没有

70 建议每完成一次合并后对森林F中的所有二叉树按照根的权值进行排序。
算法中要求选取根结点权值最小的两颗二叉树作为左右子数构造一颗新的二叉树，并没有要求哪一颗作左子树，哪一颗作右子树。但实现算法的时候必须把两者顺序定下来，建议权值小的作左子树，大的作右子树。 如果有多个二叉树的根权值相等，建议选择前两个进行合并。

71 作业 对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的霍夫曼树（给出构造过程），并计算它的带权路径长度WPL。

72 编码方案讨论 编码和解码 编码：将文件中的每个字符均转换为一个惟一的二进制位串。 解码：将二进制位串转换为对应的字符。 1、等长编码方案
2、变长编码方案 ASCII编码 Unicode编码 专用等长编码

73 1、等长编码方案 等长编码方案将给定字符集C中每个字符的码长固定为：[ log2|C| ]，|C|表示字符集的大小。如：
ASCII编码对每个字符采用8位二进制编码 Unicode编码对每个字符采用16位二进制编码 例如：语句：If a woodchuck could chuck wood！一共由32个字符组成（包括空格和标点符号）。 如果每个字符采用Unicode编码，一共需要多少位？ 答：32×16＝512位。 如果每个字符采用ASCII编码，一共需要多少位？ 答：32×8＝256位。 但实际上上述的字符创中只有13个不同的字符，采用4位表示足已。一共需要多少位？ 答：32×4＝128位。

74 2、变长编码方案 每个字符的编码长度不固定，一般的做法是将频度高的字符编码编成短码，将频度低的字符编成长码。
例如：语句：If a woodchuck could chuck wood！采用变长编码，如右图所示：

75 等长、变长编码对比 从这个例子可以看出，变长编码可以减少整句话所占的位数，从而节省存储空间，加快数据的传输。
但等长编码解码时很方便，不会出现解码歧义问题。而变长编码就有可能会出现解码歧义问题 产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分（称为前缀）相同。  【例】设E、T、W分别编码为00、01、0001，则解码时无法确定信息串0001是ET还是W。

76 霍夫曼编码 因此对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符编码的前缀。
我们用霍夫曼树可以实现满足这种要求的编码，并且用这样的编码可以达到最佳的压缩效果。 我们称这种编码为霍夫曼编码。相应的压缩技术为霍夫曼压缩技术

77 霍夫曼编码实现 具体做法： （1）用字符ci作为叶子，频率fi做为叶子ci的权，构造一棵霍夫曼树，并将树中左分支和右分支分别标记为0和1； （2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为霍夫曼编码。 思考： （1）为什么霍夫曼编码不会产生解码歧义问题？ （2）为什么霍夫曼压缩能达到最佳的压缩效果？

78 举例 F= F= b d a e c 初始化 b d 1 a e c 第1次合并
已知某字符串中共有5种字符，分别为： a（5） 、 b（2）、c（7）、d（3）、e（5），括号中的数字代表各种字符的出现次数。求他们的霍夫曼编码。 2 3 5 7 F= b d a e c 初始化 2 3 5 7 F= b d 1 a e c 第1次合并

79 2 3 5 7 F= 10 1 e c b d a 第2次合并 2 3 5 7 F= 10 12 1 e c b d a 第3次合并

80 F= 第4次合并 1 a e c b d 2 3 5 7 10 12 22 各个字符的霍夫曼编码分别是： a:01 b:000 c:11
1 b d e c a 第4次合并 各个字符的霍夫曼编码分别是： a:01 b:000 c:11 d:001 e:10

81 小结 树是一种非线性结构。 树的遍历，先序，中序，后序，层序 树的递归属性。 霍夫曼树及其应用