数据结构C++版__复习资料.ppt

第9章 索引技术 以中序遍历线索二叉树能绘出线索链表的示意图 树、森林与二叉树的转换 给定一组权值能构建出哈夫曼树 可求出每一个权值所对应的哈夫曼编码 能计算该哈夫曼树的带权路径长度。 2、图 给定一个图的邻接矩阵或邻接表（无向图、有向图、网图） 能画出相应的图 能写出从给定结点出发进行广度、深度优先遍历的结点序列 能 分别按Prim和Kruskal算法构造该图的最小生成树，写出构造过程。 第9章 索引技术 AOV网与拓朴排序 AOE网与关键路径 3、查找技术 给定一组数据构造出二叉排序树 给定二叉排序树删除指定结点 平衡二叉树的调整 给定一组数据和散列函数： 用线性探测法或链地址法构造出散列表 并求查找成功与不成功的的平均查找长度 第 5 章 树和二叉树 二叉树的遍历操作: 先序遍历，中序遍历，后序遍历，层序遍历 由中序和先（后）序遍历结果可惟一确定一棵二叉树。 二叉树的顺序存储结构： 二叉树的顺序存储结构：可采用完全二叉树一样的编号方法（左子：两倍，右子：两倍多1）。 8 9 F 10 G E D C B A 13 12 11 7 6 5 4 3 2 1 第 5 章 树和二叉树 二叉链表存储结构： rchild data lchild 右孩指子针 数据域 左孩子指针 struct BiNode { T data; BiNodeT *lchild, *rchild; //存储左/右孩子指针 }; rchild data lchild 第 5 章 树和二叉树 二叉链表主要函数（操作）： BiTree(BiNodeT *root); //有参构造函数 void PreOrder(BiNodeT *root); //前序遍历二叉树 void InOrder(BiNodeT *root); //中序遍历二叉树 void PostOrder(BiNodeT *root); //后序遍历二叉树 void LeverOrder(BiNodeT *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 rtag rchild data 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）--带权路径长度最小的二叉