计算机软件基础课件：非线性数据结构

非线性数据结构《计算机软件基础》01.树和二叉树02.哈夫曼树03.图主要内容04.最小生成树和拓扑排序本章重点难点本章重点：二叉树的遍历；二叉树的性质；哈夫曼树；图的存储结构；图的遍历；图的连通分量和生成树的区别；Kruskal算法；拓扑排序方法。本章难点：二叉树的遍历；Kruskal算法；拓扑排序方法。01树和二叉树1.树的基本概念

树形结构表示方法的多样化a)自然表示法；b)是集合表示法；c)是层次表示法树的基本术语1）结点的度：结点拥有的子树数。2）树的度：树内各结点的度的最大值。3）叶子结点（终端结点）：度为0的结点。4）孩子和双亲结点：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。5）兄弟结点：用一双亲结点的孩子结点互称为兄弟。6）树的高度（深度）：树的层数（根为第1层）2.二叉树

二叉树是一种特殊的树形结构

特点：树中每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左、右之分，其次序不能任意颠倒。a)空树c)右子树为空b)仅有根结点d)左子树为空e)左右子树皆不为空1）树和二叉树的区别树二叉树同一棵树，不同的二叉树2）二叉树的性质

满二叉树：高度为k的二叉树，若具有2k-1个节点，称为满二叉树。完全二叉树：假设二叉树具有n个节点，对二叉树的节点进行编号，若二叉树各节点与深度相同的满二叉树中编号相同的1~n个各节点一一对应，则称为完全二叉树。

3.二叉树的存储结构存储元素，表示关系。可以顺序存储，也可以链式存储。但：存储元素简单，表示关系困难！顺序存储分配连续空间，依次存放树的各个元素。如何依次存放？例如，可约定：从上至下、从左至右将树的节点依次存入连续内存空间。优点：简单缺点：不能很好地表示出关系！123456789abcdefghiabcdeghif123456789链式存储用任意的存储空间，存放数据元素，在存储元素的同时存放其相关元素的地址。二叉链表存储结构的类型定义如下：typedefcharElemType;structbtlnode{ElemTypedata;structbtlnode*lchild,*rchild;};思考：其他链式存储方法？？？4.二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树中各个结点，使得每个结点被访问一次且仅被访问一次。遍历方式：由于元素之间的关系复杂了，按什么样的顺序访问数据元素？人们约定一个原则。深度优先遍历：广度优先遍历1）深度优先遍历：中序遍历其遍历过程为：中序遍历其左子树；访问根节点；中序遍历其右子树。voidInOrderTraversal(BinTreeBT){if(BT){InOrderTraversal(BT->Left);printf(“%d”,BT->Data);InOrderTraversal(BT->Right);}}中序遍历结果序列为：DBGEHACIF2）深度优先遍历：先序遍历voidPreOrderTraversal(BinTreeBT){if(BT){printf(“%d”,BT->Data);PreOrderTraversal(BT->Left);PreOrderTraversal(BT->Right);}}其遍历过程为：访问根节点；先序遍历其左子树；先序遍历其右子树。先序遍历结果序列为：ABDEGHCFI3）深度优先遍历：后序遍历voidPostOrderTraversal(BinTreeBT){if(BT){PostOrderTraversal(BT->Left);PostOrderTraversal(BT->Right);printf(“%d”,BT->Data);}}其遍历过程为：后序遍历其左子树；后序遍历其右子树；访问根节点。后序遍历结果序列为：DGHEBIFCA访问一个元素后，再依次访问其各个后继。对于二叉树，从第1层开始，逐层访问其元素，每一层从左向右。先访问的元素，它们的孩子也先访问！层次序遍历结果序列为：ABCDEFGHI4）广度优先遍历：层序（层次）遍历用队列数据结构辅助来完成层次遍历。例9-6已知一个二叉树的后序遍历和中序遍历结果分别为：DGHEBIFCA和DBGEHACIF，试确定该二叉树。第1步：由后序遍历结果确定整个二叉树根为A，由中序结果确定A的左、右子树中序遍历结果分别为DBGEH和CIF。第2步：确定A的左子树。第3步：确定A的右子树。5.树和森林1）树的存储表示①双亲表示法②孩子表示法③孩子兄弟表示法2)树与二叉树将一棵树转换成二叉树的方法是：①加线。在兄弟之间加一连线。②抹线。对每个结点，除了其左孩子外，去除其与其余孩子之间的关系。③旋转。以树根为轴心，把孩子兄弟表示顺时针旋转45°。3)森林

