CAD中常用数据结构PPT教学课件

1、1个体特征总体事物及其联系现实世界实体属性实体集实体及其联系信息世界记录数据项文件数据组织（数据文件、数据库）计算机世界4.1数据结构的概念第2页/共64页第1页/共64页2 (Data) ：是客观事物的符号表示。是客观事物的符号表示。 是组成数据的最小单位；是组成数据的最小单位； 可用数字、字可用数字、字母、专用符号表示母、专用符号表示 是数据中最基本的、不可分的并有命名是数据中最基本的、不可分的并有命名的数据单位的数据单位是数据的基本单位，在程序中是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。通常作为一个整体来进行考虑和处理。是性质相同的数据元素的集是性质相同的数据元素的集合

2、，是数据的一个子集。如字符集合合，是数据的一个子集。如字符集合C=C=A A, ,B B, ,C C, , 4.1数据结构的概念第3页/共64页第2页/共64页3是指相互之间具有是指相互之间具有( (存在存在) )一一定联系定联系( (关系关系) )的数据元素的集合。的数据元素的集合。数据的逻辑结构描述的是数据之间的逻辑关系、数据的逻辑结构描述的是数据之间的逻辑关系、它从客观的角度组织和表达数据。它从客观的角度组织和表达数据。图4-2 四类基本结构图4.1数据结构的概念第4页/共64页第3页/共64页4 两种不同的存储结构：顺序存储结构和链式存储结构。两种不同的存储结构：顺序存储结构和链式存储

3、结构。 顺序存储结构顺序存储结构：用数据元素在存储器中的相对位置来表：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构示数据元素之间的逻辑结构( (关系关系) )。 链式存储结构链式存储结构：在每一个数据元素中增加一个存放另一：在每一个数据元素中增加一个存放另一个元素地址的指针个元素地址的指针(pointer )(pointer )，用该指针来表示数据元，用该指针来表示数据元素之间的逻辑结构素之间的逻辑结构( (关系关系) )。 是指数据在计算机内部的存储方式，它从物是指数据在计算机内部的存储方式，它从物理存储的角度来描述数据以及数据间的关系。理存储的角度来描述数据以及数据间的关系。

4、4.1数据结构的概念第5页/共64页第4页/共64页5第6页/共64页第5页/共64页6 线性结构线性结构是最常用、最简单的一种数据结构。而线性表是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。元素是有序且是有限的。 1. 1.定义：定义： 线性表线性表(Linear List) (Linear List) ：是由：是由n(n0)n(n0)个数据元素个数据元素( (结点结点)a1)a1，a2a2， anan组成的有限序列。该序列中的所有结点具有相同的数组成的有限序列。该序列中的所有结点

