还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
北京信息科技大学数据机构课件第章7本章主要介绍树和图的相关概念和算法内容包括树的存储结构、二叉树的遍历、线索二叉树、二叉搜索树以及平衡二叉树等树的基本念和术语节点根节点树的基本单元,包含数据和指向其他节点的指树的顶端节点,没有父节点针叶节点子节点没有子节点的节点直接连接到父节点的节点树的存储结构数组和链表数组链表使用数组来存储树的节点,每个节点包含数据和指使用链表来存储树的节点,每个节点包含数据和指向子节点的索引向子节点的指针二叉树及其性质性质一1每个节点最多有两个子节点性质二2左子树和右子树是有序的性质三3二叉树的深度不超过节点数减一二叉树的遍历前序、中序、后序前序遍历1先访问根节点,然后递归遍历左子树和右子树中序遍历2先递归遍历左子树,然后访问根节点,最后递归遍历右子树后序遍历3先递归遍历左子树和右子树,然后访问根节点线索二叉树及其遍历线索化通过改变二叉树的空指针,存储前驱节点和后继节点的信息中序遍历利用线索二叉树的线索信息,按照节点之间的前驱关系进行遍历树的深度和高度深度高度节点到根节点的路径长度树中节点的最大深度二叉搜索树特性查找和插入左子树的所有节点小于根节点,右子树的所有节点利用二叉搜索树的有序性,快速实现查找和插入操大于根节点作平衡二叉树树和红黑树AVL树红黑树AVL通过左旋和右旋操作,保持树的高度平衡通过颜色标记和旋转操作,保持树的高度平衡和节点的有序性堆和堆排序堆堆排序一种特殊的树形数据结构,可以快速找到最值利用堆的特性进行排序,时间复杂度为Onlogn赫夫曼树和赫夫曼编码赫夫曼树1一种特殊的二叉树,用于有效编码赫夫曼编码2根据字符出现的频率,生成唯一的编码压缩算法3利用赫夫曼编码,实现大规模文件的压缩和解压缩图的基本概念和术语顶点边12图中的节点,可以表示实体或位置连接两个顶点的线段,表示顶点之间的关系有向图无向图34边有方向的图,表示顶点之间的单向关系边没有方向的图,表示顶点之间的双向关系图的存储结构邻接矩阵和邻接表邻接矩阵邻接表使用二维数组表示图的邻接关系使用链表数组表示图的邻接关系图的遍历深度优先搜索和广度优先搜索深度优先搜索1从起始节点出发,沿着一条路径遍历到底,然后回溯继续遍历其他路径广度优先搜索2从起始节点出发,先访问所有邻接节点,然后依次访问它们的邻接节点最小生成树法和算法Prim Kruskal法算法Prim Kruskal从某个节点开始,以贪心策略逐步扩展生成最小生通过不断添加边来生成最小生成树,保证生成树不成树形成环。