《[工学]计算机软件技术基础课件-第2章 常用数据结构及其运算2非线性》由会员分享，可在线阅读，更多相关《[工学]计算机软件技术基础课件-第2章 常用数据结构及其运算2非线性（69页珍藏版）》请在金锄头文库上搜索。
1、,概述,图,查找,排序,2.6,2.8,2.7,第二章 常用的数据结构及其运算,概述,2.1,2.2,2.3,2.4,2.5,树与二叉树,数组,栈与队列,线性表,2.5 树与二叉树,数据结构： 线性结构：（线性表、栈、队列等等。） 非线性结构：至少存在一个数据元素有不止一个直接前驱或直接后继（树、图）。,2.5树与二叉树,一、树的定义基本术语,树是由 n(n=0)个数据元素组成的有限集合（记为T），对于任意一棵树T： （1） 存在唯一一个称为根的数据元素； （2） 当 n1时其它数据元素可分为m(m0)个互不相交的有限集合 T1，T2，Tm，而其中每个集合Ti（i=1，2，m）本身又是一棵树，
2、并称Ti是根的子树。,2.5树与二叉树,树的结点(node) ：树中的数据元素和指向其子树的分支。 结点的度(degree)：一个结点的子树的个数称为该结点的度，度为0 的结点称为叶结点 树的度：树的所有结点中最大的度称为树的度 。,结点的层次(level)：根结点为第一层，其他任何结点的层数等于它的父结点的层数加1。 树的深度( depth ) ：树的所有结点中最大的层次称为树的深度或高度。,森林(Forest ) ：m （m0）棵互不相交的树的集合。,一、树的定义基本术语,2.5树与二叉树,二、二叉树及其性质,1、二叉树的定义,二叉树：是结点数为0或每个结点最多只有左右两棵子树的树。二叉树
3、是一种特殊的树，它的特点是： 每个结点最多只有两棵子树，即不存在度大于2的结点。 是有序树，子树有左右之分，不能颠倒。思考：二叉树和度为2的树有何区别？,2.5树与二叉树,2、二叉树的基本性质,【性质1】第i层上最多有2i-1(i=1)个结点,证明： 当i=1，即根结点，结点数为21-1=1，成立； 假设第i-1层上的结点数最多有2(i-1)-1=2i-2个，则： 由于二叉树中每一个结点度数最大为2，故第i层上结点数至多为i-1层上结点数的2倍，即22i-2=2i-1。 由归纳法，性质得证。,二、二叉树及其性质,2.5树与二叉树,【性质2】深度为h的二叉树最多有2h-1个节点,证明： 利用性质
4、(1)的结论，在深度为h的二叉数中至多含有的结点数：,二、二叉树及其性质,2.5树与二叉树,【性质3】二叉树中，若有n0个叶子结点， n2个度为2的结点，则必有n0=n2+1,证明：设n1为度为1的结点数，则总结点数n为：n=n0+n1+n2 在二叉树中除根结点外，其他n-1个结点都是度为1或度为 2 的结点的孩子，度为1的结点有一个孩子，度为 2 的结点有 2个孩子，因而又有： n-1 =n1+2n2 以上两式联立.即得 n0=n2+1,二、二叉树及其性质,2.5树与二叉树,3、几种特殊形式的二叉树,(1)满二叉树：深度为k, 结点个数为2k-1 的二叉树。,每一层的结点数都达到最大值. 没
5、有度为1的结点（只有度为0和2的结点），叶子都分布在最后一层上。 编号： 自上而下，自左至右。,二、二叉树及其性质,k4 n24-1=15,2.5树与二叉树,(2)完全二叉树,如果一棵有n个结点的二叉树，按与满二叉树相同的方式对结点进行编号,若树中n个结点和满二叉树1n编号完全一致，则称该树为完全二叉树。,二、二叉树及其性质,2.5树与二叉树,完全二叉树的特点,前k-1层（k为深度）是满二叉树。 结点数n满足：2k-1-11,则i的双亲是i/2 。(2) 若2i n，则i的左孩子为2i；否则(2in)i无左孩子。(3) 若2i1 n,则i的右孩子为2i1；否则(2i+1n)i无右孩子。,二、二
6、叉树及其性质,证明：略。,二叉树这样的非线性结构能否用顺序存储结构?,三、二叉树的存储结构,顺序存储结构,三、二叉树的存储结构,BT(3)=的双亲为3/21,即在BT(1)。 其左孩子为BT(2i)=BT(6) 其右孩子为BT(2i+1)=BT(7),用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴涵着结点之间的关系。,顺序存储结构,结论：顺序存储机构适合于完全二叉树，对于一般的二叉树，可能会造成存储空间的浪费。,三、二叉树的存储结构,顺序存储结构,三、二叉树的存储结构,例如：深度为k，且只有k个结点的右单枝树，需要2k-1个存储单元，有2k-1-k个单元被浪费。,2
7、.5树与二叉树,主要有：二叉链表、三叉链表、线索链表,三、二叉树的存储结构,链式存储结构,二叉链表,2.5树与二叉树,三、二叉树的存储结构,链式存储结构,*【性质6】具有n个结点的二叉链表中，有n+1个空链域 。（证明略）,6个结点，7个空链域,2.5树与二叉树,三、二叉树的存储结构,链式存储结构,三叉链表,2.5树与二叉树,四、二叉树的遍历,遍历二叉树： 按照一定的规律，对二叉树的每个结点访问且仅访问一次的处理过程。,遍历的次序： 设二叉树的根结点为D、左子树为L、右子树为R， 并规定先左后右，则遍历次序有三种：先序遍历（根左右）： DLR中序遍历（左根右）： LDR后序遍历（左右根）： L
8、RD,1、先序遍历,算法思想： 访问根结点； 先序遍历左子树； 先序遍历右子树。,四、二叉树的遍历,void PreOrder (nodetype *bt) if (bt = NULL) return；Visit (bt-Data);if (bt-LChild != NULL) PreOrder（bt- LChild);if (bt-RChild != NULL) PreOrder(bt-RChild); ,算法描述：,例：对图所示二叉树, 先序遍历次序为：A B D G E C F H,四、二叉树的遍历,2、中序遍历,算法思想： 中序遍历左子树； 访问根结点； 中序遍历右子树,四、二叉树的遍
9、历,void InOrder (nodetype *bt) if (bt = NULL) return;if (bt-LChild != NULL) InOrder(bt-LChild);Visit (bt-Data);if(bt-RChild != NULL) InOrder(bt-RChild); ,算法描述：,例：对右图所示二叉树, 中序遍历次序为：D G B E A F H C,四、二叉树的遍历,3、后序遍历,算法思想 后序遍历左子树； 后序遍历右子树； 访问根结点,四、二叉树的遍历,void PostOrder (nodetype *bt) if (bt = NULL) return
10、;if (bt-LChild != NULL) PostOrder（bt- LChild);if (bt-RChild != NULL) PostOrder(bt-RChild);Visit (bt-Data); ,算法描述：,例：对右图所示二叉树, 后序遍历次序为：G D E B H F C A,四、二叉树的遍历,后序遍历次序为：G D E B H F C A,四、二叉树的遍历,中序遍历次序为：D G B E A F H C,先序遍历次序为：A B D G E C F H,2.5树与二叉树,五、哈夫曼树,路径长度 (Path Length) 两个结点之间的路径长度是连接两结点的路径上的分支数
11、。 树的路径长度是各结点到根结点的路径长度之和。,2.5树与二叉树,带权路径长度 ( Weighted Path Length, WPL ),二叉树的带权路径长度是树的各叶结点所带的权值 wi 与该结点到根的路径长度 li 的乘积的和。,五、哈夫曼树,2.5树与二叉树,WPL = 2*2+ WPL = 2*1+ WPL = 7*1+4*2+5*2+ 4*2+5*3+ 5*2+2*3+7*2 = 36 7*3 = 46 4*3 = 35,五、哈夫曼树,2.5树与二叉树,哈夫曼树 ：带权路径长度最小的二叉树。,五、哈夫曼树,完全二叉树不一定是哈夫曼树权值越大的结点离根越近哈夫曼树不唯一，但WPL值
12、一定相等。,2.5树与二叉树,(1) 由给定的 n 个权值 w0, w1, w2, , wn-1，构造具有 n 棵二叉树的森林 F = T0, T1, T2, , Tn-1 ，其中每棵二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。,(2) 重复以下步骤, 直到 F 中仅剩下一棵树为止： 在 F 中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F。,哈夫曼树的构造：,五、哈夫曼树,F : 7 5 2 4,F : 7 5 6,F : 7 11
13、,7,5,2,4,初始,合并2 4,F : 18,11,7,5,2,4,6,合并5 6,5,合并7 11,2,7,4,6,11,18,2.5树与二叉树,五、哈夫曼树,考试成绩分布表,2.5树与二叉树,五、哈夫曼树,哈夫曼树的应用判定树,哈夫曼树的应用判定树,WPL = 0.10*1+0.15*2+0.25*3+0.35*4+0.15*4= 3.15,2.5树与二叉树,五、哈夫曼树,最佳判定树,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,WPL = 0.10*3+0.15*3+0.25*2+0.35*2+0.15*2= 0.3+0.
14、45+0.5+0.7+0.3 = 2.25,2.5树与二叉树,五、哈夫曼树,主要用途是实现数据压缩。,设给出一段报文： CAST CAST SAT AT A TASA字符集合是 C, A, S, T ，各个字符出现的频度(次数)是 W 2, 7, 4, 5 。若给每个字符以等长编码A : 00 T : 10 C : 01 S : 11 则总编码长度为 ( 2+7+4+5 ) * 2 = 36.,2.5树与二叉树,五、哈夫曼树,哈夫曼树的应用哈夫曼编码,若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为 2/18, 7/18, 4/18, 5/18 ,化整为 2, 7, 4, 5 。以它们为各叶结点上的权值, 建立哈夫曼树。左分支赋 0，右分支赋 1，得哈夫曼编码(变长编码)。,
