电子科大研究生图论课件-第1-2章基本概念-树

图论课件第章基1-2:本概念树-欢迎来到电子科大研究生图论课件的第1-2章本章将介绍树的基本概念、遍历算法、最小生成树、带权路径长度和树的应用准备好跟随我一起探索这个精彩世界吧！树的基本概念定义性质树是一种没有回路的连通图树的特点包括无向、连通、无环、有且仅有一个根结点，并且每个非根结点都有一个父结点种类表示方法常见的树的种类包括二叉树、AVL树、红黑树可以使用链式存储、数组存储或其他方式树等进行表示树的遍历深度优先遍历1通过递归或栈实现，先访问根结点，然后依次访问左子树和右子树广度优先遍历2通过队列实现，先访问根结点，然后按层次依次访问左子树和右子树最小生成树普里姆算法1从图中选取一个顶点作为起点，每次将与当前已选顶点集合距离最小的顶点加入到集合中，直到生成最小生成树克鲁斯卡尔算法2将图中的所有边按照权值从小到大排序，然后依次选择权值最小且不会形成环路的边加入最小生成树带权路径长度定义编码Huffman树中所有叶子结点的路径长度之和称为带权路用于数据压缩，根据字符出现频率构建最优前径长度缀编码树，以减少压缩后文件的大小树的应用高精度计算图的连通性判断操作系统文件目录123结构树的结构可以用于实现通过遍历树可以判断无高精度加减乘除等运算向图的连通性文件目录的嵌套结构可以用树的形式表示练习题选择题填空题12选择正确的答案来检验你对树的理解填写相应的内容来测试你对树的知识证明题3写出完整的证明过程来展示你对树的深刻理解。