第六章 模具CAD中常用的数据结构.ppt

第六章 模具CAD/CAM中常用的数据结构 模具CAD中常用的数据结构有线形表、栈、树与二叉树等。这里主要介绍树与二叉树。 树与二叉树 树型结构是一类很重要的非线形数据结构，在这类结构中，元素结点之间存在着明显的分枝和层次关系。树型结构在客观世界中广泛存在，如家族关系中的家谱、各种社会组织机构、一本书的章节组织划分等都可以形象地以树结构表示。在计算机软件中，树结构也得到广泛的应用。 一、树的定义和术语 1、定义：树是由n(n≥1)个结点组成的有限集合T,其中有且仅有一个结点称为根结点（root)。其余结点可以分为m个互不相交的有限集合T1、T2、…Tm,其中每一个集合Ti本身又是一棵树，称为根结点root的子树。当n=0时为空树。 2、树结构中常用术语 结点（node)：表示树中的元素。 结点的度（degree):结点拥有的子树数。图7-1中结点A的度为3，C的度为1，一棵树中最大的结点度数为这棵树的度。图7-1这棵树的度为3。 叶子（leaf)：度为0的结点。又称为端结点。 孩子（child):除根结点外，每一个结点都是其前驱结点的孩子。 双亲（parents):对应于上述孩子结点的上层结点称为这些结点的双亲。例如图7-1中，D是A 的孩子，A是D、C、B的双亲。 结点的层次（level)：从根结点开始算起，根为第一次层，根的直接后继为第二层，其余各层依次类推。 深度（depth):树中结点最大的层次数。 森林（forest):是m(m ≥0)个互不相交的树的集合。 有序树：树中结点在同层中从左至右有序排列，不能互换的称为有序树，反之，称为无序树 。 二、二叉树 1、定义：二叉树是n(n ≥0)个结点的有限集合，它或为空树（ n =0），或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 注意：二叉树的结点子树有左右之分。 2、二叉树的逻辑结构图 通常用含有两个指针域的链表作为二叉树的存储结构。其中每个结点由数据域（data)、左指针域（Lchild)、和右指针域（Rchild) 组成。 3、二叉树的基本性质 （1）二叉树的第i层至多有2 i-1(i≥1)个结点。 （2）深度为h的二叉树中至多含有2 h-1个结点。 （3）在任意二叉树中，若有n0个叶子结点，n2为度为2的结点，则必有n0= n2+1 4、几种特殊的二叉树 （1）满二叉树 深度为h且含有2h-1个结点的二叉树为满二叉树。 图7-3为一棵深度为4的满二叉树，其结点的编号为自上而下，自左至右。 （2）完全二叉树 结点数目不满足2h-1,已有结点的顺序和满二叉树完全相同。 (3)平衡二叉树 平衡二叉树又称AVI树，它或者是棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 我们把结点的左子树深度减去它的右子树深度定义为结点的平衡因子，因此，平衡二叉树上所有结点的平衡因子只可能是-1，0，1。只要二叉树上有一个结点的平衡因子绝对值大于1，则该二叉树就是不平衡的 。 5、一般树转化为二叉树 为了使一般树也能象二叉树一样用二叉链表示，必须找出树与二叉树之间的对应关系，这样当给定一棵树时，可以找到唯一的一棵二叉树与之对应。 将一般树转化为二叉树的方法为： （1）在兄弟结点之间加一连线。 （2）对每一个根结点，除了与它的第一个孩子保持联系外，去除与其它孩子的联系。 （3）以树根为中心，将整棵树顺时针旋转450。 6、二叉树的遍历 遍历是指循某条有哪些信誉好的足球投注网站路线，依次访问某数据结构中的全部结点，而且每个结点只被访问一次。 由于一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，遍历二叉树就是依次遍历这三部分。 DLR（先序遍历）：先访问根结点，再访问左子树，再访问右子树。 LDR（中序遍历）：左根右 LRD（后序遍历）：左右根 由上述遍历的定义可知，用不同的遍历方式对同一棵二叉树进行遍历，可以得到不同的结点序列。 三、二叉树的应用： 1、二叉排序树 二叉排序树是一种特殊结构的二叉树，它作为一种表的组织手段，通常称为树表，可以作为排序和查找的方法之一。 （1）定义：二叉排序树或者是空树，或者是具有下列性质的二叉树：其左子树上所有结点的数据值均小于根结点的数据值，右子树上所有结点的数据值均大于或等于根结点的数据值，左子树和右子树又各是一棵二叉排序树。 在二叉排序树中，若按中序遍历就可以得到由小到大的有序序列。上图中的二叉排序树，中序遍历（LDR）可以得到有序序列： ｛2，3，4，8，9，9，10，13，15，18，21｝ 升序 （2）二叉排序树的生成 二叉排序树是一种动态表结构，即二叉排序树的生成过程是不断地向二叉排序树中插入新的结点。