第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料) 方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉树，再用中序遍历方式打印每个 结点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫 曼编码。 方案三：哈夫曼编/译码器的设计与实现
1 方案一：二叉树的建立和遍历 具体内容：先生成一棵二叉树，再用中序遍历方式打印每个 结点值，并统计其叶子结点的个数。 方案二：哈夫曼树的建立和编码器的实现 具体内容：先生成一棵哈夫曼树，再打印各字符对应的哈夫 曼编码。 方案三：哈夫曼编/译码器的设计与实现 第二次上机内容预告： （三个方案由易到难，可自选，参见自测题集实验二资料）
第6章树和二叉树 CTree Binary Tree) 6.1树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 Huffman树及其应用 2
2 第6章 树和二叉树 （Tree & Binary Tree） 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 Huffman树及其应用
先介绍二叉树的典型应用 平衡树 特点：所有结点左右子树深度差s1 排序树 特点：所有结点“左小右大” 字典树 由字符串构成的二叉排序树 判定树 特点：分支查找树（例如12个球如何只称3次 便分出轻重) 带权树 特点：路径带权值（例如长度） 最优树 是带权路径长度最短的树，又称Huffman树， 用途之一是通信中的压缩编码。 3
3 先介绍二叉树的典型应用 平衡树—— 排序树—— 字典树—— 判定树—— 带权树—— 最优树—— 由字符串构成的二叉排序树 特点：分支查找树（例如12个球如何只称3次 便分出轻重） 特点：路径带权值（例如长度） 是带权路径长度最短的树，又称 Huffman树， 用途之一是通信中的压缩编码。 特点：所有结点左右子树深度差≤1 特点：所有结点“左小右大
什么是平衡二叉树（又称AVL树） 性质：所有结点左、右子树深度之差的绝对值≤1 若定义结点的“平衡因子”BF=左子树深度-右子树深度 则：平衡二叉树中所有结点的BF∈[-1,0,1] 例 判断下列二叉树是否AVL树？ (a)平衡树 (b)不平衡树
4 什么是平衡二叉树（ 又称AVL 树）？ 性质： 所有结点左、右子树深度之差的绝对值≤ 1 若定义结点的“平衡因子” BF = 左子树深度 – 右子树深度 则：平衡二叉树中所有结点的BF∈[ -1, 0, 1 ] (a) 平衡树 (b) 不平衡树 例：判断下列二叉树是否AVL树？ 0 0 0 1 1 -1 -1 2 0 0 0 1 -1
什么是二叉排序树？ 一一一或是一棵空树；或者是具有如下性质的非空二叉树： （1)左子树的所有结点均小于根的值： (2)右子树的所有结点均大于根的值： (3)它的左右子树也分别为二叉排序树。 例：下列2种图形中，哪个不是二叉排序树？ (a (b) 想一想：对它中序遍历之后是什么效果？
5 什么是二叉排序树？ （a） （b） 例：下列2种图形中，哪个不是二叉排序树？ -或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。 想一想：对它中序遍历之后是什么效果？ 7 1 4 10 2 6 5 3 9 8 5 10 2 1 6 4 7 3 9 8