第四章+机械CAD中常用的数据结构+.ppt

1、1,编写解决实际问题的程序的一般过程： 如何用数据形式描述问题?从具体问题抽象出一个适当的数学模型； 设计一个解此数学模型的算法； 确定问题所涉及的数据量大小及数据之间的关系; 如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算?（排序、查询等） 所编写的程序的性能是否良好?,计算机求解问题的一般步骤,2,很多问题求解最后都转化为求解数学方程或数学方程组。 在房屋设计或桥梁设计中的结构应力分析计算可化解为线性代数方程组求解的问题， 天天看到的天气预报，它的数学模型是一个环流模式方程。 预报人口增长情况的数学模型为微分方程。 当计算机进入非数值计算领域，特别是用在管理上

2、的时候，计算机的操作对象之间的关系就无法用数学方程加以描述了。,非数值计算问题的数学模型正是本课程要讨论的数据结构。,3,计算机不仅要处理数值计算问题，还要大量地处理包括图形、图像、文字、表格、声音等各种各样复杂的问题，这时提供给计算机的已不只是简单的、孤立的数据，而是存在某些关系的数据。,(a)五个顶点,()五边形,(a)五角形,(a)五边形与五角形,(x1,y1),(x2,y2),4,一个孤立的具体数据往往没有任何意义。 各相关数据的集合描述任何复杂事物。 数据之间的关系为数据赋予了丰富的含义。,数据结构-是数据之间的关系,5,学习目标：,掌握CAD软件开发所需数据结构的 基本理论； 线性

3、表 栈 树 二叉树,第四章 机械CAD中常用的数据结构,6,数据 是对客观事物的符号表示，是指能输入到计算机内中并被计算机接受和处理的符号的总称。 用文字符号、数字符号及其它规定的符号（如图形、图像）对现实世界的事物及其活动的抽象描述。 数据按其结构层次可分为； 数据项、组合项、数据元素、文件、数据库。,4.1 基本概念,7,数据项 是数据中最基本的、不可分的并有命名的数据单位，是对客观事物某一方面特性的 数据描述。,2）组合项 由若干个数据项组成。,8,3） 数据元素 数据元素是数据的基本单位，是数据这个集合中相对独立的个体。 例如在设计产品的过程中，可以把该产品的每个部件的每一个零件看作一

4、个相对独立的单元，这时每个零件就是一个数据元素；圆柱体、长方体可以作为零件形体的数据元素；直线、圆弧可以作为图形的数据元素。,9,4）文件 相同性质数据的集合就是文件,5）数据库 非单纯性、有结构文件的集合,10,数据结构理论 研究数据元素之间的抽象化关系，并不涉及数据元素的具体内容。,数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。,11,数据结构的三个组成部分： 逻辑结构：描述数据元素之间的逻辑关系。 D_S=（D，S） 存储结构： 数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 数据操作： 对数据要进行的运算（

5、查找、插入、删除）。,12,数据的逻辑结构 定义：数据的逻辑结构描述的是数据之间的逻辑关系、它从客观的角度组织和表达数据。,逻辑结构归纳 为两大类型：,线性结构,非线性结构,树状结构,网状结构,13,线性结构结构中的数据元素之间存在一对一的关系。每一个数据元素仅与它前面的一个和后面的一个数据元素相联系。,特点：数据间的关系很简单，只是顺序排列的位置关系，而且这种位置关系是线性的。 这种结构的数据可以用数表的形式表示。 又称这类数据结构为“线性表结构”,14,例4-1：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b

6、2)，(an, bn)，其中ai, bi(i=1，2n) 分别表示某人的名字和电话号码。 本问题是一种典型的表格问题。数据与数据成简单的一对一的线性关系。,表1-1 线性表结构,15,例如：线性表的逻辑结构,16,非线性结构 这种结构的数据间逻辑关系比较复杂。,类型：树状结构、网状结构及树状网状的结合,（1） 树状结构 结构中的数据元素之间存在一对多的关系。 每个数据元素仅与它前面的一个数据元素相关，可与后面多个数据元素相关。,17,3.1.2 数据结构,18,19,例42：磁盘目录文件系统 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依

