树和二叉树作业PPT学习教案

1、会计学1 树和二叉树作业树和二叉树作业 1）将如图所示的二叉树进行）将如图所示的二叉树进行 中序线索化。中序线索化。 2 试找出分别满足下面条件的所有二叉树：试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同；）前序序列和中序序列相同； （2）中序序列和后序序列相同；）中序序列和后序序列相同； （3）前序序列和后序序列相同；）前序序列和后序序列相同； （4）前序、中序、后序序列均相同）前序、中序、后序序列均相同 3 假定用于通信的电文仅由假定用于通信的电文仅由8个字母个字母c1, c2, c3, c4, c5, c6, c7, c8组成组成, 各字母在电文中出现的频率分别为各字

2、母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。 试为这试为这8个字母设计不等长个字母设计不等长Huffman编码编码, 并给出该电文的总码数并给出该电文的总码数 作业：作业：2 1 3 9 112 5 13 10 6 7 12 8 4 15 14 第1页/共9页 作业：作业：1 1）顺序存储：）顺序存储： 树的深度是树的深度是7 数组存储单元大小数组存储单元大小 是是27-1=127 叶子结点叶子结点 L,FGM J A B C D E F L G H I J M K 1 2 4 5 8 9 10 11 17 22 44 45 91 第2页/共9页 0 1 2

3、 3 4 5 678 91011 . 91 126 A B0E C 0 0 K F G D J . H L MI A B E C D G K F J 0 0 第3页/共9页 遍历序列遍历序列 先序：先序：ABEKLFCGDHMIJ 中序中序 KLEFBGCMHIJDA 后序后序 LKFEGMJIHDCBA 2统计出给定二叉树中叶子结点的数目统计出给定二叉树中叶子结点的数目 （1）顺序存储结构的实现）顺序存储结构的实现 int CountLeaf1（SqBiTree bt，int k） /*一维数组一维数组bt2k-1为二叉树存储结构，为二叉树存储结构，k为二叉树深度，函数值为叶子数。为二叉树深

4、度，函数值为叶子数。*/ total=0; for(i=1;i(2k-1)/2) total+; return(total); 第4页/共9页 （2）二叉链表存储结构的实现）二叉链表存储结构的实现 int CountLeaf2（BiTree bt） /*开始时，开始时，bt为根结点所在链结点的指针，为根结点所在链结点的指针， 返回值为返回值为bt的叶子数的叶子数*/ if (bt=NULL) return(0); if (bt-lchild=NULL return(CountLeaf2(bt- lchild)+CountLeaf2(bt-rchild); A B F G EC D H I J

5、3)重建二叉树重建二叉树 第5页/共9页 作业：作业：2 1 3 9 112 5 13 10 6 7 12 8 4 15 14 1）转化的二叉树）转化的二叉树 如图如图 二叉树中序遍历序列：二叉树中序遍历序列：3 4 2 8 6 7 5 1 10 9 11 15 13 14 12 NULL NULL 第6页/共9页 2 试找出分别满足下面条件的所有二叉树：试找出分别满足下面条件的所有二叉树： （1）前序序列和中序序列相同；）前序序列和中序序列相同； （2）中序序列和后序序列相同；）中序序列和后序序列相同； （3）前序序列和后序序列相同；）前序序列和后序序列相同； （4）前序、中序、后序序列均相

6、同）前序、中序、后序序列均相同 解：解： （1）空二叉树或任一结点均无左子树的非空二叉树）空二叉树或任一结点均无左子树的非空二叉树 （2）空二叉树或任一结点均无右子树的非空二叉树）空二叉树或任一结点均无右子树的非空二叉树 （3）空二叉树或仅有一个结点的二叉树）空二叉树或仅有一个结点的二叉树 （4）空二叉树或仅有一个结点的二叉树）空二叉树或仅有一个结点的二叉树 第7页/共9页 3 假定用于通信的电文仅由假定用于通信的电文仅由8个字母个字母c1, c2, c3, c4, c5, c6, c7, c8组成组成, 各字母在电文中出现的频率分别为各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。 试为这试为这8个字母设计不等长个字母设计不等长Huffman编码编码, 并给出该电文的总码数并给出该电文的总码数 C7:36 61 22 C2:25 17 11 C5:10 7 C8:4 C3:3 39 C1:5C4:6 C6:11 100 0 0 0 0 1 1 0 1 1 1 0 1 10 C1: 0100 C2: 10 C3: 0000 C4 0101 C5 001 C6 011 C7 11 C8 0001 电文总码数电文总码数: 0100 1000000101 001 011 11 0001 注意注意:电文总编码形式不唯一电文总编码形式