电大数据结构复习大纲.docx

数据构造第 1 页 共 30 页数据构造及算法复习大纲题型及分值分布第一部份 复习大纲第一章 绪论1. 数据构造的根本概念和术语1.1 数据、 数据元素、 数据项、 数据构造等根本概念1.2 数据构造的逻辑构造、 存储构造及数据运算的含义及其互相关系1.3 数据构造的两大逻辑构造和四种常用的存储表示方法2. 算法的描绘和分析2.1 算法、算法的时间困难度和空间困难度、最坏的和平均的时间困难度等概念2.2 算法描绘和算法分析的方法，对于一般算法能分析出时间困难度第二章 线性表1. 线性表的逻辑构造 1.1 线性表的逻辑构造特征2. 线性表的依次存储构造 2.1 依次表的含义及特点，即依次表如何反映线性表中元素之间的逻辑关系2.2 依次表上的 插入 、删除 操作及其平均时间性能分析3. 线性表的链式存储构造3.1 链表如何表示线性表中元素之间的逻辑关系3.2 链表中头指针和头结点的运用3.3 单链表 、双向链表 、循环链表链接方式上的区分3.4 单链表上实现的建表 、查找 、插入 和删除4. 依次表和链表的比较 数据构造第 2 页 共 30 页4.1 依次表和链表的主要优缺点4.2 针对线性表上所须要执行的主要操作，知道选择依次表还是链表作为其存储构造才能获得较优的时空性能第三章 栈和队列1.栈的逻辑构造、存储构造及其相关算法1.1 栈的逻辑构造特点，栈及线性表的异同1.2 依次栈和链栈上实现的进栈、退栈等根本算法1.3 栈的“上溢和“下溢的概念及其判别条件2. 队列的逻辑构造、存储构造及其相关算法 2.1 队列 的逻辑构造特点，队列及 线性表 的异同 2.2 依次队列 主要是 循环队列 和 链队列 上实现的 入队 、 出队 等根本算法2.3 队列的“上溢和“下溢的概念及其判别条件 2.4 运用数组实现的循环队列取代一般的依次队列的缘由 2.5 循环队列中对边界条件的处理方法 3. 栈和队列的应用 3.1 栈和队列的特点，什么样的状况下可以运用栈或队列3.2 表达式求值的算法思想，及栈变更状况。第四章 串、数组和广义表1.1 串的有关概念及根本运算1.2 串及线性表的关系2.多维数组 2.1 多维数组的逻辑构造特征2.2 多维数组的依次存储构造及地址计算方式2.3 数组是一种随机存取构造的缘由2.4 矩阵的压缩存储对称矩阵、三角矩阵、稀疏矩阵的表示方式和对应的地址计算方式。3. 广义表的概念3.1 广义表的有关概念及其及线性表的关系3.2 求给定的广义表的表头、表尾运算 数据构造第 3 页 共 30 页第五章 树和二叉树1.1 树的逻辑构造特征1.2 树的不同表示方法 1.3 树的常用术语及含义2. 二叉树2.1 二叉树的递归定义及树及二叉树的差异 2.2 二叉树的性质，理解相应的证明方法 3. 二叉树的遍历3.1 二叉树的三种遍历算法，理解其执行过程 3.2 确定三种遍历所得到的相应的结点访问序列 4. 线索二叉树4.1 二叉树线索化的目的及本质 4.2 在中序线索树中查找给定的中序前趋和中序后继的方法 5. 树和森林5.1 树和森林及二叉树之间的转换方法 5.2 树的各种存储构造及其特点5.3 树的两种遍历方法 6. Huffman 树 及其应用 6.1 最优二叉树和最优前缀码的概念及特点 6.2 Huffman 算法的思想 6.3 依据给定的叶结点及其权值构造出相应的最优二叉树 6.4 依据最优二叉树构造对应的 Huffman 编码第六章 图1.图的概念 1.1 图的逻辑构造特征 1.2 图的常用术语及含义2. 图的存储构造2.1 邻接矩阵和邻接表这两种存储构造的特点及适用范围 2.2 依据应用问题的特点和要求选择相宜的存储构造3. 图的遍历 3.1 连通图及非连通图的深度优先搜寻和广度优先搜寻两种遍历算法 3.2 确定两种遍历所得到的顶点访问序列及两种生成树4.生成树和最小生成树 4.1 生成树和最小生成树的概念 数据构造第 4 页 共 30 页4.2 对遍历给定的图，画出深度优先和广度优先生成树或生成森林 4.3 Prim 和 Kruskal 算法的根本思想、时间性能及这两种算法各自的特点 4.4 要求对给定的连通图，依据 Prim 和 Kruskal 算法构造出最小生成树 5. 图的应用5.1 对于给定的有向图，依据 Dijkstra 算法 画出求单源最短途径的过程示意图 5.2 拓扑排序的根本思想和步骤 5.3 对给定的有向图 ，假设拓扑序列 存在，那么要求 写出一个或多个拓扑序列 5.4 关键途径的根本思想和步骤 5.5 对给定的有向图，写出求关键途径的过程第七章 查找1. 线性表的查找 1.1 依次查找 、 二分查找的根本思想、算法实现和查找效率分析 1.2 依次查找中哨兵的作用 1.3 二分查找对存储构造及关键字的要求 2. 树的查找3.1 二叉排序树和平衡二叉树的定义和特点 3.2 二叉排序树的插入、删除、建树和查找算法 3.3 建立一棵二叉查找树的过程本质上是对输入实例的排序过程，输入实例对所建立的二叉查找树形态的影响3.4 平衡二叉树的插入时平失衡的调整的根本思想4. 哈希表4.1 哈希表、哈希函数、哈希地址和装填因子 等有关概念 4.2 哈希函数的选取原那么及产生冲突的缘由 4.3 承受线性探测法、平方探测法和链地址法解决冲突时， 哈希表的建表方法、查找过程以及算法实现和时间分析 第八章 内部排序1. 根本概念1.1 排序 在数据处理中的重要性 1.2 排序方法的“ 稳定 性含义 1.3 排序方法的分类及算法好坏的评判标准2. 插入排序 2.1 干脆插入排序的根本思想以及在最好、最坏和平均状况下的时间性能分析 2.2 干脆插入排序中哨兵的作用 2.3 针对给定的输入实例，要能写出干脆插入排序的排序过程 数据构造第 5 页 共 30 页2.4 驾驭干脆插入排序的算法3. 交换排序 3.1 冒泡排序的根本思想以及在最好、最坏和平均状况下的时间性能分析3.2 推断冒泡排序完毕的条件3.3 针对给定的输入实例，要能写出冒泡排序的排序过程3.4 驾驭冒泡排序的算法3.5 快速排序的根本思想和算法实现，以及在最坏和平均状况下的时间性能分析，理解算法的稳定性 3.6 针对给定的输入实例，能写出快速排序的排序过程3.6 驾驭快速排序的算法4. 选择排序4.1 简洁项选择择排序的根本思想和算法实现，以刚好间性能分析 4.2 针对给定的输入实例，写出干脆选择排序的排序过程 4.3 驾驭简洁项选择择排序的算法5. 各种排序方法的比较和选择5.1 通过对被排序的记录数目、记录信息量的大小、关键字的构造及初始状态、稳定性能、扶植空间的大小、各种时间性能等方面的比较驾驭各种排序的优缺点 5.2 依据实际问题的特点和要求选择相宜的排序方法 数据构造第 6 页 共 30 页第二部份 复习重点第一章 绪论1.1 数据、 数据元素、 数据项、 数据构造等根本概念1.数据data：客观事物的符号表示，在计算机科学中指全部能输入计算机中并被计算机处理的符号总称。整数、浮点数、字符串、声音、图像。2.数据元素data element：数据的根本单位，在计算机程序中通常作为一个整体进展考虑和处理。3.一个数据元素可能由假设干个数据项data item组成。数据元素是一个数据整体中相对独立的单位。但它还可以分割成假设干个具有不同属性的项字段。故不是组成数据的最小单位。数据项是构成数据的最小单位。4.数据对象data object：性质一样的数据元素的集合，是数据的一个子集。5.数据构造data structure：数据元素以及数据元素之间存在的关系。6.数据构造主要描绘：数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算，即数据的逻辑构造、存储构造和数据的操作集合1.2 数据构造的逻辑构造、 存储构造的含义及其互相关系1.数据的逻辑构造：用形式化方式描绘数据元素间的关系。数据的逻辑构造独立于计算机，是数据本身所固有的。用于算法的设计。2.有两大类逻辑构造：线性构造线性表、栈、队列、数组和串，非线性构造树和图。3.数据的物理构造也称存储构造：数据在计算机中的详细表示。包括数据元素的表示和关系的表示。存储构造是逻辑构造在计算机存贮器中的映像，必需依靠于计算机。用于算法的实现。4.数据的存储方式可分为如下两类：依次存储、链接存储。1.3 算法1.算法的定义：算法是对特定问题求解步骤的一种描绘， 是指令的有限序列。2.算法的特性：有穷性算法必需在执行有穷步之后完毕，而且每一步都可在有穷时间内完成确定性每条指令无二义性。并且，一样的输入只能得到一样的输出；可行性算法中描绘的每一操作，都可以通过已实现的根本运算来实现。输入算法有零至多个输入。输出算法有一个至多个输出3.算法效率的度量：时间困难度和空间困难度及计算。 数据构造第 7 页 共 30 页第二章 线性表2.1 线性表的逻辑构造特征存在唯一的一个被称作第一个的数据元素；存在唯一的一个被称作最终一个的数据元素；除第一个元素之外，集合中的每个数据元素均只有一个前驱；除最终一个元素之外，集合中的每个数据元素均只有一个后继。2.2 线性表的依次存储构造1.用一组连续的存储单元依次存储线性表的数据元素。在线性表的依次存储表示中，只要确定了线性表的起始位置，线性表中任一数据元素都可随机存取。线性表的依次存储构造是一种随机存取的存储构造。LOC(ai+1) = LOC(ai) + lLOC(ai+1) = LOC(a1) + i*lLOC(ai)表示元素 ai 的存储位置； LOC(a1) 表示第一个数据元素的存储位置，通常称为线性表的起始位置或基地址每个数据元素占用 l 个存储单元。2.线性依次表上的插入是指在第 i(1in+1)个位置插入一个新的数据元素，需将第 i 至第 n共(n-i+1)个元素后移留意：Ø 依次表中数据区域有 listSize 个存储单元，所以在向依次表中做插入时先检查表空间是否满了，在表满的状况下不能再做插入，否那么产生溢出错误。Ø 要检验插入位置的有效性，这里 i 的有效范围是：1 <= i <= n + 1，其中 n 为原表长。Ø 留意数据的挪动方向算法时间困难度：挪动元素个数：n-i+1平均挪动元素个数：n/2Tn=On；3.线性依次表上的删除是指第 i (1in)个数据元素删除掉，需将第 i+1 至第 n 共n-i)个元素前移留意：Ø 删除第 i 个元素，i 的取值为 1 <= i <= n ,否那么第 i 个元素不存在，因此，要检查删除位置的有效性。Ø 当表空时不能做删除。Ø 删除 ai 之后，该数据已不存在，假设须要，先取出 ai，再做删除。 算法时间困难度：挪动元素个数：n-i平均挪动元素个数：n-1/2Tn=On； 数据构造第 8 页 共 30 页4.线性表的依次存储。优点：逻辑相邻，物理相邻可以实现数据元素的随机存取；缺点：在作插入或是删除操作时，须要挪动大量数据元素2.3 线性表的链式存储构造1.线性表链式存储构造的特点：用一组随意的存储单元存储线性表的数据元素。在线性表的链式存储中，在进展插入或是删除操作时，不须要进展数据元素的挪动，但不能实现数据元素的随机存取。2.线性链表的表示：数据元素、数据元素之间的关系；数据域存储数据元素，指针域存储数据元素之间的关系：干脆后继的存储位置，线性链表：每个节点只包含一个指针域3.假定指针 p 指向线性链表中的第 i 个数据元素，那么 p->next 为指向线性链表中第 i+1 个数据元素的指针。即 p->data 为 ai， p->next ->data 为 ai+1。(*p)表示 p 所指向的结点(*p).dataÛp->data 表示 p 指向结点的数据域(*p).nextÛp->next 表示 p 指向结点的指针域4.在单链表中查找第 i 个元素Status getElem_L(LinkList L, int i, ElemType &e) /获得线性链表中的第 i 个数据元素p = L->next; j = 1;while (p && j < i)p = p -> next;+ j;if ( !p j > i) return ERROR;return p -> data; / GetElem_L S->next = P->next；P->next = S; 数据构造第 9 页 共 30 页Status listInsert_L(LinkList &L, int i, ElemType e)p = L;j = 0;while (p && j < i - 1)p = p -> next; + j；if ( !p j > i - 1) return ERROR;s = (LinkList) malloc ( sizeof (LNode); s -> data = e; s -> next = p -> next; p -> next = s;return OK;P - next = P - next - next; 或q=p->next; p->next=q->next;free(q);Status listDelete_L(LinkList &L, int i) p = L; j = 0;while (p -> next && j < i - 1)p = p -> next; +j; if ( !(p -> next) j > i - 1)return ERROR; / 删除位置不合理q = p -> next ; p -> next = q -> next; free(q); / 删除并释放结点return OK; / ListDelete_L7.循环链表：表中最终一个结点的指针域指向头结点，整个链表形成一个环。循环链表的操作和单链表根本一样，差异仅在于，判别链表中最终一个结点的条件不再是"后继是否为空"，而是"后继是否为头结点"。(1)单链表 p 或 p->next=NULL(2)循环链表 p->next=L8.双向链表有两个指针域，一个指向干脆前驱，一个指向干脆后继。1向双向链表中插入一个结点： 数据构造第 10 页 共 30 页s-prior = p-prior；p-prior-next = s；s-next = p；p-prior = s；2向双向链表中插入一个结点：s-prior = p；s-next = p->next；p->next-prior = s；p-next = s；3从双向链表中删除一个结点 p-prior-next = p-next； p-next-prior = p-prior；第三章 栈和队列3.1 栈和队列的逻辑构造特征1.栈stack和队列queue是两种重要的线性构造，特别性在于其根本操作是线性表操作的子集，是操作受限的线性表操作限定在两个端点进展，为具有限定性的数据构造。栈按“后进先出的规那么进展操作，队列按“先进先出的规那么进展操作。 数据构造第 11 页 共 30 页2.栈是限定在表尾进展插入和删除操作的线性表。允许插入,删除的一端称为栈顶(top),另一端称为栈底(bottom)。3.栈的根本运算主要有两个： Push(S, e)，进栈，插入压入元素 e 为新的栈顶元素， Pop(S)，出栈，删除弹出 S 的栈顶元素。如：假设元素入栈的依次为 1234，为了得到 1342 出栈依次，操作序列为：Push(S, 1)，Pop(S)，Push(S, 2)，Push(S, 3)，Pop(S)，Push(S, 4)，Pop(S)，Pop(S)。3.2 栈的依次存储构造1.依次栈：利用一组地址连续的存储单元一次存放从栈底到栈顶的数据元素，用指针 top 指示栈顶元素在依次栈中的位置。top 指向栈顶元素的下一个位置 top 指向栈顶元素入栈： *s->top+= e先压后加 *+s->top= e先加后压出栈： e = *-S.top先减后弹 e = *S.top-先弹后减Ø 入栈时，首先判栈是否满了，栈满的条件为：，栈满时，不能入栈; 否那么出现空间溢出，引起错误，这种现象称为上溢。 Ø 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否那么产生错误。通常栈空时常作为一种限制转移的条件。top 指向栈顶元素的下一个位置 top 指向栈顶元素初始化： top=0 top=-1判栈空： top=0 top=-1入栈： vtop+=x先压后加 v+top=x先加后压栈满： top-base>=stacksize; top-base>=stacksize-1;出栈： y=v-top)先减后弹 y=vtop-)先弹后减3.两栈共享空间:top0表示第一个栈的栈顶; top1表示第二个栈的栈顶栈空:top0=-1; top1=n入栈: a+top0=e; a-top1=e栈满:top0+1=top1出栈: e= atop0 - ; e=atop1+4.关于依次栈的说明:入栈时，首先判栈是否满了，栈满时，不能入栈; 否那么出现空间溢出，引起错误，这种现象称为上溢。 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否那么产生错误。通常栈空时常作为一种限制转移的条件。 数据构造第 12 页 共 30 页3.3 栈的依次链式存储入栈：p = new LNode ; / 建新的结点if(!p) exit(1) ; / 存储支配失败p -> data = e; p->next=S->top ;/ 链接到原来的栈顶S->top = p; / 挪动栈顶指针出栈：if ( !S->top )return NULL; else e=S->top->data; / 返回栈顶元素q = S->top; S->top=S->top->next; /修改栈顶指针free(q); / 释放被删除的结点空间return e;3.4 栈的应用举例#define NUM 10void conversion(int N，int r) int sNUM,top; /*定义一个依次栈*/int x;top = -1; /*初始化栈*/while ( N ) s+top = N % r; /*余数入栈 */N = N / r ; /* 商作为被除数接着 */while (top != -1) x = stop -; 数据构造第 13 页 共 30 页printf(“%d,x);2.括号匹配的检验：3.表达式求值 ：熟识前缀、中缀和后缀表达式，表达式求值时栈的状态变更。4.栈及递归的实现：熟识运用递归解决3.5 队列的逻辑构造特征队列: 只允许在一端进展插入，而在另一端删除元素。允许插入的一端为队尾(rear),允许删除的一端为队头(front) 。3.6 队列的依次存储构造1.循环队列的依次存储构造: 队列存放数组被当作首尾相接的表处理。队头、队尾指针加 1 时用语言的取模(余数)运算实现。队列初始化：front = rear = 0;队空条件：front = rear;队满条件：(rear+1) % MAXQSIZE = front队头指针进 1: front = (front+1) % MAXQSIZE; 队尾指针进 1: rear = (rear+1) %MAXQSIZE;队中元素个数：rear-front+ MAXQSIZE% MAXQSIZE2. 链式队列：进队：p = (QueuePtr) malloc (sizeof (QNode);if (!p)return 0; /存储支配失败p->data = e; p->next = NULL;Q->rear->next = p; Q.rear = p;出队：if (Q->front = Q->rear) return NULL;p = Q->front->next; e = p->data;Q->front->next = p->next;if (Q->rear = p) Q->rear = Q->front;free (p); return e; 数据构造第 14 页 共 30 页第四章 串、数组和广义表4.1 串相关术语串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特别线性表。串长：串中字符个数n0. n=0 时称为空串 Æ。空白串：由一个或多个空格符组成的串。子串：串 s 中随意个连续的字符序列叫 s 的子串; s 叫主串。子串位置：子串的第一个字符的序号。字符位置：字符在串中的序号串相等：串长度相等，且对应位置上字符相等。串的逻辑构造和线性表极为相像，区分仅在于串的数据对象约束为字符集； 串的根本操作和线性表有很大差异。在线性表的根本操作中，大多以“单个元素作为操作对象；在串的根本操作中，通常以“串的整体作为操作对象。4.2 串的根本操作熟识以下操作的意义：StrAssign (&T, chars) StrCopy (&T, S)DestroyString (&S)StrEmpty (S)StrCompare (S, T)StrLength (S) Concat (&T, S1, S2)SubString (&Sub, S, pos, len)Index (S, T, pos)Replace (&S, T, V)StrInsert (&S, pos, T)StrDelete (&S, pos, len)ClearString (&S)4.3 数组1.二维数组的依次存储构造及地址计算方式。úúûùêêëé=2 , 1 2 , 1,2 , 1 2 , 1. .d d c dj id c c cmna aaa aA设一般的二维数组是 Ac1.d1, c2.d2，这里 c1,c2 不愿定是 0。L：单个元素长度那么行优先存储时的地址公式为：LOC(aij)=LOC(c1，c2)+(i-c1)*(d2-c2+1)+(j-c2)*L 数据构造第 15 页 共 30 页二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+(i-c1)*L2.对称矩阵的压缩存储：在对称矩阵中，只需存储对称矩阵的下半部分。所需空间数为：n×n+1/2。设一般的二维数组是 Ac1.d1, c2.d2，这里 c1,c2 不愿定是 0，对应一维存储空间 SA 的起始值是 C3。那么行优先存储时的地址公式为：( ) ( )( ) ( )ïîïíì< + - +- - ´ -³ + - +- - ´ -=j i c c ic j c jj i c c jc i c ik3 21 13 21 121213.三角矩阵：假设 n 阶方阵中下(上)三角(不包括对角线)中的元均为常量 c 或 0，那么称为上(下)三角矩阵；下三角矩阵：主队角线以上均为同一个常数；上三角矩阵，主队角线以下均为同一个常数。及对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了 n*(n+1)/2 + 1 个元素，设存入数组：SAn*(n+1)/2 + 1中，这种的存储方式可节约 n*(n-1)/2 个存储单元。4.理解下、上三角矩阵：SAk 及 ai,j 的对应关系。5. 稀疏矩阵：将每个非零元素用一个三元组i,j,aij来表示，将三元组按行优先的依次，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，每个稀疏矩阵可用一个三元组表来表示。4.4 广义表1. 广义表是递归定义的线性构造，是线性表的推广，也称为列表(lists) 数据构造第 16 页 共 30 页记为： LS = (1, 2,., n ) 。2. 广义表及线性表的区分和联络: 广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型一样时，就是线性表。3. 广义表 LS =(a1,a2,an )的的性质:1) 广义表中的数据元素有相对次序;2)广义表的长度定义为最外层包含元素个数;3)广义表的深度定义为所含括弧的最大重数;留意:“原子的深度为 0;“空表的深度为 1 4)广义表是一种多层次的数据构造。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，。5)广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。6)广义表可以为其他表所共享。7) 任何一个非空广义表 LS = ( 1, 2, , n)均可分解为: 表头 Head(LS) = 1 和 表尾 Tail(LS) =( 2, , n) 两部分.任何一个非空表，表头可能是原子，也可能是列表；但表尾确定是列表4. 广义表的根本运算: 广义表有两个重要的根本操作，即取头操作Head和取尾操作Tail。要熟识这个两个操作，正确给出一个广义表的这两个操作的结果。第五章 树及二叉树5.1 树构造及根本概念1. 树具有下面两个特点：1) 树的根结点没有前驱结点，除根结点之外的全部结点有且只有一个前驱结点。2) 树中全部结点可以有零个或多个后继结点。2.根本术语：结点(node): 表示树中的元素，包括数据项及假设干指向其子树的分支结点的度(degree): 结点拥有的子树数称为叶子(leaf): 度为 0 的结点孩子(child): 结点子树的根称为该结点的孩子双亲(parents): 孩子结点的上层结点兄弟(sibling): 同一双亲的孩子 数据构造第 17 页 共 30 页树的度: 一棵树中最大的结点度数结点的层次(level): 从根结点算起，根为第一层，它的孩子为第二层深度(depth): 树中结点的最大层次数森林(forest): m(m³0)棵互不相交的树的集合5.2 二叉树构造1. 定义: 二叉树是 n(n 0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成2.特点： 每个结点至多有二棵子树(即不存在度大于 2 的结点) 二叉树的子树有左、右之分，且其次序不能随意颠倒3.根本形态:性质 1: 在二叉树的 第 i 层上至多有 2i -1个结点。性质 2: 深度为 k 的二叉树，至多有 2 k-1 个结点。性质 3: 对随意二叉树 BT ，假设叶结点数为 n0 ，度为 2 的结点数为 n2，那么：n0 = n2 +1性质 4: ë û 1 log 2 + n n 深度为 个结点的完全二叉树的 具有性质 5: 假设对一棵有 n 个结点的完全二叉树的结点按层序编号，那么对任一结点 i(1£i£n)，有： (1) 假设 i=1，那么结点 i 是二叉树的根，无双亲；假设 i>1，那么其双亲是结点 ëi/2û(2) 假设 2i>n，那么结点 i 无左孩子；假设 2i£n，那么其左孩子是结点 2i(3) 假设 2i+1>n，那么结点 i 无右孩子；假设 2i+1£n，那么其右孩子是结点 2i+15.几种特别形式的二叉树：满二叉树： 1 2 个结点的二叉树称为 且有 一棵深度为 -kk特点：每一层上的结点数都是最大结点数完全二叉树：深度为 k，有 n 个结点的二叉树当且仅当其每一个结点都及深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时，称为特点：叶子结点只可能在层次最大的两层上出现；对任一结点，假设其右分支下子孙的最大层次为 l，那么其左分支下子孙的最大层次必为 l 或 l+15.3 二叉树存储1.二叉树的依次存储构造：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 数据构造第 18 页 共 30 页特点：结点间关系蕴含在其存储位置中；奢侈空间，适于存满二叉树和完全二叉树2.二叉树的链式存储构造二叉链表：在 n 个结点的二叉链表中，有 n+1 个空指针域3. 二叉树的链式存储构造三叉链表5.4 二叉树遍历1.二叉树的遍历：先序遍历(DLR) ：先访问根结点,然后分别先序遍历左子树、右子树中序遍历(LDR)：先中序遍历左子树，然后访问根结点，最终中序遍历右子树后序遍历(LRD)：先后序遍历左、右子树，然后访问根结点2.遍历的递归算法:void preOrder(bt) /*先序遍历二叉树 bt*/ if (bt) /*递归调用的完毕条件为 bt 为空*/ visit(bt->data); /*访问结点的数据域*/ preorder(bt->lchild); /*先序递归遍历 bt 的左子树*/ preorder(bt->rchild); /*先序递归遍历 bt 的右子树*/ void inOrder(bt) /*中序遍历二叉树 bt*/ if (bt) /*递归调用的完毕条件为 bt 为空*/ inOrder(bt->lchild); /*中序递归遍历 bt 的左子树*/ 数据构造第 19 页 共 30 页visit(bt->data); /*访问结点的数据域*/ inOrder(bt->rchild); /*中序递归遍历 bt 的右子树*/void postOrder(bt) /*后序遍历二叉树 bt*/ if (bt) /*递归调用的完毕条件为 bt 为空*/ postOrder(bt->lchild); /*后序递归遍历 bt 的右子树*/postOrder(bt->rchild); /*后序递归遍历 bt 的右子树*/visit(bt->data); /*访问结点的数据域*/ 5.5 线索二叉树1. 线索二叉树的定义前驱及后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为线索：指向前驱或后继结点的指针称为线索二叉树：加上线索的二叉链表表示的二叉树叫线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫2. 线索二叉树的实现在有 n 个结点的二叉链表中必定有 n+1 个空链域。在线索二叉树的结点中增加两个标记域ltag :假设 ltag =0, lchild 域指向左孩子；假设 ltag =1, lchild 域指向其前驱rtag :假设 rtag =0, rchild 域指向右孩子；假设 rtag =1, rchild 域指向其后继数据构造第 20 页 共 30 页假设 rt=1, 那么 rc 域干脆指向其后继假设 rt=0, 那么结点的后继应是其右子树的左链尾lt=1)的结点4. 在中序线索二叉树中找结点前驱的方法：假设 lt=1, 那么 lc 域干脆指向其前驱假设 lt=0, 那么结点的前驱应是其左子树的右链尾rt=1)的结点5.6 树和森林1.树和森林及二叉树之间的转换方法: 孩子兄弟表示法数据构造第 21 页 共 30 页5.7 赫夫曼树1. 赫夫曼树(Huffman)带权途径长度最短的树1 依据给定的 n 个权值构成 n 棵二叉树的集合 F，其中每棵二叉树中只有一个带权值的结点；2 在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和；3在 F 中删除这两棵树，同时将新得到的二叉树参与到 F 中；4重复 2)和 3)，直到 F 中只含一棵树为止3.Huffman 编码：数据通信誉的二进制编码1思想：依据字符出现频率编码，使电文总长最短2编码：依据字符出现频率构造 Huffman 树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1；每个字符的编码即为从根到每个叶子的途径上得到的 0、1 序列3译码：从 Huffman 树根开始，从待译码电文中逐位取码。假设编码是“0”，那么向左走；假设编码是“1，那么向右走，一旦到达叶子结点，那么译出一个字符；再重新从根动身，直到电文完毕