①将森林中各棵树转换成二叉树。②依次把后一个二叉树连在前一个二叉树根的右子树上。02哈夫曼树1.哈夫曼树的概念路径和路径长度从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。路径上的分支条数称为路径长度。哈夫曼树概念带权路径长度最小的二叉树，也称为最优二叉树。树的路径长度从树的根结点到每一结点的路径长度之和。结点的权：树中结点赋予一个具有某种含义的数值树的带权路径长度：树中所有叶子结点的带权路径长度之和。2.哈夫曼树的构造例9-8

求图中给出的四个权值9、5、2、4的哈夫曼树及带权路径长度WPL。此时，WPL=9*1+5*2+(2+4)*3=37。

同一组权值构造的哈夫曼树不唯一，但WPL相同。权值越大的结点离根结点越近。3.哈夫曼树的性质4.哈夫曼树的应用例9-9

某工厂对其产品质量进行自动检测，并根据检测结果划分产品的质量等级。等级标准如表所示。试设计一个分类算法，根据产品的检测结果d值能快速确定其质量等级。等级EDCBA检测值dd<55≤d<66≤d<77≤d<88≤d百分比0.10.20.350.250.1例9-10

已知一串电文内容如下：AACBDADACBAADCADCADA。试为电文中各字符设计最优的二进制电文编码，即哈夫曼编码。求哈夫曼编码的方法是：①以电文中各字符出现的次数为权值，构造哈夫曼树，该树的叶子结点表示电文中的一个字符。上述电文中A、B、C、D四个字符出现的次数依次为9、2、4、5。所构造的哈夫曼树如图a)所示。

②将哈夫曼树左子树边上置0，右子树边上置1。电文中各字符的哈夫曼编码为：从根到叶子（字符）结点路径上的二进制序列。此树称为哈夫曼编码树，如图b)所示。A——1、B——010、C——011、D——00。利用哈夫曼树为电文中各字符设计最优的二进制电文编码。03图1.图的概念图G由顶点和边组成，G=(V,E)。V是顶点的有穷非空集合，E是边（弧）的有穷集合。1）图

请在图中分别举例：邻接点？度？路径？回路？2.图的存储结构邻接矩阵是用矩阵表示图中各顶点之间的邻接关系和权值，是图的一种顺序存储结构。邻接表是图的一种顺序存储与链式存储结合的存储结构，由单链表组成，每个表头结点对应图中的一个顶点，表结点存放表头结点的邻接点。1）邻接矩阵2）邻接表3.图的遍历深度优先遍历是树的先序遍历，从A顶点出发，先访问A点，再访问A的第1个尚未访问的邻接点B，再访问B的第1个尚未访问的邻接点C，以此类推，直到所有顶点访问完毕。1）深度优先遍历图的广度优先遍历类似于树的按层次序遍历。从图中某顶点A出发，在访问了A之后依次访问A的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，先被访问的顶点其邻接点也先被访问，直至图中所有顶点都被访问到为止。结果不唯一。2）广度优先遍历04最小生成树和拓扑排序1.生成树和最小生成树

1）图的连通分量连通图：如果图中任意两顶点都是连通的。连通分量：无向图的极大连通子图称为连通分量。连通分量的概念包含以下要点：①子图：连通分量应该是原图的子图；②连通：连通分量本身应该是连通的；③极大顶点数：连通子图包含有极大顶点数，即再加入其他顶点将会导致子图不连通；④极大边数：具有极大顶点数的连通子图包含依附于这些顶点的所有边。

3）最小生成树

如果无向连通图的边上带有权值，那么它的生成树中必有一棵边的权值总和最小的生成树，称这棵生成树为最小生成树。当然，对任意一个带权的连通图来说，最小生成树也未必是唯一的。4）Kruskal算法Kruskal算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。基本思路是对一个有n个顶点的连通图G=(V,E)，令最小生成树的初值状态为只有n个顶点而无任何边的非连通图T，此时图中每个顶点自成一个连通分量。按照权值递增的顺序依次选择E中的边，若该边依附于T中两个不同的连通