《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－6》由会员分享，可在线阅读，更多相关《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－6（41页珍藏版）》请在金锄头文库上搜索。
1、1,计算机软件技术基础,课件,第一章 数据结构,第二章 操作系统,第三章 软件工程,第四章 数据库,制作者：张选芳 Email: 电话:5182508,2,第一章 数据结构,第一单元,第二单元,第三单元,第四单元,第五单元,第六单元,第七单元,第八单元,3,树、森林与二叉树的转换,第六单元,第一章 数据结构,4,1.3.3 二叉树的遍历,所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。 访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。 “访问”的意思对结点施行某些操作。 例：输入结点的信息、修改
2、结点的数据值等。（但要求这种访问不破坏它原来的数据结构）,遍历的规则 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，对于任一给定结点，可以按某种次序执行三个操作： （1）访问结点本身(N)， （2）遍历该结点的左子树(L)， （3）遍历该结点的右子树(R)。 以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。, 设访问根结点记作 N 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 NLR 镜像 NRL 中序 LNR 镜像 RNL 后序 LRN 镜像 RLN,5,一遍历算法 (Inorder Traver
3、sal) 1中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)访问根结点； (3)遍历右子树。,例：表达式语法树 遍历结果: a + b * c - d - e / f,表达式 a + b * (c d ) e / f 对应的语法树,6,采用二叉链表作为存储结构，则中序遍历算法可描述为： void InOrder(BinTree T) if(T) / 如果二叉树非空 InOrder(T-lchild)； printf(“c“，T-data) / 访问结点 InOrder(T-rchild); / InOrder,7,例：表达式语法树 遍历结果 - + a
4、* b - c d / e f,表达式 a + b * (c d ) e / f 对应的语法树,2先序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： 前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 (1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。,8,例：表达式语法树 遍历结果 a b c d - * + e f / -,表达式 a + b * (c d ) e / f 对应的语法树,3后序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： 后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 (1)遍历左子树； (2)遍历右子树； (3)访问
5、根结点。,9,二遍历序列 1遍历二叉树的执行踪迹,图1-50遍历二叉树的搜索路线,10,例:右图,得到的中序序列为： D B A E C F,2.遍历序列 (1)中序序列 中序遍历二叉树时，对结点的访问次序为中序序列。,(2)先序序列 先序遍历二叉树时，对结点的访问次序为先序序列。 例:上图，得到的先序序列为： A B D C E F,11,三 二叉链表的构造 1. 基本思想 基于先序遍历的构造，即以二叉树的先序序列为输入构造。,(3)后序序列 后序遍历二叉树时，对结点的访问次序为后序序列。,例:右图, 得到的后序序列为： D B E F C A,例: 建立上图所示二叉树，其输入的先序序列是：
6、ABD CE F 。,12,2 构造算法 假设虚结点输入时以空格字符表示，相应的构造算法为: void CreateBinTree (BinTree *T) /构造二叉链表。T是指向根指针的指针, /故修改*T就修改了实参(根指针)本身 char ch； if(ch=getchar()=) *T=NULL； /读入空格，将相应指针置空 else,13, /读入非空格 *T=(BinTNode *) malloc(sizeof(BinTNode)； /生成结点 (*T)-data=ch； CreateBinTree(&(*T)-lchild)； /构造左子树 CreateBinTree(&(*T
7、)-rchild)； /构造右子树 ,14,1.3.4 树、森林与二叉树的转换 一树、森林到二叉树的转换 1将树转换为二叉树 左子女-右兄弟表示法 在所有兄弟结点之间加一连线； 对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。 例: 图151(a)所示的树可转换为图151(c)所示的二叉树。,15,图1-51 树转换为二叉树,16,2将一个森林转换为二叉树 具体方法是： 将森林中的每棵树变为二叉树； 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。 例如图152中,(a)中包含三棵树的森林可转换为(c)的二叉树。
8、,17,森林与二叉树的转换,森林与二叉树的对应关系,图1-52 森林转换为二叉树,18,二二叉树到树、森林的转换,(a),(b),图1-53 将图1-52(c)中二叉树转换为森林,19,1.3.5 哈夫曼树和哈夫曼编码 路径长度 (Path Length) 两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是从树的根结点到树中各个结点的路径长度之和。,具有不同路径长度的二叉树,例：如图a所示的二叉树中，根结点到其它各结点的路径长度分别为0 , 1 , 1 , 2 , 2, 2 , 2 , 3。 该树的路径长度：PL = 0+1+1+2+2+2+2+3 = 13 如图b所示的二叉树
9、的路径长度： PL = 0 + 1+1+2+2+2+3+3=14,20,一哈夫曼树 权 在实际应用中，树中的结点常被赋予 一个有某种意义的数，该数我们称为结点 的权。,带权路径长度 ( Weighted Path Length, WPL ) 树的带权路径长度是树的各叶结点所带 的权值与该结点到根的路径长度的乘积之 和。,21,具有不同带权路径长度的扩充二叉树,图a：WPL = 2*(2+4+5+7) = 36 图b：WPL = 2+2*4+3*(5+7) = 46 图c：WPL = 7+2*5+3*(2+4) = 35,图1-54带权路径长度不同的二叉树,22,哈夫曼树(Huffman Tre
10、e) 树的带权路径长度WPL最小的称为最优二叉树, 通常称为哈夫曼树。 例: 给定4个叶子结点，其权分别为7, 5,2和4。,23,霍夫曼算法 (1) 由给定的 n 个权值w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林F = T0, T1, T2, , Tn-1 ，其中每一棵扩充二叉树 Ti 只有一个带有权值 wi 的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉
11、树。 把新的二叉树加入 F。,24, 霍夫曼树的构造过程,严格二又树 哈夫曼树没有度数为1的分支结点，一个结点若没有左孩子，那么肯定是叶子，称之为严格二又树。,图1-55 霍夫曼树的构造过程,25,二哈夫曼编码 编码 在数据通信中，经常需要把文字(英文或中文)转换成二进制位0，1组成的代码串，然后发送出去。这一过程称为编码。 译码 在接收方收到一系列0，1组成的代码串后，再把它们还原成文字，这一过程称为译码。,26,1问题的提出 (1)编码的长短 等长编码 在英文通信中，电文由26个英文字母组成，当采用等长编码时，每个英文字母可用5个二进制位表示。上述编码方法就是等长编码。 例:A, B, C
12、, D的编码分别为000，001，010和 011。这样，电文“ACDACAB”的二进制编码串为： 000010011000010000001，即总的码长为21位。,27,不等长编码 在上面的例子里，由于电文中A和C出现的次数较多，可以再设计一套编码方案，令A,B,C,D的编码分别为0, 01, 1, 11。此时电文“ACDACAB”的二进制代码串 为：011101001 (2)译码的唯一性 译码的唯一性也是非常重要的。 前缀码 译码的唯一性,要求任何一个字符的编码,不能是另一个编码的前缀。这种编码称为前缀码。,28,2哈夫曼编码 (1)哈夫曼编码的特点 电文的总长度最短 采用哈夫曼树就可以构
13、造使电文的总长度最短的编码方案。 前缀码 利用哈夫曼树，不仅能使电文的总长度最短，而且能构造出前缀码。 (2)哈夫曼编码的步骤 假设电文中使用n种字符，每种字符在电文中出现的次数为Wi(i1 n)。,以Wi作为哈夫曼树叶子结点的权值，用哈夫曼算法构造出哈夫曼树。规定树中每个结点的左分支代表“0”，右分支代表“l”。则从根结点到代表该字符的叶结点之间，沿途路径上的分支组成的“0”或“l”代码串就是该字符的编码，称之为哈夫曼编码,29,具体步骤是： 在n个字符中，选出两个权值最小的字符作为左右子树，构造一棵新的二叉树，该新的二叉树的根结点的权值为其左右子树权值之和； 在n中删去已用过的左右子树(两
14、个字符)，加入该新的二叉树； 重复和，直到n个字符中只有一棵树为止，该树就是哈夫曼编码树。 (3)哈夫曼编码的例子,30,例: 利用哈夫曼树对“it is a tree”这个简单 英文句子进行编码， 句子中有的字符： i，t，口，s，a，r，e。 七个字符的权值分别为： (2，2，3，1，1，1，2)。构造的哈夫曼树如图153所示。,31,(2),(3),32,(4),(5),33,(6),0,1,0,1,0,1,0,1,0,1,0,1, i，t，口，s，a，r，e的前缀码 01l，10，11，001，0000，0001，010。,34,说明： 圆圈结点内的数字代表该字母的权值。 i，t，口，
15、s，a，r，e的前缀码 分别为： 01l，10，11，001，0000，0001，010。 电文“it is a tree”的二进制代码串为： 01110l101100111000011100001010010。,011 10 l1 011 001 11 0000 11 10 0001 010 010 i t 口 i s 口 a 口 t r e e,35,1.3.6 二叉排序树 二叉排序树是一种特殊结构的二叉树，它作为一种表的组织手段，通常称为树表，可以作为排序和查找的方法之一。 一二叉排序树的定义 二又排序树或者是空树，或者是具有下述性质的二又树： 其左子树上所有结点的数据值均小于根结点的数据值，右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右于树又各是一棵二又排序树。图157所示就是一棵二叉排序树。,36,在二又排序树中，若按中序遍历就可以得到由小到大的有序序列，如上图中的二叉排序树，中序遍历可得有序序列(2，3，4，8，9，9，10，13，15，18，21)。,37,二二叉排序树的生成 对任意的一组数据元素序列R1 ,R2 , ,Rn, 生成一棵二又排序树的过程为： 令R1为二叉排序树的根结点。 若R2R1,令R2为R1的左子树的根结点; 否则R2为R1的右子