5、具有相同的数据类型。其中数据元素的个数据类型。其中数据元素的个数n n称为线性表的长度。称为线性表的长度。 例：例： (A(A，B B，C C、Z Z） (2(2，3 3，4 4，J J，Q Q，K K，A) A) (20014141012001414101，张里户张里户，男男，06/24/1983)06/24/1983)， ( (20014141022001414102，张化司张化司，男男，08/12/1984) 08/12/1984) ， ( (20014141022001414102，李利辣李利辣，女女，08/12/1984) 08/12/1984) 第7页/共64页第6页/共64页7

6、2、顺序存储 定义定义：顺序存储是把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。 a1 a2 ai an Loc(a1)Loc(ai)+(i-1)* l 特点：特点：1 1）有序性）有序性 2 2）均匀性）均匀性4.2线性表第8页/共64页第7页/共64页8特点：特点：1 1）存储单元少，简单易行，结构紧凑。）存储单元少，简单易行，结构紧凑。 2 2）数据结构缺乏柔性，）数据结构缺乏柔性，若要增删数据若要增删数据，必须，必须重新分配重新分配存储单元。存储单元。应用应用 ：查询频繁，修改、补充、删除数据量小的场合。查询频繁，修改、补充、删除数据量小的场合。4.2线性表第9页/共64

7、页第8页/共64页9 线性表顺序存储结构的运算： （1）建表 static char listc6=A,B,C,D,E; （2）访问 char c; C=listc2; （3）修改 listc2=T; （4）删除 （5）插入4.2线性表第10页/共64页第9页/共64页10 3.线性表的链式存储结构用一组任意的存储单元存储数据元素用一组任意的存储单元存储数据元素( (这组存储单这组存储单元可以是连续的，也可以是不连续的元可以是连续的，也可以是不连续的) )。data ：数据域，存放结点的值。：数据域，存放结点的值。next ：指针域，存放结点的直接后继的地：指针域，存放结点的直接后继的地址。址

8、。4.2线性表第11页/共64页第10页/共64页11u存储结构可独立于逻辑结构。存储结构可独立于逻辑结构。 存储的物理顺序不必与逻辑顺序一致而仍能按逻存储的物理顺序不必与逻辑顺序一致而仍能按逻辑要求存取数据。辑要求存取数据。特点：特点：链式存储结构在不改变原来存储结构的条链式存储结构在不改变原来存储结构的条件下，增删记录十分方便，只要控制指针即可。件下，增删记录十分方便，只要控制指针即可。根据指针的数目，根据指针的数目，链接存储结构有链接存储结构有三种类型：三种类型： 4.2线性表第12页/共64页第11页/共64页12正向链：正向链：连接方向与逻辑顺序相同连接方向与逻辑顺序相同反向链：反向

9、链：连接方向与逻辑顺序相反连接方向与逻辑顺序相反R1R2R3R4R5反向链1）单向链结构）单向链结构 各个数据元素由一各个数据元素由一个指针域个指针域和和一个数据域组成一个数据域组成，通过，通过指针构成一个链状结构，且链接方向单一指针构成一个链状结构，且链接方向单一。 R1R2R3R4R54.2线性表第13页/共64页第12页/共64页13- -个简单的单向链表的图示datanext头指针headdatanext尾指针NULL4.2线性表第14页/共64页第13页/共64页14 （1 1 ）结点的描述与实现）结点的描述与实现 C语言中用带指针的结构体类型来描述 typedef struct L

10、node ElemType data; / /* *数据域，保存结点的值数据域，保存结点的值 * */ / struct Lnode *next; / /* *指针域指针域* */ / LNode; / /* *结点的类型结点的类型 * */ / （2 2 ）结点的实现）结点的实现 结点是通过动态分配和释放来的实现，即需要结点是通过动态分配和释放来的实现，即需要时分配，不需要时释放。实现时是分别使用时分配，不需要时释放。实现时是分别使用C C语语言提供的标准函数：言提供的标准函数：malloc() malloc() ，realloc()realloc()，sizeof() sizeof() ，

11、free() free() 。4.2线性表第15页/共64页第14页/共64页15 动态分配动态分配 p=(LNodep=(LNode* *)malloc(sizeof(LNode);)malloc(sizeof(LNode); 函数函数mallocmalloc分配了一个类型为分配了一个类型为LNodeLNode的结点变量的空间，的结点变量的空间，并将其首地址放入指针变量并将其首地址放入指针变量p p中。中。 动态释放动态释放 free(p) ;free(p) ; 系统回收由指针变量系统回收由指针变量p p所指向的内存区。所指向的内存区。P P必须是最近必须是最近一次调用一次调用mallocm

12、alloc函数时的返回值。函数时的返回值。4.2线性表第16页/共64页第15页/共64页16 在链表建立过程中在链表建立过程中, ,首先要建立第首先要建立第- -个结点个结点, ,然后不然后不断地在其尾部增加新结点断地在其尾部增加新结点, ,直到不需再有新结点直到不需再有新结点, ,即尾即尾指针指向指针指向NULLNULL为止。为止。设有结构指针变量设有结构指针变量 struct note struct note * *p,p,* *p1,p1,* *head;head; headhead: :用来标志链表头；用来标志链表头； p:p:在链表建立过程中在链表建立过程中,p,p总是不断先接受系

13、统动态分总是不断先接受系统动态分配的配的新结点地址。新结点地址。 p1-nextp1-next：存储新结点的地址。：存储新结点的地址。A 链表的建立4.2线性表第17页/共64页第16页/共64页17链表建立的步骤：链表建立的步骤：第第- -步：建立第步：建立第- -个结点个结点struct node int data; struct node *next; ;struct note *p,*p1,*head;head=p1=p=(struct node *)malloc(sizeof(struct node);datanextheadp,p1第-结点4.2线性表第18页/共64页第17页/共

14、64页18第二步：第二步： 给第给第- -个结点成员个结点成员datadata赋值并产生第二个结点赋值并产生第二个结点scanf(“%d”,&p-data);/*输入10*/p=(struct node *)malloc(sizeof(struct node);datanextnext10第-结点第二结点headp1p链表建立的步骤：链表建立的步骤：4.2线性表第19页/共64页第18页/共64页19第三步：将第-个结点与第二个结点连接起来p1-next=p;10nextnextdata第-结点第二结点headp1p链表建立的步骤：链表建立的步骤：4.2线性表第20页/共64页第19页/共64

15、页20第四步：产生第三个结点第四步：产生第三个结点p1=p;scanf(“%d”,&p-data);/*输入8*/p=(struct node *)malloc(sizeof(struct node); 以后步骤都是重复第三、四步以后步骤都是重复第三、四步, ,直到给出直到给出- -个结束条件个结束条件, ,不再建新的结点时不再建新的结点时, ,要有要有 p-nextp-nextNULLNULL；它表示尾结点。；它表示尾结点。 链表建立的步骤：链表建立的步骤：4.2线性表第21页/共64页第20页/共64页21例1建立链表 #include #include #define LEN sizeo

16、f(struct node) struct node int data； struct node *next； ； main( ) struct node *p, , *pl, ,* head； headp(struct node * )malloc(LEN)； scanf(“d”, ,&p- -data)； / /*头结点的数据成员*/ / while(p- -data!0) / /*给出0结束条件, ,退出循环*/ / p1p； p(struct node * )malloc(LEN)； scanf(”d”, ,&p- -data)； / /*中间结点数据成员*/ / p1- -next=

17、p； / /*中间结点的指针成员值*/ / p- - nextNULL； / /*尾结点的指针成员值*/ / 4.2线性表第22页/共64页第21页/共64页22 为了证实已建链表是所需要的，应在上程序的省略处加入下列程序段： phead； *链表显示* printf(”链表数据成员是：”)； while(p- -next!=NULL) printf(”d”，p- -data)； pp- -next； printf(”dn”，p- -data)； 【结果】 10 8 6 4 2 0 *建链表时输入的数据* 链表数据成员是：10 8 6 4 2 0 *显示所建的链表*4.2线性表第23页/共64

18、页第22页/共64页23ai-1/ 插入数据元素插入数据元素ListInsert(&L, i, e),第第i个节点前插入数据个节点前插入数据e 在单链表中的实现： 有序对有序对 a 改变为改变为 a , e 和和e, a eaiai-1B.链表插入4.2线性表第24页/共64页第23页/共64页24 因此，在单链表中第因此，在单链表中第 i i 个结点之前进行插个结点之前进行插入的基本操作为入的基本操作为: : 找到线性表中第找到线性表中第i-1i-1个结点，然后修改其个结点，然后修改其指向后继的指针。指向后继的指针。 可见，在链表中插入结点只需要修改指针。可见，在链表中插入结点只需要修改指针

19、。但同时，若要在第但同时，若要在第 i i 个结点之前插入元素，个结点之前插入元素，修改的是第修改的是第 i-1 i-1 个结点的指针。个结点的指针。B.链表插入4.2线性表第25页/共64页第24页/共64页25int ListInsert_L(NODE *head, int i, int e) / LinstInsert_Lelse NODE *p,*s; int j;p = head; j = 0;while (p & j next; j +; if (!p | j i-1) return 0; / i i 大于表长或者小于大于表长或者小于1 1 p=head-next,如何修改程序？j

20、=1时，如何修改程序B.链表插入4.2线性表第26页/共64页第25页/共64页26s =(NODE* malloc(sizeof(NODE); / 生成新结点if ( s = NULL) return 0;s-data = e; s-next = p-next; p-next = s; / 插入return 1; eai-1aiai-1spB.链表插入4.2线性表第27页/共64页第26页/共64页27链表结点的插入意味着要在某结点前或后插入-个或多个结点，所插入的结点必须 (1)动态分配地址 p2(struct node *)malloc(LEN)； (指针变量p2指向该地址); (2)将

21、原链表插入处,后结点p-next取出,存放在指针变量p3中 即p3p-next; (3)将新结点的地址赋给而原插入处前结点的p-next 即p-nextp2 (4)而原插入处后结点的地址值(p3)赋给新结点的p2-next 即p2 - nextp3 注意 (1)本节仅描述在某结点后插入，若想在某结点之前插入，怎么做？。 (2)在插入操作中，多增加了两个结构指针变量p2、p3。B.链表结点的插入4.2线性表第28页/共64页第27页/共64页28例2在链表中插入新结点的程序段。 phead； while(p!=NULL) if (p - - data= =8) p3p - - next； p2(

22、struct node *)malloc(LEN)； scanf(”d”，&p2 - - data)； p2 - - nextp3； p - - next=p2； B.链表插入4.2线性表第29页/共64页第28页/共64页29/ 删除数据元素删除数据元素ListDelete (&L, i, &e)在链表中的实现在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1C.链表结点删除4.2线性表第30页/共64页第29页/共64页30 在单链表中删除第删除第 i i 个结点个结点的基本操作基本操作为:找找到线性表中第到线性表中第i-1i-1个结点，修改其指向后继的指针。个

23、结点，修改其指向后继的指针。ai-1aiai+1ai-1q = p-next; p-next = q-next; e = q-data; delete(q);pqc.链表结点删除4.2线性表第31页/共64页第30页/共64页31 int ListDelete_L(NODE *head, int i, int *e) / 删除以 head 为头指针(带头结点)的单链表中第 i 个结点 / ListDelete_LNODE *p = head; int j = 0;while (p-next & j next; j +; / 寻找第 i-1个结点，q = p-next;p-next = q-ne

24、xt；e = q-data; free（q）;/ 删除并释放结点return 1;if (!(p-next) | j i-1) return 0; / 删除位置不合理4.2线性表第32页/共64页第31页/共64页322)双向链表双向链表 datanextprior图图4-7 双向链表结点形式双向链表结点形式非空双向链表heada2a1an空双向链表head图图4-8 带头结点的双向链表形式带头结点的双向链表形式4.2线性表第33页/共64页第32页/共64页33节点声明节点声明 typedef struct DuLNode ElemType data; / 数据域 struct DuLNod

25、e *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;4.2线性表第34页/共64页第33页/共64页34Initlist(int n) int i; DuLNode *p,*q; head=(DuLNode *)malloc(sizeof(DuLNode ); q=head; / q指向头节点 q-prior = NULL for(i=1;idata); q-next = p; p-prior =q; q =p; / 将将p指向的结点连在链表的尾端指向的结点连在链表的尾端 q-next=NULL;

26、 / 链表的尾端链表的尾端A. 双向链建立双向链建立4.2线性表第35页/共64页第34页/共64页35B.双向链表的插入双向链表的插入 在结点p后面插入一个新结点s头结点psq引入一个指针引入一个指针q qq=p-nexts-next=qq-prior=sp-next=ss-prior=p不引入指针不引入指针s-next=p-nextp-next-prior=s;p-next=s;s-prior=p4.2线性表第36页/共64页第35页/共64页36 1)插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是： “先右后左” 。 S=(DulNode *)malloc(sizeof(DulNo

27、de); S-data=e; S-next=p-next; p-next-prior=S; p-next=S; S-prior=p; /* 钩链次序非常重要 */图图4-9 双向链表的插入双向链表的插入Sepaiai+1Sepaiai+14.2线性表第37页/共64页第36页/共64页37 2)插入时同时指出直接前驱结点p和直接后继结点q，钩链时无须注意先后次序。部分语句组如下： S=(DulNode *)malloc(sizeof(DulNode); S-data=e; p-next=S; S-next=q; S-prior=p; q-prior=S; 4.2线性表第38页/共64页第37页

28、/共64页38c.双向链表的删除双向链表的删除引入两个指针q、rq=p-prior;r=p-next;delete p;q-next=r;r-prior=q; 不引入指针 p-prior-next=p-next; p-next-prior=p-prior; delete p;4.2线性表L第i个结点p图图4-10 4-10 双向链表的删除双向链表的删除第39页/共64页第38页/共64页39 最后一个结点的指针域的指针又指回第一个结点的最后一个结点的指针域的指针又指回第一个结点的链表链表. . a1 a2 . an 3 3）循环链表）循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件

29、不再是“后继是否为空”，而是“后继是否为头结点”。4.2线性表第40页/共64页第39页/共64页40结构中有多个指针域（多于结构中有多个指针域（多于2 2个）个）应用：应用：通常用于矩阵元素、树结构存储，通常用于矩阵元素、树结构存储，只要查只要查询到某一元素，即可获得相邻的、相关元素的地询到某一元素，即可获得相邻的、相关元素的地址。址。 R24 R12 R42 R21R224) 4) 多向链结构多向链结构4.2线性表第41页/共64页第40页/共64页41顺序存储结构和链式存储结构的特点顺序存储结构和链式存储结构的特点1. 1.顺序结构存储顺序结构存储时，相邻数据元素的存放地址也相邻，时，相

30、邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。单元的地址必须是连续的。优点优点：一般情况下，存储密度大，存储空间利用率：一般情况下，存储密度大，存储空间利用率高。高。缺点缺点：（1 1）在做插入和删除操作时，需移动大量元素；）在做插入和删除操作时，需移动大量元素；（2 2）由于难以估计，必须预先分配较大的空间，往往使存）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；储空间不能得到充分利用；（3 3）表的容量难以扩充。）表的容量难以扩充。2.2.链式结构存储链式结构存储时，相邻数

31、据元素可随意存放，所占时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的放表示结点间关系的 指针。指针。优点优点：插入和删除元素时很方便，使用灵活。：插入和删除元素时很方便，使用灵活。缺点缺点：存储密度小，存储空间利用率低。：存储密度小，存储空间利用率低。第42页/共64页第41页/共64页42练习练习 双向链表，某一节点双向链表，某一节点p p，前驱为，前驱为priorprior，后继为，后继为nextnext，在该节点前插入节点，在该节点前插入节点s s，不，不引入指针，列其数据物理结构引入指针，列其数

32、据物理结构 单向链表，某一节点单向链表，某一节点p p，后继为，后继为nextnext，在该节点后插入节点，在该节点后插入节点s s，不引入指针，列其，不引入指针，列其数据结构，数据结构，第43页/共64页第42页/共64页43栈是一种特殊的线性表，它的插入与删除操栈是一种特殊的线性表，它的插入与删除操作只能在表的一端进行。作只能在表的一端进行。定义定义: :栈顶栈顶 栈底栈底 栈的操作栈的操作 允许插入和删除操作的一端称为栈顶。允许插入和删除操作的一端称为栈顶。 不允许插入和删除操作的一端称为栈底。是不允许插入和删除操作的一端称为栈底。是固定端，又称为表头固定端，又称为表头 是按照后进先出的

33、原则进行的。是按照后进先出的原则进行的。 1.1.栈的基本概念栈的基本概念第44页/共64页第43页/共64页442.2.栈的顺序存储表示栈的顺序存储表示 栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。 1 1）静态顺序栈实现简单，但不能根据需要增大栈的存储空间；）静态顺序栈实现简单，但不能根据需要增大栈的存储空间； 2 2）动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。）动态

34、顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。第45页/共64页第44页/共64页45图图4-11 顺序顺序栈示意图栈示意图a1a2aianbottomtop进栈（进栈（pushpush）出栈出栈(pop)(pop)第46页/共64页第45页/共64页46 1 1）栈的动态顺序存储表示）栈的动态顺序存储表示 采用动态一维数组来存储栈。所谓动态，指的是栈的大采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。小可以根据需要增加。 1 1）用）用bottombottom表示栈底指针，栈底固定不变的；栈顶则表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用随着进栈

35、和退栈操作而变化。用top(top(称为栈顶指针称为栈顶指针) )指指示当前栈顶位置。示当前栈顶位置。 2 2）用）用top=bottomtop=bottom作为栈空的标记，每次作为栈空的标记，每次toptop指向栈顶指向栈顶数组中的下一个存储位置。数组中的下一个存储位置。 3 3）结点进栈：首先将数据元素保存到栈顶）结点进栈：首先将数据元素保存到栈顶(top(top所指的所指的当前位置当前位置) )，然后执行，然后执行toptop加加1 1，使，使toptop指向栈顶的下一指向栈顶的下一个存储位置个存储位置; ; 4 4）结点出栈：首先执行）结点出栈：首先执行toptop减减1 1，使，使t

36、optop指向栈顶元素指向栈顶元素的存储位置，然后将栈顶元素取出。的存储位置，然后将栈顶元素取出。第47页/共64页第46页/共64页47图图4-12 (动态动态)堆栈变化示意图堆栈变化示意图空栈空栈bottomtop元素元素a a进栈进栈bottomtopa元素元素b b，c c进栈进栈bottomtopabc元素元素c c退栈退栈bottomtopabbottomtopabdef元素元素d d，e e，f f进栈进栈第48页/共64页第47页/共64页482 2）栈的静态顺序存储表示）栈的静态顺序存储表示 采用静态一维数组来存储栈。采用静态一维数组来存储栈。 栈底固定不变的，而栈顶则随着进

37、栈和退栈操作变化的，栈底固定不变的，而栈顶则随着进栈和退栈操作变化的， 1)1)栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(top(称为栈顶指针称为栈顶指针) )来指示当前栈顶位置。来指示当前栈顶位置。 2 2）用）用top=0top=0表示栈空的初始状态，每次表示栈空的初始状态，每次toptop指向栈顶在数组中的存储位置。指向栈顶在数组中的存储位置。 3 3）结点进栈：首先执行）结点进栈：首先执行toptop加加1 1，使，使toptop指向新的栈顶位置，然后将数据指向新的栈顶位置，然后将数据元素保存到栈

38、顶元素保存到栈顶(top(top所指的当前位置所指的当前位置) )。 4 4）结点出栈：首先把）结点出栈：首先把toptop指向的栈顶元素取出，然后执行指向的栈顶元素取出，然后执行toptop减减1 1，使，使toptop指向新的栈顶位置。指向新的栈顶位置。第49页/共64页第48页/共64页49图图4 4-13 静态静态堆栈变化示意图堆栈变化示意图空栈空栈bottomtopTop=1Top=11 1个元素进栈个元素进栈bottomtopaTop=3Top=33 3个元素进栈个元素进栈bottomtopabcTop=4Top=4栈满栈满bottomtopabedTop=2Top=2元素元素c

39、c进栈进栈bottomtopab第50页/共64页第49页/共64页501. 1.树的定义和基本术语树的定义和基本术语数据之间的关系是层次关系数据之间的关系是层次关系车床零部件关系示意图车床零部件关系示意图第51页/共64页第50页/共64页51一个数据元素及其若干指向其子树的分支一个数据元素及其若干指向其子树的分支1）结点结点(node) (node) 3 3）叶子）叶子(left)(left)结点、非叶子结点结点、非叶子结点树中度为树中度为0的结点称为叶子结点的结点称为叶子结点(或终端结点或终端结点)。相对应地，度。相对应地，度不为不为0的结点称为非叶子结点的结点称为非叶子结点(或非终端结

40、点或分支结点或非终端结点或分支结点)。4 4）孩子结点、双亲结点、兄弟结点）孩子结点、双亲结点、兄弟结点一个结点的子树的根称为该结点的孩子结点一个结点的子树的根称为该结点的孩子结点(child)或子结或子结点；相应地，该结点是其孩子结点的双亲结点点；相应地，该结点是其孩子结点的双亲结点(parent)或父或父结点。结点。2 2）结点的度）结点的度(degree) (degree) 、树的度、树的度结点所拥有的子树的棵数称为结点的度。树中结点度的最大值结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。称为树的度。5 5）树的深度）树的深度(depth)(depth) 树中结点的最

41、大层次值，又称为树的高度树中结点的最大层次值，又称为树的高度 第52页/共64页第51页/共64页52图图4-14 4-14 树的示例形式树的示例形式AABDCEGFHIMJNKL(a) (a) 只有根结点只有根结点(b) (b) 一般的树一般的树第53页/共64页第52页/共64页53由于树的逻辑结构为非线性的，所以只能采用由于树的逻辑结构为非线性的，所以只能采用链式存储结链式存储结构构。可采用。可采用定长定长或或不定长不定长两种方式确定树的结点。两种方式确定树的结点。1 1）定长方式）定长方式以最大度数结点的结构作为该树的所有结点的结构。以最大度数结点的结构作为该树的所有结点的结构。 数据域数据域 指向直接后继指向直接后继1 1的指针的指针 指向直接后继指向直接后继2 2的指针的指针 指向直接后继指向直接后继n n的指针的指针 图图4-15 4-15 定长方式的结点定长方式的结点第54页/共64页第53页/共64页54图图4-16 4-16 树结构树结构ABCDEFGHB E 0 0 D 0 0 0 F 00 0 A 0 H00 0 C 0 0G 0 0 0 图