数据结构复习研究报告.ppt

树、森林与二叉树的转换 给定一组权值能构建出哈夫曼树 2、图 给定一个图的邻接矩阵或邻接表（无向图、有向图、网图）， 能画出相应的图 能写出从给定结点出发进行广度、深度优先遍历的结点序列 能 分别按Prim和Kruskal算法构造该图的最小生成树，写出构造过程。 3、查找技术 给定一组数据构造出二叉排序树 给定二叉排序树删除指定结点 给定一组数据和散列函数： 计算散列函数的值 用线性探测法或链地址法构造出散列表 并求查找成功的平均查找长度 4、排序 给定一组键值序列建立初始堆 第 5 章 树和二叉树 二叉链表主要函数（操作）： BiNode * BiTree(BiNode *root); //有构造二叉树函数 void PreOrder(BiNode *root); //前序遍历二叉树 void InOrder(BiNode *root); //中序遍历二叉树 void PostOrder(BiNode *root); //后序遍历二叉树 void LeverOrder(BiNode *root); //层序遍历二叉树 构造函数：利用扩展二叉树的先序遍历序列建立二叉树 求二叉树t的深度：int Depth(BiNode * r) 求二叉树t的叶子数：int Leaf(BiNode *r) 交换二叉树t的所有左右孩子：void exchange (BiNode *r) 求二叉树的结点个数： void Count(BiNode * r) 第 5 章 树和二叉树 要求掌握： 1、二叉树的顺序存储表示←→二叉树的图形表示 2、给定树和二叉树，能写出各种遍历结果 3、给定扩展二叉树的先序遍历序列→画出此二叉树的图形表示 给定先序（或后序）和中序遍历序列→画出此二叉树的图形表示 5、树和二叉树的形态 4、二叉树的基本性质 5、树和二叉树各有几种存储结构 6、二叉树的先序遍历和中序遍历的非递归算法 7、利用二叉树的先序遍历和中序遍历的非递归算法求二叉树t的深度、求叶子数、交换所有左右孩子、求结点个数 第 5 章 树和二叉树 线索链表 ltag lchild data rchild rtag 0: lchild指向该结点的左孩子 1: lchild指向该结点的前驱结点 0: rchild指向该结点的右孩子 1: rchild指向该结点的后继结点 ltag= rtag= 以中序遍历线索二叉树能绘出线索链表的示意图 第 5 章 树和二叉树 树、森林与二叉树的转换 树转换为二叉树： 1）加线（兄弟间） 2）去线（父子间仅保留长子） 3）调整 森林转换为二叉树： 1）将森林的每棵树转换为二叉树 2）将后继树作为前趋树的右孩子 二叉树转换为森林（树）： 1）加线-----某结点x是其双亲y的左孩子，则把结点x的右 孩子、右孩子的右孩子、…，都与结点y用线连起来； 2）去线-----删去原二叉树中所有的双亲结点与右孩子结点的连线； 3）调整-----整理由1）和2)所得到的树或森林。 第 5 章 树和二叉树 二叉树应用—哈夫曼树及哈夫曼编码 几个概念： 叶结点的权值 带权二叉树 叶结点的路径长度 树的带权路径长度 WPL= 哈夫曼树（Hhffman tree）--带权路径长度最小的二叉 树，也称为最优二叉树。 要求： 给定一组权值能构建出哈夫曼树 可求出每一个权值所对应的哈夫曼编码 能计算该哈夫曼树的带权路径长度。 第 6 章 图 1.图的定义 图（graph）是由有穷非空的顶点集和连接这些顶点的边集构成的整体，通常表示为： G=〈V,E〉 其中，G表示一个图，V是图G的顶点集，E是图G的集。 图的基本术语： 无向边、有向边、无向图、有向图、简单图、邻接、依附、完全图、稠密/稀疏图、无向图的度、有向图的入/出度、权、网图、路径、路径长度、回路、简单路径、简单回路、子图、连通图、连通分量、强连通图、强连通分量、生成树、生成森林 n个顶点的无向完全图中，有n*(n-1)/2条边 n个顶点的有向完全图中，有n*(n-1)条边