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

;;本章重点难点;;1.树的基本概念;树形结构表示方法的多样化;树的基本术语;2.二叉树;1）树和二叉树的区别;2）二叉树的性质;?;3.二叉树的存储结构;链式存储;4.二叉树的遍历;1）深度优先遍历：中序遍历;2）深度优先遍历：先序遍历;3）深度优先遍历：后序遍历;访问一个元素后，再依次访问其各个后继。

对于二叉树，从第1层开始，逐层访问其元素，每一层从左向右。;例9-6已知一个二叉树的后序遍历和中序遍历结果分别为：DGHEBIFCA和DBGEHACIF，试确定该二叉树。;5.树和森林;②孩子表示法;2)树与二叉树;3)森林;;1.哈夫曼树的概念;2.哈夫曼树的构造;;;例9-10已知一串电文内容如下：AACBDADACBAADCADCADA。试为电文中各字符设计最优的二进制电文编码，即哈夫曼编码。;;1.图的概念;?;?;;;;;;4）Kruskal算法;2.拓扑排序;拓扑排序的方法

构造拓扑序列的方法很简单，过程如下：

①在有向图中选择一个没有前驱（入度为0）的顶点并输出。

②从图中删除该顶点和所有从该点引出的边（弧）。

重复①、②直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种情况说明有向图中存在环。;?