3-基本数据结构2课件.ppt

ACM/ICPC程序设计;非线性结构;非线性结构;树;从逻辑结构看：1）树中只有树根没有父结点；2）除根外，其余结点都有且仅一个父结点； 3）树中的结点，可以有零个或多个孩子结点； 4) 没有孩子的结点称为叶子结点，或终端结点； 5）除根外的其他结点，都存在唯一一条从根到该结点的路径；;树的结点：包含一个数据元素及若干指向子树的分支； 孩子结点：结点的子树的根称为该结点的孩子； 父结点：B 是A的孩子，则A是B的父亲； 兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上的结点； 祖先结点: 从根到该结点的所经分支上的所有结点； 子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙； 结点的度：结点的子树数目； ...;二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。;二叉树的???储;二叉树的顺序存储;二叉树的链表存储;二叉树的链式存储;树的存储;树的存储;二叉树的运算和应用;二叉树的结构特点;二叉树的遍历运算;先序遍历;中序遍历;后序遍历;层序遍历;例1：Tree Recovery;例1：Tree Recovery;例1：Tree Recovery;分析;例2：Trees on the Level;例2：Trees on the Level;例2：Trees on the Level;例2：Trees on the Level;例2：Trees on the Level;例3：Is it a tree?;例3：Is it a tree?;哈夫曼树(最优二叉树);哈夫曼树(最优二叉树);哈夫曼算法;实例;实例（续）;实例（续）;实例（续）;实例;非线性结构;图结构;无向图及其生成树;图的邻接矩阵表示;图的邻接链表表示;有向图及其强连通子图;例4：学校网络;例4：学校网络(续);例4：学校网络(续);深度优先有哪些信誉好的足球投注网站DFS;广度优先有哪些信誉好的足球投注网站BFS;DFS VS BFS;例5：SPF(1119);例5：SPF;例5：SPF;例5：SPF;例5：SPF;掌握有关图的基本算法;克鲁斯卡尔算法求最小生成树;克鲁斯卡尔算法求最小生成树;克鲁斯卡尔算法求最小生成树;克鲁斯卡尔算法求最小生成树;例6：QS Network;例6：QS Network;例6：QS Network;例6：QS Network;例6：QS Network;要求;实例;集合;非线性结构;并查集;链结构的并查集;树结构的并查集;附在线试题库：