[高等教育]数据结构知识点.doc

第一课 绪论覆盖的知识点最小集：我们的地址是，重庆市九龙坡区白市驿镇金桥2号重庆市农业学校 1. 数据结构、数据元素、数据项、数据对象、数据的概念2. 数据的逻辑结构和存储结构的概念3. 算法设计时的注意事项4. 时间复杂度的概念及度量方法5. 空间复杂度的概念及度量方法知识点细化：1-001数据结构的基本概念数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构由数据的逻辑结构、存储结构和对数据的操作三部分组成。数据元素是数据的基本单位。数据项是数据的不可分割的最小单位。数据对象是性质相同的数据元素的集合，是数据的子集。数据是所有需输入计算机并为程序所处理的对象的总称。1-002数据的逻辑结构和存储结构，对后面的名词要能区分哪些是属于逻辑结构哪些属于物理结构数据的逻辑结构指的是数据元素间的逻辑关系，分为集合、线性结构、树形结构和图形结构，或分为线性结构和非线性结构。数据的物理结构指的是数据元素及其间逻辑关系在计算机中的表示，也称存储结构。其中数据元素间关系的表示有顺序映象（顺序存储结构）和非顺序映象（链式存储结构）两种方式，前者以存储地址上的联系来体现数据元素之间的逻辑关系，后者则通过指针的指向来体现数据元素之间的逻辑关系。1-003算法设计时的注意事项算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法的特性：有穷性、确定性、可行性、零或多个输入、一或多个输出。算法设计的要求：正确性、可读性、健壮性、高效性。1-004时间复杂度的概念及度量方法算法的时间复杂度是算法执行效率的量度，记作：T(n)=O(f(n)，其中n为问题的规模。衡量算法效率时，通常在算法中选择一种不可再分解的基本操作（该操作的重复执行次数应与算法的执行时间成正比），若该操作的执行次数为f(n)，则记该算法的时间复杂度为O(f(n)。若基本操作的执行次数与输入数据有关，则可求算法的平均时间复杂度或最坏时间复杂度。一般，当所有可能的输入数据集及其出现概率均可知时，可求算法的平均时间复杂度，否则求最坏情况下的时间复杂度。1-005空间复杂度的概念及度量方法算法的空间复杂度是算法执行时所需存储空间的量度，记作：S(n)=O(f(n)，其中n为问题的规模。分析算法空间复杂度时，一般只考虑执行算法所需辅助空间，但若输入数据所占空间与算法本身有关，则也应计算在内。若执行算法所需辅助空间与输入数据有关，则可求最坏情况下的空间复杂度。第二课 线性表覆盖的知识点最小集：1. 线性表的定义和基本操作2. 线性表的实现(1) 顺序存储(2) 链式存储(3) 线性表的应用知识点细化：2-010线性表基本概念线性表是个数据元素构成的有限序列。表长指线性表中数据元素的个数，表长。空表指表长为的线性表。若线性表非空，则表中第一个元素没有直接前趋，有且仅有一个直接后继；表中最后一个元素没有直接后继，有且仅有一个直接前趋；其余每个数据元素有且仅有一个直接前趋，有且仅有一个直接后继。2-011线性表的基本操作(1)取元素GetElem(L,i,&e)初始条件：线性表L已存在，1iListLength(L)操作结果：用e返回L中第i个数据元素的值(2)插入ListInsert(&L,i,e)初始条件：线性表L已存在，1iListLength(L)+1操作结果：在L中第i个位置之前插入数据元素e，L的长度加1(3)删除ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1iListLength(L)操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减12-012线性表的顺序存储方式用一组地址连续的存储单元依次存储线性表中数据元素，以数据元素物理地址上的相邻关系表示其逻辑上的先后关系。以顺序存储方式保存的线性表也称顺序表。在顺序表中访问结点时，由于第i个元素就存储在相对地址为i-1的位置上（随机存取），算法时间复杂度为O(1)。设顺序表长为n，则在第i（1in+1）个元素前插入时，需移动n-i+1个元素。设在各位置上插入元素的概率相等，则需移动元素的平均个数为n/2，算法时间复杂度为O(n)。设顺序表长为n，则删除第i（1in）个数据元素时，需移动n-i个元素。设删除任一元素的概率相等，则需移动元素的平均个数为：(n-1)/2，算法时间复杂度为O(n)。2-013以静态分配方法实现顺序表由于线性表的长度是可变的，采用静态分配，则需定义最大可能长度，并需设变量记录线性表长。#define MAXSIZE 1000 /最大可能长度typedef structElemType elemMAXSIZE; /保存数据元素int len; /线性表长度SqList; /顺序表类型名 (静态线性表就是用数组来存储的那种形式)2-014以一次性动态分配方法实现顺序表采用一次性的动态分配方法时，需定义最大可能长度，并需设变量记录线性表长。#define MAXSIZE 1000 /最大可能长度typedef structElemType *elem; /保存首地址int len; /线性表长度SqList; /顺序表类型名 （动态的就是需要用指针来实现的）2-015以带增量的动态分配方法实现顺序表采用带增量的动态分配方法时，需定义初始分配量和增量，并需分别设变量以记录线性表长及当前分配总量。#define LIST_INIT_SIZE 100 /初始分配量，以数据元素个数为单位#define LISTINCREMENT 10 /增量typedef structElemType *elem; /保存首地址int len; /线性表长度int listsize; /当前分配量，以数据元素个数为单位SqList; /顺序表类型名在该结构上实现三个基本操作。2-016线性表的链式存储方式用一组任意的（可连续可不连续）存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。根据所用指针的类型、个数、方法等的不同，又可分为：、循环链表、双向线性链表（单链表）链表、双向循环链表、静态链表等。2-017线性链表（单链表）及其特点每个结点由两个域组成，其中数据域用以保存数据元素的值，指针域用以保存其直接后继结点的绝对地址。表中最后一个结点的指针域值为空指针NULL。在首元结点前还可附设头结点，以方便运算的实现（无论表空与否，头指针值不变；插入时不必特别判断是否在第一个元素之前插入；删除时不必特别判断是否删除第一个元素）。头结点的数据域一般不使用。头结点（若表中不含头结点则为首元结点）的地址保存在头指针中。typedef struct LNodeElemType data; /数据域struct LNode *next; /指针域LNode,*LinkList;在该结构上实现三个基本操作。在单链表中访问结点时，必须从头指针开始顺序查找该结点，指针的移动是其中的基本操作，查找第i个结点时需移动i-1次。设查找任一元素的概率相等，则需移动指针的平均次数为(n-1)/2，算法时间复杂度为O(n)。在单链表中插入结点时，时间主要用于查找插入位置，即查找第i-1个结点上。算法的时间复杂度为O(n)。在单链表中删除结点时，时间主要用于查找待删结点。算法的时间复杂度为O(n)。2-018循环链表及其特点循环链表的结点结构同单链表，但表中最后一个结点的指针域保存头结点（若表中不含头结点则为首元结点）的绝对地址。在循环链表中，从任一结点出发均可访问到表中其余结点。循环链表上基本操作的实现与单链表基本相同，主要区别在于算法中的循环条件。2-019双向链表及其特点双向链表中每个结点由一个数据域和两个指针域组成，其中数据域用以保存数据元素的值，一个指针域用以保存其直接后继结点的绝对地址，另一个指针域用以保存其直接前趋结点的绝对地址。双向链表上基本操作的实现与单链表基本相同，主要区别在于需同时考虑两个方向上的指针。typedef struct DuLNodeElemType data; /数据域struct DuLNode *prior; /指向直接前驱的指针域struct DuLNode * next; /指向直接后继的指针域DuLNode,*DuLinkList;2-020双向循环链表及其特点双向循环链表的结点结构同双向链表，但表中最后一个结点的next指针域保存头结点（若表中不含头结点则为首元结点）的绝对地址，头结点（若表中不含头结点则为首元结点）的prior指针域保存表中最后一个结点的绝对地址。双向循环链表上基本操作的实现与双向链表基本相同，主要区别在于算法中的循环条件。2-021静态链表及其特点静态链表的结点保存在一段连续的存储空间中，每个结点由两个域组成，其中数据域用以保存数据元素的值，指针域保存其直接后继结点的相对地址。相对地址为的结点用作头结点，其指针域存放首元结点的相对地址。表中最后一个结点的指针域值为。#define MAXSIZE 1000 /链表的最大长度typedef struct ElemType data; /数据域int next; /指针域SLNode,SLinkListMAXSIZE;2-022线性表的顺序存储与链式存储的优缺点比较，及各自适用场合若线性表采用顺序存储，则：可随机存取表中数据元素；存储密度大；(优点)但：插入、删除时需大量移动元素（在最后一个元素的后面插入新元素、删除最后一个元素时不需移动元素）；需预先估计所需存储空间，可能使存储空间不能得到充分利用，且表的最大长度受此限。适用于元素总数有上限、仅在表尾进行插入删除的应用。(缺点)若线性表采用链式存储，则：插入、删除时不需移动元素（在第i个结点之前插入或删除第i个结点时，均需移动辅助指针，使其指向第i-1个结点）；不需预估预分配存储空间，而是在插入时按需分配，在删除时及时释放（但这也导致运行效率降低）；表的最大长度只受内存容量的限制；但：对表中数据元素的存取为顺序存取；需占用额外的存储空间来保存元素间关系。适用于元素总数上限难确定，插入、删除操作频繁的应用。2-023静态链表与顺序表的相似及不同之处相似：都占用一段连续的存储空间；这段空间的分配可用静态分配方法，也可用动态分配方法。建表时都要要估算最大容量，插入元素前都要先判断是否有空余空间。不同：顺序表通过数据元素物理地址上的相邻来体现元素间的逻辑关系，属于一种顺序存储结构；静态链表借助指针的指向来体现元素间的逻辑关系，属于一个链式存储结构。顺序表中元素是随机存取，静态链表中元素是顺序存取。顺序表中执行插入、删除操作要移动元素，静态链表中不要。2-024线性表的应用基于线性表的各种存储方式实现指定的操作，尤其是各种链表（带头结点、不带头结点）（仅设头指针、仅设尾指针、分设头尾指针）上插入（当前结点之前，当前结点之后，头结点之后，尾结点之后，其它位置），删除（当前结点、前趋结点、后继结点、首元结点、其它结点），分解（一表到多表），归并（多表合一表），查找（顺序表上的顺序和折半查找，链表上的顺序查找）、排序（各种排序方法的实现）等。第三课 栈、队列和数组覆盖的知识点最小集：1. 栈和队列的基本概念2. 栈和队列的顺序存储结构3. 栈和队列的链式存储结构4. 栈和队列的应用5. 特殊矩阵的压缩存储知识点细化：3-001栈的基本概念栈是限定仅在表尾端进行插入、删除的线性表；表尾端称栈顶，an称栈顶元素；表头端称栈底，a1称栈底元素。栈的长度即栈中元素个数。长度为0的栈称空栈。向栈中插入元素称入栈，从栈中删除元素称出栈。栈的修改是按后进先出的原则进行的。3-002栈的顺序存储方式与线性表的顺序存储方式类似：三种分配方法；线性表长度分量栈顶指针分量（指向栈顶元素的下一个位置）。以顺序存储方式保存的栈称顺序栈。设采用静态分配。实现入栈和出栈操作。#define MAXSIZE 1000 /栈的最大容量typedef struct ElemType elemMAXSIZE; /保存数据元素，以低地址为栈底 int top; /栈顶指针SqStack;3-003栈的链式存储方式与单链表类似：带/不带头结点；插入、删除操作点（即栈顶端）放在靠近头指针的一端。以链式存储方式保存的栈称链栈。实现入栈和出栈操作typedef struct SNode ElemType data; struct SNode *next;SNode,*LinkStack;3-101队列的基本概念队列是限定仅在表尾端进行插入，而在表头端进行删除的线性表。表头端称队头，a1称队头元素；表尾端称队尾，an称队尾元素。队列的长度即队列中元素个数。长度为0的队列称空队。向队列中插入元素称入队，从队列中删除元素称出队。队列的修改是按先进先出的原则进行的。双端队列是限定仅在表的两端进行插入删除操作的线性表（如果规定从哪端入的只能从哪端出，则退化为两个栈底相邻的栈）。输入受限的双端队列是插入操作仅在一端进行而删除操作可在两端进行的线性表。输出受限的双端队列是删除操作仅在一端进行而插入操作可在两端进行的线性表。3-102队列的顺序存储方式线性表的顺序存储方式去除线性表长度分量，添加指向队头元素所在位置的队头指针以及指向队尾元素的下一个位置的队尾指针产生假溢出问题三个解决方案：(1)每删一个元素，其余元素向前移；(2)发生假溢出时才移动剩余元素；(3)采用循环队列，不移动元素，但不能采用带增量的动态分配，且需解决队空、队满判定条件相同的问题，解决方法可为：添加长度分量（添加标志分量）浪费一个元素的存储空间。循环队列另一设计方案：以数组存储元素，以队尾指针指示队尾元素所在位置，并记录队列长度。循环队列只能采用静态分配或一次性动态分配，不能采用带增量的动态分配，因而队列最大长度应能预估。3-103循环队列的入队和出队设采用一次性动态分配，设置队头队尾指针，以浪费一个元素存储空间的方式解决队空、队满判定条件相同的问题。实现入队、出队和求队列长度操作。#define MAXSIZE 1000typedef struct ElemType *base; int front; int rear;CirQueue;3-104队列的链式存储方式与单链表类似：带/不带头结点；删除操作点（即队头端）放在靠近头指针的一端，另设尾指针，指向队尾元素结点，以方便插入操作的执行。以链式存储方式保存的队列称链队列。链队列在执行出队操作时要考虑空队列和队列中只有一个结点这两种特殊情况。3-105链队列的入队和出队实现入队和出队操作。typedef struct QNode ElemType data; struct QNode *next;QNode;typedef struct QNode* front; QNode* rear;LinkQueue;3-106栈和队列的应用栈在表达式求值、括号匹配、进制转换、递归问题等中都有应用。队列在共享打印机缓冲池、消息队列、二叉树的层序遍历、图的广度优先遍历等中都有应用。3-107从递归到非递归一个函数直接或间接调用自己即为递归。函数递归是因为：(1)有很多数学函数是递归定义的；(2)有些数据结构本身就有递归性（广义表、树、二叉树），其上操作常用递归描述；(3)有些问题本身虽无明显递归结构，但用递归求解较简单（汉诺塔）。递归算法可转换为用栈来实现的非递归算法。3-201对称阵的定义及压缩存储若n阶方阵A有aij=aji，i,j1,n/0,n-1，则称A为n阶对称阵。压缩存储时用一组地址连续的存储单元按行或列优先的顺序保存对称阵上或下三角（含对角线）中的数据元素，共n(n+1)/2个。对矩阵进行压缩存储是为了节省空间，仍属随机存取，但计算地址的运算会复杂。3-202上三角阵的定义及压缩存储若n阶方阵A有aij=C，i,j1,n/0,n-1且ij，C为常量，则称A为n阶上三角阵。上三角阵中下三角部分元素（不含对角线）的值为常量。压缩存储时用一组地址连续的存储单元按行或列优先的顺序保存上三角（含对角线）中的数据元素，再加一个下三角常量，共n(n+1)/2+1个。3-203下三角阵的定义及压缩存储若n阶方阵A有aij=C，i,j1,n/0,n-1且ij，C为常量，则称A为n阶下三角阵。下三角阵中上三角部分元素（不含对角线）的值为常量。压缩存储时用一组地址连续的存储单元按行或列优先的顺序保存下三角（含对角线）中的数据元素，再加一个上三角常量，共n(n+1)/2+1个。3-204对角阵的定义及压缩存储若n阶方阵A中除主对角线及其上下若干条对角线上的元素之外，其余元素均为0，则称对角阵。将矩阵中的非零元按某种次序（行优先、列优先、对角线顺序等）存储于一组地址连续的存储单元。对n阶x对角阵A进行压缩存储，采用行优先/列优先/指定的对角线顺序-第一元素为a00/a11，保存在足够大的一维数组e中。若aij保存在ek中，要求由i,j值求k值。3-205稀疏阵的定义及压缩存储设在mn矩阵中，有t个数据元素不为零，则通常认为当时，称该矩阵为稀疏矩阵，其中称稀疏因子。对稀疏矩阵进行压缩存储时，可只保存其中非零元，同时还需指明非零元所处的行列位置及总的行数、列数（可再加非零元个数），此即稀疏矩阵的三元组表示法。此时不能再随机存取。第四课 树与二叉树覆盖的知识点最小集：1. 树的基本概念2. 二叉树(1) 二叉树的定义及其主要特征(2) 二叉树的顺序存储结构和链式存储结构(3) 二叉树的遍历(4) 线索二叉树的基本概念和构造3. 树、森林(1) 树的存储结构(2) 森林与二叉树的转换(3) 树和森林的遍历4. 树与二叉树的应用(1) 二叉排序树(2) 平衡二叉树(3) 哈夫曼（Huffman）树和哈夫曼编码知识点细化：4-001树和结点树是n（n0）个结点的有限集。若n=0则为空树，记为。若n0，则：有且仅有一个根结点；若n1，则其余结点可分为m（m0）个互不相交的有限集T1,T2,Tm，其中每一集合又是一棵树，并称根的子树。若将树中结点的各子树看成从左至右是有次序的，即不能互换的，则称该树为有序树，否则称无序树。结点可分为分支结点（根结点+内部结点）和叶子结点。结点的度即结点拥有的子树数。树的度是树内各结点的度的最大值。结点的层次从根开始定义起，根为第一层，根的孩子为第二层，余则类推。树的深度（高度）即树内结点的层次的最大值。4-002二叉树二叉树是具有如下特点的树型结构：每个结点至多只有两棵子树；二叉树的子树有左右之分。二叉树有五种基本形态：空二叉树只有根结点根结点只有左子树根结点只有右子树根结点左右子树都有。二叉树和度为2的有序树的本质区别在于有序树上结点若只有一个孩子，则孩子无次序之分。4-003满二叉树和完全二叉树满二叉树是深度为k且有2k-1个结点的二叉树。若含n个结点的二叉树中各结点位置与同深度的满二叉树按层序的前n个结点位置相对，则称完全二叉树。满二叉树一定是完全二叉树，反之未必。若完全二叉树上有n个结点按层序从1开始编号，则第个结点是最后一个有孩子的结点；若n是偶数，则该完全二叉树上有一个度为1的结点，若n是奇数，则该完全二叉树上没有度为1的结点。4-004森林森林为m（m0）棵互不相交的树的集合。4-101二叉树性质一在二叉树的第i层上最多有2i-1个结点(i1)。【证明】当i=1时，只有一个根结点。2i-1=20=1，结论成立。假设第k层上最多有2k-1个结点二叉树中每个结点最多有2个孩子第k层结点的孩子总数最多为2k-12=2k个第k+1层上的结点均为第k层结点的孩子第k+1层上最多有2k=2(k+1)-1个结点由可得结论成立。4-102二叉树性质二深度为k的二叉树最多有2k-1个结点。(k1)【证明】由二叉树性质1可知在二叉树的第i层上最多有2i-1个结点(i1)，因此深度为k的二叉树最多结点数为：。深度为k的m叉树最多有个结点。4-103二叉树性质三对任意二叉树T，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。【证明】设二叉树中度为的结点数为n1二叉树中结点的度只能为0、1、2结点总数n=n0+n1+n2；又含n个结点的二叉树必有n-1条分支，这些分支是有孩子的结点提供的分支数b=n-1=2*n2+1*n1结点总数n=2*n2+1*n1+1；由和，可得n0=n2+1，结论成立。4-104二叉树性质四具有n个结点的完全二叉树的深度为。【证明】设完全二叉树深度为k前k-1层元素个数为2k-1-1又第k层元素个数至少为1，最多为2k-1深度为k的完全二叉树最多2k-1个结点，最少2k-1个结点（另：深度为k的二叉树最多2k-1个结点，最少k个结点）即(2k-1-1)+1n(2k-1-1)+2k-1，即2k-1n2k-12kk-1log2nklog2nklog2n+1k是整数k=4-105二叉树性质五若对一棵含n个结点的完全二叉树中的结点按层序进行编号，则其中编号为i的结点有：若i=1，则结点i为二叉树的根，无双亲，若1n，则结点i无左孩子，否则其左孩子为结点2i；若2i+1n，则结点i无右孩子，否则其右孩子为结点2i+1。4-106二叉树的顺序存储结构用一段地址连续的存储空间，从下标为1的存储单元开始按层序依次保存完全（满）二叉树中的数据元素，以结点间存储地址上的联系（按层序编号为i的结点保存在下标为i的存储单元，其双亲若存在则保存在下标为i/2的存储单元，其左孩子若存在则保存在下标为2*i的存储单元，其右孩子若存在则保存在下标为2*i+1的存储单元），体现结点间双亲与孩子的关系。二叉树顺序存储结构的优点包括：(1)便于由一个结点找其双亲结点、孩子结点；(2)存储密度大。缺点包括：(1)需预测二叉树上可能的最多结点数。适用：完全二叉树、满二叉树，若用于保存一般二叉树，则最坏情况下，深度为k的二叉树只含k个结点却需使用长度为2k-1的一维数组保存。4-107二叉树的二叉链表存储结构每个结点含三个域，即数据域、指向左孩子的指针域和指向右孩子的指针域。设置头指针，指向根结点。含n个结点的二叉链表中有n+1个空链域。typedef struct BiTreeNode TElemType data; struct BiTreeNode *lchild; struct BiTreeNode *rchild;BiTreeNode,*BiTree;4-108二叉树的三叉链表存储结构在二叉链表的基础上，每个结点再增加一个指向双亲的指针域。typedef struct BiTreeNode TElemType data; struct BiTreeNode *lchild; struct BiTreeNode *rchild; struct BiTreeNode *parent;BiTreeNode,*BiTree;4-109二叉树的中序遍历【方法】中序遍历左子树；访问根结点；中序遍历右子树。【递归算法】int InOrderTraverse(BiTree T, int (*visit)(TElemType e) /若遍历成功则返回1，否则返回0 if (!T) if (!InOrderTraverse(T-lchild,visit) return 0; /中序遍历左子树 if (!visit(T-data) return 0; /访问根结点 if (!InOrderTraverse(T-rchild,visit) return 0; /中序遍历右子树 return 1;/InOrderTraverse 【非递归算法】int InOrderTraverse(BiTree T, int (*visit)(TElemType e) /若遍历成功则返回1，否则返回0 InitStack(S); p=T; while (p|!StackEmpty(S) if (p) Push(S,p); p=p-lchild; else Pop(S,p); if (!visit(p-data) return 0; p=p-rchild; /else /while return 1;/InOrderTraverse辅助栈的最大容量等于二叉树的深度，最坏情况下为。二叉树遍历算法中的基本操作是访问结点，无论按何种次序，对含个结点的二叉树，时间复杂度均为O(n)。4-110二叉树的先序遍历【方法】访问根结点；先序遍历左子树；先序遍历右子树。【递归算法】int PreOrderTraverse(BiTree T, int (*visit)(TElemType e) /若遍历成功则返回1，否则返回0 if (!T) if (!visit(T-data) return 0; /访问根结点 if (!PreOrderTraverse(T-lchild,visit) return 0; /先序遍历左子树 if (!PreOrderTraverse(T-rchild,visit) return 0; /先序遍历右子树 return 1;/PreOrderTraverse【非递归算法】int PreOrderTraverse(BiTree T, int (*visit)(TElemType e) /若遍历成功则返回1，否则返回0 InitStack(S); p=T; while (p|!StackEmpty(S) if (p) if (!visit(p-data) return 0; if (p-rchild) Push(S,p-rchild); p=p-lchild; else Pop(S,p); /else /while return 1;/PreOrderTraverse4-111二叉树的后序遍历【方法】后序遍历左子树；后序遍历右子树；访问根结点。【递归算法】int PostOrderTraverse(BiTree T, int (*visit)(TElemType e) /若遍历成功则返回1，否则返回0 if (!T) if (!PostOrderTraverse(T-lchild,visit) return 0; /后序遍历左子树 if (!PostOrderTraverse(T-rchild,visit) return 0; /后序遍历右子树 if (!visit(T-data) return 0; /访问根结点 return 1;/PostOrderTraverse【非递归算法】typedef struct BiTreeNode node; int flag; /0表示结点node的右子树尚未被访问，1表示结点node的右子树已被访问SElemType;int PostOrderTraverse(BiTree T, int (*visit)(TElemType e) /若遍历成功则返回1，否则返回0 InitStack(S); p=T; while (p|!StackEmpty(S) if (p) temp.node=p; temp.flag=0; Push(S, temp); p=p-lchild; else Pop(S, temp); if (temp.flag)/出栈结点的左、右子树均已被访问 if (!visit(temp.node-data) return 0; else/出栈结点的右子树尚未被访问 temp.flag=1; Push(S, temp); /修改标志位后重新入栈 p=temp.node-rchild; /处理右子树 /if /while/PostOrderTraverse4-112二叉树的层序遍历【方法】按结点所在层次，由低层向高层依次遍历；同层中按自左向右次序遍历。【算法】int LevelOrderTraverse(BiTree T, int (*visit)(TElemType e) /若遍历成功则返回1，否则返回0 if (!T) return 1; /空二叉树 InitQueue(Q); /初始化辅助队列 if (!visit(T-data) return 0; /访问根结点 EnQueue(Q, T); /指向根结点的指针入队 while (!QueueEmpty(Q) /若队列非空 DeQueue(Q, p); /队头指针出队 if (p-lchild) /先访问p所指结点的左孩子，再访问其右孩子 if (!visit(p-lchild-data) return 0; EnQueue(Q,p-lchild); /if if (p-rchild) if (!visit(p-rchild-data) return 0; EnQueue(Q,p-rchild); /if /while return 1;/LevelOrderTraverse4-201线索二叉树二叉树的任何一种遍历，其实质均为对非线性结构的线性化。若将遍历序列中所体现的结点间的线性关系保存在二叉树的存储结构中，这样的二叉树称线索二叉树，存储结构称线索链表。线索链表中指向结点的前驱、后继的指针称线索。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。一棵二叉树在中序线索化后，其中空的链域的个数是2。一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是2；一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是1。一棵右子树为空的二叉树在后序线索化后，其中空的链域的个数是2；一棵左右子树均不空的二叉树在后序线索化后，其中空的链域的个数是1。4-202线索链表【方法一】在二叉链表中每个结点上增加两个指针域，分别用以指向该结点在遍历序列中的直接前驱和直接后继。【方法二】利用二叉链表中的空链域保存结点间的线性关系。规定：若结点的lchild域为空，则在其中保存指向其直接前驱的指针；若结点的rchild域为空，则在其中保存指向其直接后继的指针；每个结点再设两个标志域ltag和rtag，当指针域指向孩子时标志域取值为0，否则取值为1。在线索链表中还可添加头结点：头结点的data域不使用，其lchild域指向根，ltag域为，rchild域指向遍历序列中的尾结点，rtag域为1。同时，令遍历序列中首结点的lchild域和尾结点的rchild域均指向头结点。typedef enum Link,Thread PointerTag; /Link值为，Thread值为typedef struct BiThrNode TElemType data; struct BiThrNode *lchild; struct BiThrNode *rchild; PointerTag ltag; PointerTag rtag;BiThrNode, *BiThrTree;4-203中序线索化【方法】对二叉链表T进行中序线索化，生成二叉中序线索链表Thrt。生成头结点，其data域不用，ltag=Link，rtag=Thread；若二叉树为空，则头结点的lchild和rchild均指向自己；若二叉树非空，则头结点的lchild指向根，rchild需指向遍历序列中的尾结点，应在遍历完成后处理；对二叉链表进行中序遍历，对于在遍历过程中遇到的每个结点：若lchild域非空则令ltag=Link否则令lchild=指向其直接前驱的指针且令ltag=Thread（在遍历中设指针pre指向刚访问过的结点）若rchild域非空则令rtag=Link否则令rchild=指向其直接后继的指针且令rtag=Thread（此操作需在访问到下一结点时处理，即访问当前结点时，处理其直接前驱的rchild、rtag域）。【递归算法】void InOrderThreading(BiThrTree &Thrt, BiThrTree T) /由二叉链表T生成二叉中序线索链表Thrt Thrt=(BiThrTree)malloc(sizeof(BiThrNode); /生成头结点 if (!Thrt) exit(-2); if (!T) /二叉树为空树 Thrt-lchild=Thrt; Thrt-ltag=Link; Thrt-rchild=Thrt; Thrt-rtag=Thread; /if else Thrt-lchild=T; Thrt-ltag=Link; /头结点的lchild指向二叉链表根结点 pre=Thrt; /pre为指向前驱的指针，在InThreading中需使用，此处用全局变量实现，也可设置为参数 InThreading(T); /调用中序线索化函数处理二叉链表T pre-rchild=Thrt; pre-rtag=Thread; /中序遍历完成，pre指向遍历序列中的尾结点，该结点一定无右子树 Thrt-rchild=pre; Thrt-rtag=Thread; /头结点的rchild指向遍历序列中的尾结点 /else/InOrderThreadingvoid InThreading(BiThrTree p) if (p) InThreading(p-lchild); /左子树线索化 if (!p-lchild)p-lchild=pre; p-ltag=Thread; else p-ltag=Link; if (!pre-rchild)pre-rchild=p; pre-rtag=Thread; else pre-rtag=Link; InThreading(p-rchild); /右子树线索化 /ifInThreading【非递归算法】void InOrderThreading(BiThrTree &Thrt, BiThrTree T) /由二叉链表T生成二叉中序线索链表Thrt Thrt=(BiThrTree)malloc(sizeof(BiThrNode); /生成头结点 if (!Thrt) exit(-2); if (!T) /二叉树为空树 Thrt-lchild=Thrt; Thrt-ltag=Link; Thrt-rchild=Thrt; Thrt-rtag=Thread; /if else Thrt-lchild=T; Thrt-ltag=Link; /头结点的lchild指向二叉链表根结点 pre=Thrt; /pre为指向前驱的指针 InitStack(S); p=T; while (p|!StackEmpty(S) if (p) Push(S,p); p=p-lchild; else Pop(S,p); if (!p-lchild)p-lchild=pre; p-ltag=Thread; else p-ltag=Link; if (!pre-rchild)pre-rchild=p; pre-rtag=Thread; else pre-rtag=Link; p=p-rchild; /else /while pre-rchild=Thrt; pre-rtag=Thread; /遍历序列中的尾结点的rchild域指向头结点 Thrt-rchild=pre; Thrt-rtag=Thread; /头结点的rchild域指向遍历序列中的尾结点/ InOrderThreading4-204中序线索二叉树的遍历【方法】对中序线索二叉树进行遍历，可从头结点开始，沿前驱或后继进行遍历。若对中序线索二叉树从首结点起沿后继进行遍历，则遍历序列中首结点是二叉树中最左下的结点。若结点无右子树，则其直接后继由其右指针指向，否则其直接后继为其右子树中最左下的结点。若对中序线索二叉树从尾结点起沿前驱进行遍历，则遍历序列中尾结点由头结点的右指针指向（二叉树中最右下的结点）。若结点无左子树，则其直接前驱由其左指针指向，否则其直接前驱为其左子树中最右下的结点。【算法】Status IOT_Thr(BiThrTree T,Status (*visit)(TElemType e) /对中序线索链表从首结点起，沿后继进行遍历，遍历成功则返回1，否则返回0 p=T-lchild; /p指向根结点 while(p!=T) /第一次判定时若p等于T，则二叉树为空，以后判定时若p等于T，则遍历完成 while (p-ltag=Link) p=p-lchild; /找p的最左下孩子，第一次p指向根，所找结点即遍历序列首结点， /以后p指向刚访问过的结点的右孩子，此时刚访问过的结点，其rtag应为Link if (!visit(p-data) return 0; while(p-rtag=Thread&p-rchild!=T) /若p所指结点的rchild指向其直接后继，且该直接后继不是头结点，即p所指结点不是遍历序列尾结点 p=p-rchild; if (!visit(p-data) return 0; /while while/IOT_Thr4-205先序线索化及其遍历若对先序线索二叉树从首结点起沿后继进行遍历，则遍历序列中首结点是二叉树的根结点。若结点无右子树，则其直接后继由其右指针指向，否则其直接后继为其左孩子（即左子树的根结点），若左孩子不存在，则为其右孩子。若对先序线索二叉树从尾结点起沿前驱进行遍历，则遍历序列中尾结点是二叉树中最右下的结点。若结点无左子树，则其直接前驱由其左指针指向，否则其直接前驱为其双亲（当该结点是其双亲的左孩子或该结点虽是其双亲的右孩子但其双亲并无左孩子时）或为其双亲的左子树中最右下的结点（当该结点是其双亲的右孩子且其双亲有左孩子时），若该结点无双亲（即根结点）则无直接前驱。4-206后序线索化及其遍历若对后序线索二叉树从首结点起沿后继进行遍历，则遍历序列中首结点是二叉树中最左下的结点。若结点无右子树，则其直接后继由其右指针指向，否则其直接后继为其双亲（当该结点是其双亲的右孩子或该结点虽是其双亲的左孩子但其双亲并无右孩子时）或为其双亲的右子树中第一个被访问的结点（所以仍需栈的支持）（当该结点是其双亲的左孩子且其双亲有右孩子时）。若对后序线索二叉树从尾结点起沿前驱进行遍历，则遍历序列中尾结点是二叉树的根结点。若结点无左子树，则其