第5章 树和二叉树.ppt

电文中共使用八种字符，如果按一般方法对其进行编码，则最少需要3位码长，如：A(000)，B(001)，C(010)，D(011)，E(100)，F(101)，G(110)，H(111)，假设电文中共100个字符，按其出现频率则该电文的码长为：3*100＝300。 若按哈夫曼编码A：01010（5位）B：00（2位）C：0100（4位）D：111（3位）E：011（3位）F：10（2位）G：01011（5位）H：110（3位），按其出现频率则该电文的码长（即带权路径长度WPL）为： 4*5+30*2+8*4+9*3+13*3+22*2+3*5+11*3＝270， 明显的压缩了30位码长。 * 1、定义和性质 2、存储结构 3、遍历 4、线索化：线索树 顺序结构 链式结构 二叉链表 三叉链表 树 二叉树 森林 中序遍历 后序遍历 先序遍历 霍夫曼树 霍夫曼编码 小结 * 1. 掌握二叉树的基本概念、性质和存储结构 2. 熟练掌握二叉树的前、中、后序遍历方法 3. 了解线索化二叉树的思想 4. 熟练掌握：霍夫曼树的实现方法、构造霍夫曼编码的方法 5. 了解：森林与二叉树的转换，树的遍历方法 小结 进阶任务 （完成每任务加经验值100） 教材P123页，1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。 A．唯一的 Ｂ．有多种 C．有多种，但根结点都没有左孩子 Ｄ．有多种，但根结点都没有右孩子 （2）由3 个结点可以构造出多少种不同的二叉树？（ ） A．2 B．3 C．4 D．5 （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）。 A．250 B． 500 C．254 D．501 进阶任务 （完成每任务加经验值100） 教材P123页，1．选择题 （4）一个具有1025个结点的二叉树的高h为（ ）。 A．11 B．10 C．11至1025之间 D．10至1024之间 （5）深度为h的满m叉树的第k层有（ ）个结点。(1=k=h) A．mk-1 B．mk-1 C．mh-1 D．mh-1 （6）利用二叉链表存储树，则根结点的右指针是（ ）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 进阶任务 （完成每任务加经验值100） 教材P123页，1．选择题 （7）对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 （8）在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（ ） A．41 B．82 C．113 D．122 （9）在下列存储形式中，（ ）不是树的存储形式？ A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 进阶任务 （完成每任务加经验值100） 教材P123页，1．选择题 （10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）。 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 （11）某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A．空或只有一个结点 B．任一结点无左子树 C．高度等于其结点数 D．任一结点无右子树 （