最新双向循环链表操作-二叉树和树操作-图的创建及相关操作的实现5ppt课件.ppt

《最新双向循环链表操作-二叉树和树操作-图的创建及相关操作的实现5ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新双向循环链表操作-二叉树和树操作-图的创建及相关操作的实现5ppt课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、双向循环链表操作双向循环链表操作- -二叉树二叉树和树操作和树操作- -图的创建及相关图的创建及相关操作的实现操作的实现5 5LOGOPage 2双向循环链表双向循环链表n 功能：n 建立一个空表。n 插入第i个结点。n 删除第i个结点。n 插入第1个结点。n 插入最后一个结点。n 就地逆置LOGOLOGOLOGOLOGOLOGOLOGOLOGO二叉树算法思想：算法思想：层次遍历层次遍历用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 创建一个队列将根放入队列;while(队列非空)从队列取出一个元素并访问;如果该元素有左子树就将它放入队列;如果该元素有右子树就将它放入队列; LOGO

2、二叉树 统计叶子节点数目统计叶子节点数目 采取的方法就是利用函数返回值.把函数定义为返回值为int型的函数.然后进行判断:如果左右结点都为NULL,则返回1(也就是计数+1). 否则调用递归函数,先左子树,后右子树.这个算法真正精髓的一句就是: return leafLeft+leafRight； 在调用递归的同时把各个递归函数的返回值都加了起来.而最终返回到主函数的值，就是叶子节点的个数LOGO树功能功能 分别使用双亲表示法、孩子链表、孩子-兄弟表示法建立树，并输出任一种遍历序列检查所建树的正确性 LOGO树结构简介结构简介树的双亲表示法LOGO树孩子链表表示法LOGO树树的孩子兄弟存储表示

3、法LOGO树方法简介方法简介双亲表示法建立树 ParentsTree() 构造方法 addPTNode（PTNode ptnode）添加节点 printTree( ) 输出树 preOrder( ) 先根遍历孩子链建立树 ChildrenTree() 构造函数 PTListNode(AnyType data) 定义双亲节点 CTNode(intint child) 定义孩子节点 levelOrder（） 层次遍历 孩子-兄弟表示法建立树 createTreeByChildAndBrother（） 构造方法 preOrder（） 先序遍历LOGO树算法思想算法思想双亲表示法从树的定义可知，除根结

4、点外，树中的每个结点都有唯一的一个双亲结点。根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各结点。树中的结点除保存结点本身的信息之外，还要保存其双亲结点在数组中的位置（数组的序号） LOGO树孩子兄弟表示法孩子兄弟表示法 每个结点除存储本身的信息外，还有两个引用域分别存储该结点第一个孩子的地址信息和下一个兄弟的地址信息。LOGO树孩子链表示法孩子链表示法 孩子链表表示法中的结点除保存本身的信息外，不是保存其双亲结点在数组中的序号，而是保存一个链表的第一个结点的地址信息。这个链表是由该结点的所有孩子结点组成。每个孩子结点保存有两个信息，一个是每个孩子结点在一维数组中的序号，另一个是下

5、一个孩子结点的地址信息。LOGO图功能1、存储结构转换2、增加顶点和删除顶点LOGO图结构简介：结构简介：该图为有向图结构，该图为有向图结构， 有两种常见的结构来存储有两种常见的结构来存储该图。该图。LOGO图图结构简介：结构简介：图的邻接矩阵存储结构图的邻接矩阵存储结构图的邻接表存储结构图的邻接表存储结构LOGO图方法简介：方法简介： 存储结构转换存储结构转换n menu1() 创建图，返回图的邻接矩阵创建图，返回图的邻接矩阵n converse2List(int graph,int vexnum) 转换为邻接链表存储结构转换为邻接链表存储结构n converse2InverseList(i

6、nt graph,int vexnum) 转换为逆邻接链转换为逆邻接链表存储结构表存储结构n orthogonalList(int graph,int vexnum) 转换成十字链表存储转换成十字链表存储 增加顶点和删除顶点增加顶点和删除顶点n menu() 创建图创建图n delete（int idx） 删除节点删除节点n add(AnyType data) 增加节点增加节点n printGraph() 输出图结构输出图结构LOGO图算法思想：算法思想： 存储结构转换存储结构转换n 创建图返回图的邻接矩阵创建图返回图的邻接矩阵n 转换为邻接链表存储结构转换为邻接链表存储结构,图的邻接矩阵数组图的邻接矩阵数组 顶点数目弧的数目顶点数目弧的数目n 转换为逆邻接链表存储结构转换为逆邻接链表存储结构LOGO图算法思想：算法思想：增加删除节点增加删除节点n 删除顶点删除顶点 n 1、删除弧结点、删除弧结点n 2、删除顶点节点、删除顶点节点 n 增加顶点增加顶点n 1、增加顶点数、增加顶点数n 2、增加弧的数目、增加弧的数目25 结束语结束语