7、此类推： 本问题是一种典型的树型结构问题，如图1-1 ，数据与数据成一对多的关系，是一种典型的非线性关系结构树形结构。,图1-1 树形结构,20,（2) 网状结构结构中的数据元素之间存在多对多的关系。数据元素之间的关系是一种多元关系，即多对多、多对一。,工艺路线方案图,21,例43：交通网络图 从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。,22,23,数据的存储（物理）结构,定义: 是指数据在计算机内部的存储方式，它从物理存储的角度来描述数据以及数据间的关系。,常用种类: 顺序存储结构、链接存储结构。,(1) 顺序存储

8、结构,定义: 利用一组地址连续的存储单元依次存放各数据元素。,24,25,特点：1）存储单元少，简单易行，结构紧凑。 2）数据结构缺乏柔性，若要增删数据，必须 重新分配存储单元。,应用 ：查询频繁，修改、补充、删除数据量小的场合。,26,用一组任意的存储单元存储数据元素(这组存储单元可以是连续的，也可以是不连续的)。,3.1.2 数据结构,结构形式：,一个数据元素项（结点）由两个字段组成 信息字段（INFO）和指针字段(POINT),信息字段 存放数据元素本身的域 指针字段 存放直接后继或直接前驱的域称为指针域(point )。指针域中存储的信息称作指针。,（2）链接存储结构,27,链式存储结

9、构,28,链表概念提出：,struct link char name; struct link *next ;,29,存储结构可独立于逻辑结构。 存储的物理顺序不必与逻辑顺序一致而仍能按逻辑要求存取数据。,特点：链接存储结构在不改变原来存储结构的条件下，增删记录十分方便，只要控制指针即可。,根据指针的数目，链接存储结构有三种类型：,单向链结构,双向链结构,多向链结构,30,数据的逻辑结构,数据的存储结构,数据的运算：检索、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面,31,正向链：连接方向与逻辑顺序相同,反向链：连

10、接方向与逻辑顺序相反,反向链,1) 单向链结构,各个数据元素由一个指针域和一个数据域组成，通过指针构成一个链状结构，且链接方向单一。,32,单向环链：最后一个数据元素与第一个数据元素通过指针链接,特点： 可以从任意一个元素进入，按指针逐个存取各条记录； 某个指针损坏不影响整个结构。,33,2）双向链结构,双向链结构中有两个指针域，分别按正、反两个方向链接。,34,结构中有多个指针域（多于2个）,应用：通常用于矩阵元素、树结构存储，只要查询到某一元素，即可获得相邻的、相关元素的地址。,3) 多向链结构,35,链接存储结构的记录增、删,在不改变原来存储结构的条件下，只要控制指针即可,36,线性结构

11、是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中： 存在一个唯一的被称为“第一个”的数据元素； 存在一个唯一的被称为“最后一个”的数据元素； 除第一个元素外，每个元素均有唯一一个直接前驱； 除最后一个元素外，每个元素均有唯一一个直接后继。,38,线性表(Linear List) ：是由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。 当n=0时，称为空表。 当n0时，将非空的线性表记作： (a1，a2，an) a1称为线性表的第一个

12、(首)结点，an称为线性表的最后一个(尾)结点。,线性表的定义,4.2 线性表,39,线性表逻辑结构,a(1)，a(2)，a(3)，,a(i-1)，a(i)，a(i+1)，a(n),4.2 线性表,其中，这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 数据元素ai可以是一个数，可以是一个符号，还可以是一个线性表，甚至是更复杂的数据结构。,40,42 线性表,例如：光轴轴径系列值表示成线性表形式: （3，6，10，14，18，20，22，,90）,减速器明细表也属线性表，该表中的数据元素是由4个数据项组成的一个记录。,41,线性表逻辑结构具有以下特点：,线性表

