3基本数据结构.pptVIP

ACM/ICPC程序设计 基本数据结构 及其在程序设计中的应用 计算机学院 张淑平 非线性结构 树、二叉树 图 并查集 非线性结构 树、二叉树 图 并查集 树 树 从逻辑结构看：1）树中只有树根没有父结点；2）除根外，其余结点都有且仅一个父结点； 3）树中的结点，可以有零个或多个孩子结点； 4) 没有孩子的结点称为叶子结点，或终端结点； 5）除根外的其他结点，都存在唯一一条从根到该结点的路径； 树的基本术语 二叉树的定义 二叉树的定义：二叉树要么为空，要么由根结点、左子树和右子树组成。左、右子树本身也是二叉树。 二叉树的存储 顺序存储 链表存储 二叉树的顺序存储 二叉树的顺序存储指的是用元素在数组中的下标表示一个结点与其孩子和父结点的关系. 二叉树的链表存储 二叉树的二叉链表存储(每个节点有两个指针域)，分别指示出结点的左子树和右子树 二叉树的链式存储 三叉链表存储(每个节点有三个指针域，分别指示出左子树、右子树和父结点) 树的存储 树的孩子兄弟表示法 用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和其右边的下一个兄弟结点 树的存储 树的孩子兄弟表示法 用二叉链表作为树的存贮结构。链表的两个指针域分别指向该结点的第一个孩子结点和其右边的下一个兄弟结点 二叉树的运算和应用 二叉树的遍历运算 先序、中序、后序、层序遍历 哈夫曼树 二叉树的结构特点 任何一个非空的二叉树都由三部分构成 二叉树的遍历运算 遍历运算是有关二叉树的主要运算，遍历方式有 先序遍历(DLR)、中序遍历(LDR)、后序遍历(LRD) 层序遍历 先序遍历 DLR：访问根结点、先序遍历左子树、先序遍历右子树 中序遍历 LDR：中序遍历左子树、访问根结点、中序遍历右子树 后序遍历 LRD：后序遍历左子树、后序遍历右子树、访问根结点 层序遍历 LRD：先根，后子树；先左子树，后右子树 例1：Tree Recovery 已知二叉树的先序遍历序列和中序遍历序列，输出它的后序遍历序列． 如图 输入：DBAFCEG FABCDEG 输出：FACBGED 例1：Tree Recovery 先序遍历序列特点： 例1：Tree Recovery 分析 输出后序序列，必先输出左子树的后序序列，再输出右子树的后序序列，最后再输出根。 例2：Trees on the Level Trees are fundamental in many branches of computer science. Current state-of-the art parallel computers such as Thinking Machines CM-5 are based on fat trees. Quad- and octal-trees are fundamental to many algorithms in computer graphics. This problem involves building and traversing binary trees. ... 例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? 哈夫曼树(最优二叉树) 结点的带权路径长度 从根到该结点的路径长度与该结点权的乘积称为结点的带权路径长度 树的带权路径长度 树中所有叶子的带权路径长度之和称为树的带权路径长度 记作 哈夫曼树(最优二叉树) 设有四个叶子a、b、c和d的二叉树中，对应的权值分别为7、5、2和4，计算WPL。 哈夫曼算法 根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删除这两棵树，同时将新得到的二叉树加入F中。 重复2)和3)，直到F中只含一棵树为止。这棵树便是最优二叉树。 实例 合并果子 (fruit.pas/dpr/c/cpp) 【问题描述】 在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。