电子科大820数据结构考纲考点归纳

1、ch1. 数据结构及算法的相关概念和术语（1） 数据结构及算法的概念；数据：所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：数据的基本单位，一个数据项可由若干个数据项组成。数据项：构成数据元素的不可分割的最小单位。* 关系：数据数据元素数据项数据对象：性质相同的数据元素的集合。数据类型：原子类型、结构类型、抽象数据类型。数据结构：相互之间存在一种或多种特定关系的数据元素的集合。（2）数据的逻辑结构和存储结构；数据结构三要素： 数据的逻辑结构、数据的存储结构、数据的运算数据的逻辑结构：线性结构（线性表）、非线性结构（集合、树和图）。数据的存储结构：顺序存储：优点：可以随机存取，每个

2、元素占用最少存储空间缺点：可能产生较多碎片现象链式存储：优点：不会出现碎片现象缺点：每个元素占用较多存储空间，只能实现顺序存储索引存储：优点：检索速度快缺点：增加了附加的索引表，会占用较多存储空间散列存储：优点：检索、增加和删除结点的操作都很快缺点：可能出现存储单元的冲突，解决冲突会增加时间和空间的开销（3）算法的定义及特性；算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的特性：有穷性、确定性、可行性、输入、输出算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求* 同一个算法，实现语言的级别越高，执行效率就越低（4）算法时间复杂度和空间复