13、中数据元素之间呈线性关系，是最简单、最常见的数据结构。 线性表中数据元素的个数定义为线性表的长度，当n =0时，为空表； 数据元素在线性表的位置取决于它们自己的序号，数据元素之间的相对位置是线性的，如a1是第一个元素，an是最后一个元素； 除了第一个和最后一个数据元素外，每个数据元素有且只有一个直接前趋，有且只有一个直接后继。当1 i n时，ai的前一个元素ai-1是它的直接前趋，ai的后一个元素ai+1是它的直接后继。,42,线性表的物理结构 （存储结构） 既可以采用顺序存储，也可以采用链接存储结构。,43,4.2.1、线性表的顺序存储结构,1、顺序存储 ：把线性表的结点按逻辑顺序依次存放在

14、一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。,假定一个线性表A(n)，它的每个数据元素占m个存储单元，第一个数据元素在内存中的开始地址为b，那么，第i个数据元素的存储位置为： L(ai)=b+(i-1)m,44,有序性：各数据元素之间的存储顺序与逻辑顺序一致。 均匀性：每个数据元素所占存储空间的长度是相等的。,线性表的顺序存储结构的特点,45,（1）建表 static char listc6=A,B,C,D,E; （2）访问 char c; C=listc2; （3）修改 listc2=T;,线性表顺序存储结构的运算：,46,线性表的删除运算是指将表的第i (1in)结点（数据

15、元素）删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，an) 变成长度为n-1的线性表： (a1，a i-1，a i+1，an),（4）删除,删除前,删除后,47,（4）删除,例4-4 删除一个数据元素。 #define LEN 6 Main（ ） static char listc6=A,B,C,D,E; int i,j; printf(“n 删除第几个数据元素？”); Scanf(“%d”, ,48,线性表的插入运算是指在表的i(1in)个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai

16、，an),（5）插入,为保证线性表的均匀性，新的数据元素必须和表内已有元素的类型一致； 为了保证线性表的有序性，原线性表第i至最后一个元素要向后移动一个数据元素所占存储空间的长度。,插入前,插入后,49,例4-5 插入一个数据元素。 #define LEN 6 Main（） static char listc6=A,B,C,D,E; int i,j; char c1； printf(“n 输入插入新的数据元素：”); c1=getche（）； printf(“n 输入新的数据元素的位置：”); Scanf(“%d”, ,50,对表中数据元素进行的访问、修改运算速度快。在删除或插入运算时，必须进

17、行大量数据元素的移动，增加运算时间。,这种存储结构多用于查找频繁、很少增删的场合。如工程手册中的数表。向量、数组、栈、队列属于顺序存储结构。,51,4.2.2 线性表的链式存储结构,1链式存储结构的待点 在线性表的链式存储结构中，每个数据元素可能存放在不连续的存储单元中，数据元素在存储介质上的顺序与其在逻辑上的顺序不必一致. 链表中数据元素的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，在存储每个数据元素域的同时，还必须存储指示其后继数据元素的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。,52,4.2.2 线性表的链式存储结构,在链表结构中，一个

18、数据元素由数据域和指针域组成，称为一个结点。 数据元素用指针来保存其直接前趋或直接后继的地址，形成环环相扣的链条，并通过指针来逐个检索数据元素。,(a1,a2, ai,ai+1, an),53,2.单向链表,单向链表是最简单的一种链表结构。结点指针域中的指针存放该节点直接后继的存放地址。 第一个结点的地址存放在链表头指针head中； 链表的最后一个结点的指针城设为NULL。,54,头结点：有时为了方便，增加一个结点，其数据域不存放任何 元素，其指针域存放第一个元素的存储地址。 头指针：第一个元素的存储地址；,l,头结点,头结点指针：指向头结点的指针；,特点 ： 存储空间不一定连续； 元素之间的

