计算机辅助设计技术-第4章_常用数据结构详解.ppt

例如：次序（V—根，L—左子树，R—右子树） 先序遍历 中序遍历 后序遍历 先右后左： VRL RVL RLV 先左后右： VLR LVR LRV bt A B C D E F G H I J VLR输出序列：A B D E G HI J C F LVR输出序列：D B G EI H J A C F LRV输出序列：D G I JH E B F C A §4－4 二叉树 三、树的二叉树表示 用二叉树表示一般树可以节省存储空间，一般树转换为二叉树的规则是： 树的根结点为二叉树的根结点； 保留根结点的孩子(从左到右)第一个孩子作为二叉树的左子 树。 根结点的其余孩子作为该左子树的右子树(与左子树原属于兄 弟关系，现变为父子关系)。 §4－4 二叉树 例题： 1. 保留每个结点与最左孩子的边，去掉其余各边。 2. 连接同一双亲的所有兄弟。 3. 以树根结点为轴心，将整棵树顺时针旋转45?即可得到转换 后的二叉树 。 图4-31 树转换为二叉树 A B C E F G D H I A B C E F G D H I A E F G B C D H I §4－4 二叉树 三、二叉树应用举例 利用二叉树排序 排序就是对一组无序的数据递增或递减的规律重新排列。 用二叉树排序的过程分为两步： 先构造这棵二叉树 对这棵二叉树进行遍历 例如: 对一组数据(a1, a2, a3, ,…, ai-1, ai, ai+1, …, an)按递增的规律排序。 (1) 构造二叉树 每一个数据将对应二叉树的一个结点。 该结点在二叉树上的位置是这样确定的： 第一个数据元素a1作为这棵二叉树的根结点； 若 a2 a1，a2作为a1的左子树，否则作为a1的右子树； 第i个数据元素ai首先同这棵二叉树的根结点比较，若 ai a1，则aI应位于a1的左边，再同a1的左子树结点比较，否则同a1的右子树结点比较，以此类推，直到找到该数据元素的位置为止。 建立数组(9, 36, 45, 13，26，7，12，48)的二叉排序树。 §4－4 二叉树 §4－4 二叉树 图3-24 建立的二叉树 (2) 中根遍历二叉排序树 用中根遍历方式遍历该二叉树，图3-24所示的二叉树排序的结果是： 7, 9, 12, 13, 26, 36, 45, 48 * * 第一节 基本概念 第二节 线性表 第三节 栈 第四节 树 第五节 二叉树 第四章 机械CAD中常用的数据结构 第四章 机械CAD中常用的数据结构 数据结构的基本概念 树与二叉树 本 章 要 点 4.1 基本概念 数据 — 数据是指用来描述客观事物的、能输入到计算机中并被计算机接受和处理的符号的总称。用文字符号、数字符号及其它规定的符号对现实世界的事物及其活动的抽象描述。 数据元素 —数据元素是数据的基本单位，是数 据这个集合的一个个体。例如在设计产品的过程中， 可以把该产品的每个部件的每一个零件看作一个相对 独立的单元，这时每个零件就是一个数据元素。 §4－1 基本概念 数据结构 ◎数据结构是指数据及其相互之间的联系 ◎数据结构有逻辑结构和物理结构之分 ◎数据的逻辑结构仅考虑数据之间的逻辑关系，它独立于数据的存储介质。所关注的是数据之间的联系，是这种联系的抽象描述。 ◎数据的物理结构也称存储结构，是数据结构在计算机中的映象。是一种逻辑结构在存储器中的存储方式，存贮方式有顺序、链接、索引、散列等多种，所以一种逻辑结构可以采用多种物理结构存贮。 ◎通常所说的数据结构就是指逻辑结构 数据结构的分类及表示方法 实例：教务处人事简表（表1—1） 职工号 姓名 性别 出生日期 职务 部门 01 02 03 04 05 06 07 08 09 10 万明华 赵宁 张利 赵书芳 刘永年 王明理 王敏 张才 马立仁 邢怀常 男 男 女 女 男 男 女 男 男 男 52.3.20 58.6.14 54.12.7 62.8.5 49.8.15 65.4.1 62.6.28 57.3.17 65.10.12 66.7.5 处长 科长 科长 科长 科员 科员 科员 科员 科员 科员 教务处 教学科 学籍科 考务科 教学科 学籍科 学籍科 学籍科 考务科 考务科 ◎目录行包括六个数据项，这些定义了表的结构 ◎共有十条记录，一个记录就是一个数据元素 ◎“职工号”的值能唯一地标识一个记录，该数据项叫做 关键项 设表1—1中只考虑年龄大小的排列