3、杂度的分析方法。时间复杂度：主要分析语句频度（一条语句在算法中被重复执行的次数）之和t(n)的数量级加法原则：t(n)=t1(n)+t2(n)=o(max(f(n),g(n)乘法原则：t(n)=t1(n)t2(n)=o(f(n)g(n)* 常见时间复杂度比较：o(1)o(n)o(nlogn)o(n2)o(n3)o(2n)o(n!)o(nn)空间复杂度：算法所耗费的存储空间，s(n)=o(g(n)算法原地工作是指算法所需辅助空间是常量，即o(1)ch2线性表（1）线性表的定义线性表：具有相同数据类型的n(n0)个数据元素的有限序列，一般表示如下：l=(a1, a2, , ai+1, , an)其

4、中，a1是唯一的“第一个”数据元素，称为表头元素；an是唯一的“最后一个”数据元素，称为表尾元素；除第一个元素外，每个元素有且仅有一个直接前趋；除最后一个元素外，每个元素有且仅有一个直接后继。线性表的特点：表中元素具有逻辑上的顺序性，表中元素都是数据元素，表中元素的数据类型都相同，表中元素具有抽象性。（2）线性表的基本操作及在顺序存储及链式存储上的实现；线性表的基本操作：initlist(&l) 构造一个空的线性表listlength(l) 求表长，即求线性表中数据结点（如果是带头结点单链表，则不含头结点）的个数locateelem(l, e) 按值查找getelem(l, i) 按位查找li

5、stinsert(&l, i, e) 在表l中的第i个位置插入指定元素listdelete(&l, i, &e) 删除表l中的第i个位置的元素，并输出其值printlist(l) 按前后顺序输出线性表l的所有元素值listempty(l) 判空，若l为空表，返回true，否则返回falsedestroylist(&l) 销毁线性表，并释放表l占用的内存空间clearlist(&l) 将l重置为空表priorelem(l,cur_e,&pre_e) 若cur_e是表l的数据元素，且不是第一个，用pre_e返回其前驱nextelem(l,cur_e,&next_e) 若cur_e是表l的元素，且不

6、是最后一个，用next_e返回其后继listtraverse(l,visit() 表的遍历，即依次对l的每个元素调用函数visit()线性表的顺序存储（顺序表）：线性表中第i+1个数据元素的存储位置loc(ai+1)和第i个数据元素的存储位置loc(ai)之间关系：loc(ai+1)= loc(ai)+l线性表的第i个数据元素ai的存储位置：loc(ai)= loc(a1)+(i-1)l顺序表的特点：可以进行随机存取，即通过首地址和元素序号可以在o(1)的时间内找到指定元素，但插入和删除元素操作需要移动大量元素顺序表结构的定义：顺序表的静态分配：#define maxsize 50typede

7、f structelemtype datamaxsize;int length;sqlist;顺序表的动态分配：#define initsize 50typedef structelemtype *data;int listsize,length;sqlist;* 动态分配语句：l.data=(elemtype *)malloc(sizeof(elemtype)*initsize);顺序表基本操作的实现：初始化操作：构造一个空的顺序表lbool initlist_sq(sqlist &l)l.data=(elemtype *)malloc(initsize*sizeof(elemtype);i

8、f(!l.data) exit(overflow);l.length=0;l.listsize=initsize;return true;/initlist_sq插入操作：在第i(1in)个元素之前插入一个元素，需将第n至第i(共n-i+1)个元素向后移动一个位置。bool listinsert_sq(sqlist &l,int i,elemtype e)/在顺序表l中的第i个位置插入新元素e/i的合法值为1il.length+1if(il.length+1) return false; /i值不合法if(l.length=listsize) /当前存储空间已满，不能插入return fals

9、e;for(i=l.length;j=i;j-) /将第i个位置及之后元素后移l.dataj=l.dataj-1;l.datai-1=e;/在位置i处放入el.length+;/表长加1return true;/listinsert_sq时间复杂度：最好情况：在表尾插入，无须移动元素，t(n)=o(1)最坏情况：在表头插入，需要移动第一个元素后面所有元素，t(n)=o(n)平均情况：t(n)=n/2=o(n)删除操作：在顺序表l中删除第i(1in)个元素，需将第n至第i(共n-i+1)个元素向前移动一个位置。bool listdelete_sq(sqlist &l,int i,elemtype

10、 e)/在顺序表l中删除第i个元素，并用e返回其值/i的合法值为1il.lengthif(il.length) return false; /i值不合法e=l.datai-1;for(int j=i;jl.length;j+)l.dataj-1=l.dataj;l.length-;return true;/listdelete_sq时间复杂度t(n)：最好情况：删除表尾元素，无须移动元素，t(n)=o(1)最坏情况：删除表头元素，需要移动第一个元素后面所有元素，t(n)=o(n)平均情况：t(n)=(n-1)/2=o(n)按值查找（顺序查找）:int locateelem(sqlist l,i

11、nt i,elamtype e)/查找顺序表中值为e的元素，若查找成功，返回元素位序，否则返回0for(int i=0;il.length;i+)if(l.datai=e) return i+1; /下标为i的元素值等于e，返回其位号i+1return 0;/locateelem顺序表的归并：t(n)=o(la.length+lb.length)void mergelist_sq(sqlist la, sqlist lb, sqlist &lc)/已知顺序表la和lb的元素按值非递减排列/归并la和lb得到新的顺序表lc，lc的元素也按值非递减排列pa=la.data;pb=lb.data;l

12、c.listsize=lc.length=la.length+lb.length;pc=lc.data=(elemtype *)malloc(lc.listsize*sizeof(elemtype);if(!lc.data) exit(overflow);pa_last=la.data+la.length-1;pb_last=lb.data+lb.length-1;while(pa=pa_last&pb=pb_last) /开始归并if(*pa=*pb) *pc+=*pa+;else *pc+=*pb+;while(pa=pa_last) *pc+=*pa+;while(pbnext=null

13、; /初始为空表for(i=n;i0;i-)p=(linklist)malloc(sizeof(lnode); /创建新结点scanf(&p-data);p-next=l-next;l-next=p;/将新结点插入表中/createlist1_l单链表的建立2（尾插法）：时间复杂度o(n)void createlist2_l(linklist &l,int n)/从表头到表尾正向输入n个元素的值，建立带头结点的单链表l/每次均在表尾插入元素l=(linklist)malloc(sizeof(lnode); /创建头结点l-next=null; /初始为空表q=l; /表尾指针for(i=n;i

14、0;i-)p=(linklist)malloc(sizeof(lnode); /创建新结点scanf(&p-data);r-next=p;r=p;/将新结点插入表中r-next=null;/表尾指针置空/createlist2_l单链表的查找1（按位置查找）：lnode* getelem_l(linklist l,int i)/l为带头结点的单链表的头指针/当第i个元素存在时，返回第i个结点的指针，否则返回nullint j=1;/计数，初始为1p=l-next;/初始化，p指向每一个结点while(p&jnext;j+;if(!p|ji) return null; /若i大于表长，p=nul

15、l直接返回nullreturn p;/返回第i个结点的指针/getelem_l单链表的查找2（按值查找）：lnode* locateelem_l(linklist l,elemtype e)/l为带头结点的单链表的头指针/当值查找成功时返回数据域值等于e的结点指针，否则返回nullint i=0;p=l-next;while(p&p-data!=e) /顺时针向后查找，直到p指向值为e的元素或p为空p=p-next;return p;/找到后返回该结点指针，否则返回null/locateelem_l插入操作(前插)：先找到前驱结点*p，然后完成在*p后插入*s，时间复杂度t(n)=o(n)bo

16、ol listinsert_l(linklist &l,int i,elemtype e)/在带头结点的单链表l中第i个位置插入元素ep=getelem_l(l,i-1);/查找插入位置的前趋结点if(!p) return false;/插入位置不合法s=(linklist)malloc(sizeof(lnode);/生成新结点s-data=e;/插入l中s-next=p-next;p-next=s;return true;/listinsert_l插入操作（后插）：设p指向单链表中某结点，s指向待插入值为e的新结点，将*s插入到*p之后。时 间复杂度t(n)=o(1)/只给出关键代码段s-n

17、ext=p-next;/修改指针域，顺序不能颠倒p-next=s;e=p-data;/交换数据域部分p-data=s-data;s-data=e删除操作1：先找到被删结点的前趋，然后完成在*p后删除被删结点，时间复杂度t(n)=o(n)bool listdelete_l(linklist &l,int i,elemtype &e)/在带头结点的单链表l中，删除第i个元素，并由e返回其值p=getelem_l(l,i-1); /查找第i个结点，并令p指向其前趋if(!p) return false;/删除位置不合法q=p-next;/令q指向被删除结点p-next=q-next;/将*q结点从链

18、中断开e=q-data;/取其数据域的值free(q);/释放结点的存储空间return true;/listdelete_l删除操作2：将结点*p后继结点的值赋予其自身，然后删除后继结点，时间复杂度t(n)=o(1)/只给出关键代码段q=p-next;/修改指针域，顺序不能颠倒p-data=p-next-data; /和后继结点交换数据域e=p-data;p-next=q-next; /将*q结点从链中断开free(q);/释放结点的存储空间单链表的归并：void mergelist_l(linklist la, linklist lb, linklist &lc)/已知单链表la和lb的元

19、素按值非递减排列/归并la和lb得到新的单链表lc，lc的元素也按值非递减排列pa=la-next;pb=lb-next;lc=pc=la;/用la的头结点作为lc的头结点while(pa&pb)/开始归并if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;/插入剩余段free(lb); /释放lb头结点/mergelist_l（3）各种变形链表（循环链表、双向链表、带头结点的链表等）的表示和基本操作的实现；循环链表：循环单链表：表尾结点的next域指向l，表中没

20、有指针域为null的结点，因此循环单链表的判空条件是看它的头结点的指针域是否等于头指针；循环单链表在任何一个位置上插入和删除操作都是等价的，无需判断是否表尾；循环单链表可以从表中任一结点开始遍历整个链表。循环单链表不设头指针而只设尾指针，可使一些操作效率更高。循环双链表：与循环单链表不同的是，循环双链表中头结点的prior指针还指向表尾结点；在循环双链表l中，某结点*p为尾结点时，p-next=l；当循环双链表为空时，对其头结点*p，有p-prior=p-next=l。双向链表：其结点有两个指针域，一个指向直接后继，另一个指向直接前趋，双向链表的插入、删除结点算法的时间复杂度为o(1)。双向链

21、表结构的定义：typedef struct dulnodeelemtype data;struct lnode *prior,*next;dulnode, *dulinklist;双向链表的插入操作：/只给出关键代码段/在结点*p之后插入值为e的新结点*ss-data=e;s-next=p-next;p-next-prior=s;/语句执行顺序不唯一，但这两步必须在最后一步之前s-prior=p;p-next=s;/在结点*p之前插入值为e的新结点*ss-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;双向链表的删除操作：/只给

22、出关键代码段/删除结点*p的后继结点*q，并用e返回其值e=q-data;p-next=q-next;q-next-prior=p;free(q);/删除结点*q的前趋*p，并用e返回其值e=p-data;q-prior=p-prior;p-prior-next=q;free(p);带头结点的链表：带头结点的链表结构定义：typedef struct lnode/结点类型elemtype data;struct lnode *next;*link,*position;typedef struct/链表类型link head,tail;/分别指向链表的头结点和尾结点int length;/线性表

23、中元素的个数linklist;ch3栈与队列（1）栈和队列的基本概念；栈和队列的顺序存储结构、链式储存结构及其存储特点；栈：限定在表尾进行插入或删除操作（头进尾出）的线性表，表尾称为栈顶（top），表头称为栈底（bottom），不含任何元素的栈称为空栈，栈又被称为后进先出（lifo）线性表。队列：只允许在表的一端进行插入，另一端进行删除操作（尾进头出），允许插入的一端叫做队尾（rear）， 允许删除的一端叫做队头（front），是一种先进先出（fifo）的线性表。栈的基本操作：initstack(&s) 初始化，构造一个空栈sstackempty(s) 栈s判空stacklength(s) 求

24、栈长，即栈s的元素个数push(&s,x) 入栈，插入元素为x的新栈顶元素pop(&s,x) 出栈，删除栈s的栈顶元素，并用x返回其值gettop(s,&x) 取栈顶，用x返回栈s的栈顶元素clearstack(&s) 将栈s清空destroystack(&s) 销毁栈，并释放其存储空间栈的顺序存储（顺序栈）：可能发生上溢基本操作：/只给出关键语句initstack(&s) /栈满条件s.top-s.base=s.stacksizes.top=s.base;s.stacksize=initsize; /栈空条件s.top=s.basegettop(s, &e)e=*(s.top-1);push

25、(&s,e)*s.top+=e;/入栈时栈顶指针先加1，再送值到栈顶元素pop(&s,&e)e=*-s.top;/出栈时先取栈顶元素值，再将栈顶指针减1栈的链式存储（链栈）：便于多个栈共享存储空间和提高其效率，不存在栈满上溢的情况，规定链栈没有头结点，lhead指向栈顶元素。基本操作：/只给出关键语句initstack(&s)/初始化p-next=s-next;s-next=p;push(&s,e)/入栈p-data=e;s-next=p;p-next=s-next;pop(&s,&e)/出栈p=s-next;e=p-data; s-next=p-next;free(p);destroysta

26、ck（&s）/销毁栈p=s;s=s-next;free(p);队列的链式存储（链队列）：基本操作：/只给出关键语句initqueue(&q)/初始化q.front=q.rear=(queueptr)malloc(sizeof(qnode);q.front-next=null;destroyqueue(&q)/销毁队列q.rear=q.front-next;free(q.front);q.front=q.rear;enqueue(&q,e)/入队p-data=e;p-next=null;q.rear-next=p;q.rear=p;dequeue（&q,&e）/出队p=q.front-next;

27、e=p-data;q.front-next=p-next;if(q.rear=p)q.rear=q.front;free(p);队列的顺序存储（循环队列）：约定初始化建空队列时，令front=rear=0，每当插入新的元素时，尾指针增1，当删除队列元素时，头指针增1，因此在非空队列中，头指针始终指向头元素，尾指针始终指向队列尾元素的下一个位置* 如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度，若用户无法预估所用队列的最大长度，宜采用链队列（2）循环队列的判满、判空方法；方法一：另设一个标志位以区别队列是空还是满方法二：牺牲一个单元来区分队空和队满，入队时少用一个队列单元，约定

28、以队头指针在队尾指针的下一位置作为队满的标志队满条件：(q.rear+1)%maxsize=q.front队空条件：q.rear=q.front队列中元素个数：（q.rear-q.front+maxsize）%maxsize（3）栈和队列的应用栈的应用：数制转换、括号匹配、表达式求值、迷宫求解、实现递归队列的应用：层次遍历、解决主机与外部设备之间速度不匹配的问题，解决由多用户引起的资源竞争问题（4）递归过程的特点及实现方法；递归的两个必要条件：1) 递归表达式（递归体）2) 边界条件（递归出口）* 递归的精髓在于能否将原始问题转的为属性相同但规模较小的问题（5）特殊矩阵的压缩储存； 数组的存储

29、结构：行优先：loc(i,j)=loc(0,0)+(b2i+j)l列优先：loc(i,j)=loc(0,0)+(b2j+i)l 特殊矩阵的压缩存储：对称矩阵：将n2个元素压缩存储到n(n+1)/2个元素的空间中，可以行序为主序存储基下三角（含对角线）中的元素，以一维数组san(n+1)/2作为n价对称矩阵a的存储结构，则sak和矩阵元aij之间存在着一一对应关系：k= i(i-1)2+j-1, &ij (下三角区和主对角线元素)j(j-1)2+i-1, &i1时，其余结点可分为m(m0)个互不相交的有限集t1，t2，tm，其中每一个集合本身又是一棵树，并称为根的子树。树是一种递归的数据结构，树

30、作为一种逻辑结构，同时也是一种分层结构。树的特点：1) 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点2) 树中所有结点可以有零个或多个后继结点树的一些基本术语：结点的度：树中一个结点的子结点数树的度：树中结点的最大度数分支结点：度大于0的结点（非终端结点）叶子结点：度为0的结点（终端结点）结点的层次：从根开始定义起，根为第一层，根的孩子为第二层，若某结点在第l层，则其子树的根就在第l+1层树的深度（高度）：树中结点的最大层次森林：m(m0)棵互不相交的树的集合，对树中的每个结点而言，基子树的集合即为森林* 注：由于树中的分支是有向的，所以树中的路径是从上到下的，同一双亲结

31、点的两个孩子结点之间不存在路径树的性质：1) 树中结点数=所有结点的度数(树中的边数)+12) 度为m的树中第i层上至多有mi-1个结点(i1)3) 高度为h的m叉树至多有(mh-1)/(m-1)个结点4) 具有n个结点的m叉树的最小高度为（表示不小于x的最小整数）（2）二叉树的定义及6大性质二叉树的定义：二叉树是别一种树型结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒二叉树的性质：性质1：在二叉树的第i层上至多有2i-1个结点(i1)性质2：深度为k的二叉树至多有2k-1个结点(k1)满二叉树：一棵深度为k且有2k-1

32、个结点的二叉树称为满二叉树完全二叉树：深度为k的有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树，其特点是：(1) 叶子结点只可能在层次最大的两层出现；(2) 对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1性质3：对任何一棵二叉树t，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1，设b为分支数，n为结点总数，则有n=n1+2n2+1=b+1性质4：具有n个结点的完全二叉树的深度为log2n+1（x表示不大于x的最大整数）性质5：如果对一棵有n个结点的完全二叉树的结点按编号（从

33、第1层到第log2n+1层，每层从左到右），则对任一结点i(1in)，有：1) 如果i=1则结点i是二叉树的根，无双亲；如果i1，则其双亲parent(i)是结点i/2（x表示不大于x的最大整数），即当i为偶数时，其双亲为结点i/2；当i为奇数时，其双亲为结点(i-1)/22) 如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子lchild(i)是结点2i3) 如果2i+1n，则结点i无右孩子；否则其右孩子rchild(i)是结点2i+1性质6： 给定n个节点，能构成h(n)种不同的二叉树。（严版教材未给出，科大考纲涉及）*注：h(n)为卡特兰数的第n项。计算方法为：hn=c2nn

34、n+1（3）二叉树的顺序储存与链式储存结构顺序存储：约定用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中，以0表示不存在的结点，这种顺序存储结构仅适用于完全二叉树。结构定义：#define maxsize 100/二叉树最大结点数typedef telemtype sqbitreemaxsize;/0号单元存储根结点sqbitree bt;* 最坏情况：一个深度为k且只有k个结点的单支树，需要长度为2k-1的一维数组链式存储：二叉链表结点包含3个域，数据域和左、右指针域（三叉链表还增加了指向其双亲结

35、点的parent指针域），链表的头指针指向二叉树的根结点，易证在含有n个结点的二叉链表中有n+1个空链域。结构定义：typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;bitnode,*bitree;（4）二叉树的先序、中序、后序三种遍历方式的关系以及实现；层序遍历的实现先序遍历：根左右若二叉树非空，则先访问根结点，然后先序遍历左子树，最后先序遍历右子树（递归过程）/算法实现：先序遍历的递归算法bool preordertraverse(bitree t,bool(*visit)(telemtype e)if(

36、t)if(visit(t-data)if(preordertraverse(t-lchild,visit)if(preordertraverse(t-rchild,visit) return true;return false;else return true;/preordertraverse/先序建立二叉树：按先序依次输入二叉树中结点的值，空格表示空树bool createbitree(bitree &t)scanf(&ch);if(ch= ) t=null;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) return false;t-data=c

37、h;createbitree(t-lchild);createbitree(t-rchild);return true;/createbitree中序遍历：左根右若二叉树非空，则先中序遍历左子树，然后访问根结点，最后中序遍历右子树（递归过程）/算法实现：中序遍历的非递归算法（栈实现）bool inordertraverse1(bitree t,bool(*visit)(telemtype e)initstack(s);push(s,t); /根指针进栈while(!stackempty(s)while(gettop(s,p)&p)push(s,p-lchild);/向左走到尽头pop(s,p)

38、;/空指针退栈if(!stackempty(s)/访问结点，向右一步pop(s,p);if(!visit(p-data) return false;push(s,p-rchild);/inordertraverse1return true;/inordertraverse/第2种非递归算法bool inordertraverse2(bitree t,bool(*visit)(telemtype e)initstack(s);p=t;while(p|!stackempty(s)if(p)push(s,p);p=p-lchild;elsepop(s,p);if(!visit(p-data) ret

39、urn false;p=p-rchild;return true;/inodertraverse2后序遍历：左右根若二叉树非空，则先后序遍历左子树，然后后序遍历右子树，最后访问根结点（递归过程）/算法实现：后序遍历的递归算法bool postordertraverse(bitree t,bool(*visit)(telemtype e)if(t)if(postordertraverse(t-lchild,visit)if(postordertraverse(t-rchild,visit)if(visit(t-data) return true;return false;else return

40、true;/postordertraverse层次遍历：从上到下、从左到右按层次遍历二叉树/算法描述（队列实现）void levelordertraverse(bitree t,bool(*visit)(telemtype e)initqueue(q);p=t;visit(p-data);/ 访问根节点enqueue(q,p);/根结点入队while(p|!queueempty(q)dequeue(q,p);/队头元素出队visit(p-data);/访问当前节点if(p-lchild)enqueue(q,p-lchild);/若存在左孩子，左孩子进队列if(p-rchild)enqueue(

41、q,p-rchild);/若存在右孩子，右孩子进队列/levelordertraverse由遍历序列构造二叉树：1) 先序遍历中，第一个结点一定是二叉树的根结点2) 中序遍历中，根结点必然将中序序列分割成两个子序列3) 后序序列的最后一个结点一定是二叉树的根结点4) 由二叉树的遍历能否唯一地确定一棵二叉树先序中序后序层序先序中序后序层序（5）线索二叉树的基本概念与构造方法线索二叉树：引入线索二叉树的是为了加快查找结点前驱和后继的速度规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继

42、。结点增加两个标志域ltag和rtag，结点结构变为：lchildltagdatartagrchild其中：ltag= 0 lchild域指示结点的左孩子1 lchild域指示结点的前驱 rtag= 0 lchild域指示结点的右孩子1 lchild域指示结点的后继结构定义：线索链表/指向结点前驱和后继的指针叫做线索，加上线索的二叉树称为线索二叉树/对typedef enum pointertaglink,thread;typedef struct bithrnodetelemtype data;struct bithrnode *lchild,*rchild;pointertag ltag,

43、rtag;bithrnode,*bithrtree;线索二叉树的构造：线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有遍历时才能得到，因此，线索化的过程即为在遍历的过程中修改空指针的过程。中序建立中序线索化链表：bool inorderthreading1(bitree &thrt,bithrtree t)/构造算法1/附设一个指针pre始终指向刚刚访问过的结点/若指针p指向当前访问的结点，则pre指向它的前驱if(!(thrt=(bithrtree)malloc(sizeof(bithrnode)return false;thrt-ltag=link;thr

44、t-rtag=thread;thrt-rchild=thrt;if(!t) thrt-lchild=thrt;elsethrt-lchild=t;pre=thrt;inthreading(t);pre-lchild=thrt;pre-rtag=thread;thrt-rchild=pre;return true;/inorderthreading1void inthreading(bithrtree p)/构造算法2if(p)inthreading(p-lchild);if(!p-lchild)p-ltag=thread;p-lchild=pre;if(!pre-rchild)pre-rtag

45、=thread;pre-rchid=p;pre=p;inthreading(p-rchild);/inthreading* 中序线索树中结点前驱的后继的确定：根据中序遍历的规律，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点；在中序线索树中查找结点前驱的规律为：若ltag=1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（即左子树中最右下的结点）为其前驱。* 后序线索树中结点前驱的后继的确定：三种情况1) 若结点x是二叉树的根，则其后继为空2) 若结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继结点即为双亲结点3) 若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点