19、后继关系是由指针来体现的； 逻辑上相邻，物理上不一定相邻； 非随机存取（顺序存取），即访问任何一个元素的时间不同,55,在链表建立过程中，首先要建立第一个结点，然后不断地在其尾部增加新结点，直到不需再有新结点，即尾指针指向NULL为止。 定义结点数据结构，有两个成员DATA和NEXT： 在数据域（data）中定义数据的类型，数据域中的数据可能只有一个也可能有多个，它们的类型可以一样也可以不一样，存放结点数据元素本身； 在指针域（next）中定义指向数据结构本身的指针，存放该结点直接后继的地址。,1) 建立单向链表,56,定义结构指针变量： struct node *p,*p1,*head; h

20、ead：用来标志链表头； p：在链表建立过程中，p总是不断先接受系统动态分配的新结点地址。 p1next：存储新结点的地址。 然后通过动态分配内存给每个结点赋值。 申请动态分配一个存储空间的表示形式为： (struct node*)malloc(sizeof(struct node),1) 建立单向链表,57,链表建立的步骤：,第-步：建立第一个结点 struct node /*定义结点数据结构*/ int data; /*数据域*/ struct node *next; /*指向直接后继的指针*/ struct node *p,*p1,*head; /*定义结构指针变量*/ head=p1=

21、p=(struct node *)malloc(sizeof(struct node); /*申请动态分配一个存储地址，为第一个结点地址*/,data,next,head p,p1,第一结点,58,第二步： 给第一个结点成员data赋值并产生第二个结点 scanf(“%d”,data,next,next,10,第一结点,第二结点,head p1,p,链表建立的步骤：,59,第三步：将第一个结点与第二个结点连接起来 p1next=p;,10,next,next,data,第一结点,第二结点,head p1,p,链表建立的步骤：,60,第四步：给第二个结点成员data赋值并产生第三个结点 p1=p

22、; scanf(“%d”,链表建立的步骤：,10,next,next,8,第一结点,第二结点,p1,第三结点,p,data,next,next,10,第一结点,head p1,8,next,第二结点,p1,data,next,第三结点,p,第五步：将第二个结点与第三个结点连接起来 p1next=p;,next,data,61,以后步骤都是重复第四、五步,直到给出一个结束条件，不再建新的结点时，要有： p nextNULL；它表示尾结点。,62,例46建立链表。用C语言建立单向链表的程序如下： #include #include #define LEN sizeof(struct node) s

23、truct node /*定义结点数据结构*/ int data； struct node *next； ； main( ) struct node *p, *pl,* head； headp(struct node * )malloc(LEN)；/*申请动态分配一个存储地址，为第一个结点地址*/ scanf(“d”, int data; Sruct node *p; p=head; while(p)/*当结点指针非空时*/ if (j+i)/*如果是第i个结点*/ datapdata；return； /*将第i个结点 数据保存在data中，返回*/,67,ppnext; /*结点指针指向下一

24、结点*/ Pritnf(“n 序号超出范围”); return(0); ,68,在链表中查找是否有指定的数据元素，若有就输出第一次出现这个数据元素的逻辑位置，否则输出没由这个数据元素的信息。 例48查找指定数据，程序如下 int search ( ) int j=1; int data; sruct node *p; p=head; Pritnf(“n 输入要查找的数据：”); scanf(”d”, /*结点指针指向下一结点*/ Pritnf(“n 没找到该数据”); return(0); ,70,70,4）删除 若要删除表中的第i个数据元素，找到表的第i-1个结点，将第i-1个结点指针域中原

25、指向第i个结点的指针指向第i+1个结点。然后释放第i个结点所占用的存储空间，如图所示。,71,如图，在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。此过程为：,p-next=p-next-next;,p=getnode(head，i-1); q=p-next; p-next=q-next; delete r;,72,例 4-8删除第i个结点。 Void delete ( int i ) int j=1; sruct node *p，*q; p=q=

26、head; if (i=1) head=qnext; free(q) ; return; /*将头结点指向第一个结点的后继点*/ while(p) /*当结点指针非空时*/ if (+ j=i) (q=p next； /*q为第i个结点， p为第i1个结点*/ if (q =NULL) Pritnf(“n 序号超出范围”); return; p-next=q-next; /*将第i-1个结点指针指向第i+1个结点*/； delete( q); return; ,73,ppnext; /*结点指针指向下一结点*/ Pritnf(“n 序号超出范围”); return(0); ,74,插入运算是将

27、值为 x 的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。,5）单向链表插入,在单链表中的实现： 有序对 改变为 ,75,(1) 为新节点申请一个存储空间， newnode (struct node *)malloc(LEN)； (指针变量newnode 指向该地址); (2)查找到第i-1个节点，将第 i 个结点的地址 node-next取出，存放在指针变量temp中， 即 tempnode-next;,链表结点的插入过程：,nwenode,temp,76,(3)将第i-1个节点的指针指向新节点的地址， 即将新结点的地址赋给第i-1个节点指针 node-next中 ， 即

28、node-next= newnode (4)将新节点的指针指向第 i 个节点的地址， 即将原链表中第 i个节点的地址值赋给新结点指针newnode -next 中， 即 newnode -next =temp,11,77,例49在下面所建链表的第i个节点之前插入一个新结点的程序如下：,78,Insert(struct link *node，int i，newdata) /*注意：在调用之前，应将node指向表头*/ int j=0; struct link *newnode，*temp; node=head； /*给新结点动态分配内存*/ newnode (struct link *)mall

29、oc(sizeof(struct link ); newnode-data =X; /*给新结点的数据域赋新值*/ Wile (node) /*当结点指针非空时*/ if j+=i-1 /*如果是第i-1个结点*/,79, /*将第i个结点地址存放在temp中*/ temp=node-next; /*将第i-1结点指针指向新节点的地址*/ node-next= newnode ； /*新结点的指针指向第i个节点的地址*/ newnode -next=temp ； return; node= node-next; /*结点指针指向下一结点*/ ,80,注意 (1)本节仅描述在某结点后插入，若想在

30、某结点之前插入，怎么做？。 (2)在插入操作中，多增加了两个结构指针变量newnode， temp,链表结点的插入,81,3 双向链表 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为： struct DuLNode datatype data; DuLNode *prior，*next; ;,结点,存储前趋结点 的地址,存储数据元素,存储后继结点 的地址,82,双向链结构中有两个指针域，分别按正、反两个方向链接。,3. 双向链表,83,3. 双向链表,双向链表的特

31、点： 不但能方便地找到其直接后继，也能方便地找到其直接前趋,84,双向链建立,首先定义结点的数据类型，它有三个成员，data、next和prior 。data存放数据元素本身的值，next存放结点直接后继的地址， prior存放结点直接前继的地址。Lead和tail分别存放链头和链尾的地址。 struct DuLnode /*定义结点数据结构*/ struct DuLNode *prior; / 指向前驱的指针域 int data； struct DuLnode *next； / 指向后继的指针域 *head,*tail;/表头指针，表尾指针,85,createlist(int n) int

32、i; DuLNode *p,*q; head=(DuLNode *)malloc(sizeof(DuLNode ); q=head; / q指向头节点 q-prior = NULL /链表的头为空 for(i=1;idata); /*输入第i个 结点的数据成员 q-next = p; /*将前一个结点的后继指向新结点的地址 p-prior =q; /*将新结点的前驱指向前一个结点的地址 q =p; / 将p指向的结点连在链表的尾端 q-next=NULL; / 链表的尾端为空 ,双向链建立,86,顺序存储结构和链式存储结构的特点,顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结

33、构是统一的，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点： （1）在做插入和删除操作时，需移动大量元素； （2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用； （3）表的容量难以扩充。,87,链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点：插入和删除元素时很方便，使用灵活。 缺点：存储密度小，存储空间利用率低。,88,4.3栈,栈是一种特殊的线性表，它的插入与删除操作只能在表的一端进行。,定义:,栈顶:,栈底:,栈的操作:,允许插入和删除操作的一端称

34、为栈顶。,不允许插入和删除操作的一端称为栈底。,是按照后进先出的原则进行的。,演示,89,1、栈的逻辑结构,栈的逻辑结构：s=(a1, a2, a3, , ai, , an)， 则a1称为栈底元素，an为栈顶元素。 进栈的顺序： a1, a2, a3, , an ； 出栈的顺序是 ：an, an-1, , a3, a2, a1。 特点： 后进先出(LIFO - Last In First Out) 。,4.3.1 栈的 结构,90,物理结构,顺序存储,链接存储,2、栈的存储结构,91,4.3.2 栈的运算,建立一个栈,栈的存储结构用数组sn。 设m为栈的上界，则在C语言中，由于第1个数组元素是

35、s0，所以栈的上界m等于n-1。 设一栈顶指针为TOP，它不必指向数据元素的实际地址，只记录数据元素的逻辑序号即可。 当元素尚未进栈时，令TOP等于-1。,92,4.3.2 栈的运算,2. 进栈,如果有元素进栈，首先检查栈顶指针TOP，如果TOP等于m，表示栈满，显示栈满信息，否则将发生上溢。如果TOPm，令TOP=TOP+1，将该元素赋给sTOP。,3. 出栈,出栈即取走栈顶元素。首先检查栈顶指针TOP，如果TOP=-1，表示栈空，显示出错信息，否则将发生下溢。如果TOP-1，出栈元素为sTOP，然后令TOP=TOP-1。,93,2应用 机械装拆就是一个栈模型的例子。机器或部件在装配时，各有

36、关零件都是按一定顺序装配上去的。拆卸的顺序正好与装配的顺序相反，后装的要先拆（LIFO）。,94,例4-10 图4-15为某齿轮传动箱的传动关系图，其中， ()号轴为输入轴，6、7、8、9号轴为输出轴，其余各轴为中间传动轴。编写程序，输入指定的轴号，打印从o号轴到指定轴的传动路线。,95,1确定各轴之间传动关系的数据结构 每根轴与其他各轴的传动关系可作为一个数据元素。若i轴直接带动J轴，则a(i，j)1，否则a(i，j)0。全部轴的传动关系构成一个传动关系表：,96,2用栈作为求解传动路线的工具,输入传动关系表：A,输入要求解的n号轴传动路线,1n9,i=0;j=0 Top=0,s(top)=

37、0,top0 OR j9,Y,N,无该号轴,出错,Y,N,0号轴为栈底,97,a(i,j)=1,s(top)=j Top=top+1,j=9,i=j, j=0,j= s(top） Top=top+1, i=s(top),j=n,j= j+1,打印输出结果,退出,Y,N,Y,N,Y,N,有传动关系 j号轴进栈,98,4.4 树,树的定义 树（Tree）是n（n0）个结点的有限集。在任意一棵非空树中： （1）有且仅有一个特定的称为根（Root）的结点； （2）当n1时，其余结点分成m（m0）个互不相交的有限集T1，T2，.，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。,99,树的基本术语

38、,1树的结点：数据元素的内容及其指向其子树的分支统称为结点。 2结点的度：结点拥有的子树的个数称为结点的度。 例如，在图中，结点A，B，C的度分别为 3树的度: 树内各结点的度的最大值。 例如，在图中，树的度为 4叶子或终端结点: 度为0的结点。 例如，在图中，结点E，F，G，H，M，均为叶子。 5非终端结点或分支结点: 度不为0的结点称为非终端结点 或分支结点。除根结点之外， 分支结点也称为内部结点。,3,2，2，3。,100,6.1.2 树的基本术语,6结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。其余结点的层次值为双亲结点层次值加1，若某结点在第i层，则其子树的根就在第i+1层。 例如，在图中，A，B，D，M的层次值分别为1，2，3，4。 7树的深度：树中结点的最大层次称为树的深度或高度。 图6-1(b）所示的树的深度为4。,101,4.4. 1 树逻辑结构,数据之间的关系是层次关系,车床零部件关系示意图,4.4 树,102,1）树中没有前驱的结点，只有一个即树根;,树的逻辑结构特点：,2）其它结点仅有一个直接前驱结点；,103,4.1.2、树的存储结构,用定长或不定长两种