遍历非递归算法精选PPT.ppt

遍历非递归算法1第1页，此课件共116页哦2递归函数的主要优点是可以把算法写的比使用非递归函数时更清递归函数的主要优点是可以把算法写的比使用非递归函数时更清递归函数的主要优点是可以把算法写的比使用非递归函数时更清递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法。递归的另一个优点是，递归函数不会受到怀疑，宜用递归方法。递归的另一个优点是，递归函数不会受到怀疑，宜用递归方法。递归的另一个优点是，递归函数不会受到怀疑，宜用递归方法。递归的另一个优点是，递归函数不会受到怀疑，较非递归函数而言，某些人更相信递归函数。较非递归函数而言，某些人更相信递归函数。较非递归函数而言，某些人更相信递归函数。较非递归函数而言，某些人更相信递归函数。第2页，此课件共116页哦3以先序遍历为例：以先序遍历为例：void PreOrder(BiTree T)if(T)coutdata;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);A AB BC CD DE EF FHHGG第3页，此课件共116页哦4A AB BC CD DE EF FHHGGB BD DGGNULLNULLD DNULLNULLGGC CE EF FHHF FHHNULLNULLGGNULLNULLNULLNULLNULLNULLNULLNULLHHE ENULLNULLNULLNULL第4页，此课件共116页哦5遍历二叉树的非递归算法遍历二叉树的非递归算法需用到栈，顺序栈的定义如下：需用到栈，顺序栈的定义如下：#define size 100 typedef struct Type data size;int top；SqStack；第5页，此课件共116页哦61.先序非递归遍历：先序非递归遍历：(1)初始化一个堆栈初始化一个堆栈(2)把根结点入栈把根结点入栈(3)当堆栈非空时，循环当堆栈非空时，循环:A.出栈取一个结点指针，访问该结点出栈取一个结点指针，访问该结点;B.若该若该结点右子树非空，右子树指针入栈结点右子树非空，右子树指针入栈(4)左端到尽头后左端到尽头后,若该若该栈非空，右子树出栈栈非空，右子树出栈第6页，此课件共116页哦7先序遍历的非递归算法先序遍历的非递归算法StatusInorderTraverseStatusInorderTraverse(BiTreeT(BiTreeT)/采用二叉链表存储结构采用二叉链表存储结构.先序遍历二叉树先序遍历二叉树T的非递归算的非递归算法法。InitStack(S);p=T;while(p|!StackEmpty(S)while(p)/访问当前结点，右子进栈访问当前结点，右子进栈，遍历左子树遍历左子树遍历左子树遍历左子树coutdata;if(p-rchild!=null)Push(S，p-rchild);p=p-lchild;if(StackEmpty(S)=0)/根指针退栈，遍历右子树根指针退栈，遍历右子树Pop(S，p);第7页，此课件共116页哦8步骤步骤指针指针P P栈栈StackStack内容内容访问结点访问结点值值初态初态A A1 1B BC CA A2 2D DGGB B3 3 D D4 4GG5 5C CF FGG6 6E E C C7 7 F F E E8 8F F9 9 F FA AC CB BF FE ED DGwhile(p)while(p)/访问当前结点，右子进栈，访问当前结点，右子进栈，访问当前结点，右子进栈，访问当前结点，右子进栈，遍历左子树遍历左子树遍历左子树遍历左子树 coutdata;coutdata;if(p-rchild!=null)if(p-rchild!=null)Push(SPush(S，p-rchild);p-rchild);p=p-lchild;p=p-lchild;if(StackEmpty(S)=0)if(StackEmpty(S)=0)/根指针退栈，根指针退栈，根指针退栈，根指针退栈，遍历右子树遍历右子树遍历右子树遍历右子树Pop(SPop(S，p);p);第8页，此课件共116页哦92.2.中序非递归遍历：中序非递归遍历：中序非递归遍历：中序非递归遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树从栈中弹出，访问，再遍历右子树从栈中弹出，访问，再遍历右子树从栈中弹出，访问，再遍历右子树第9页，此课件共116页哦10voidInOrder(BiTreeT)voidInOrder(BiTreeT)/采用二叉链表存储结构。先序遍历二叉树采用二叉链表存储结构。先序遍历二叉树采用二叉链表存储结构。先序遍历二叉树采用二叉链表存储结构。先序遍历二叉树T T的非递归算法。的非递归算法。的非递归算法。的非递归算法。InitStack(S);InitStack(S);Push(SPush(S，T);T);/根指针进栈根指针进栈根指针进栈根指针进栈while(p|!StackEmpty(S)while(p|!StackEmpty(S)while(p!=NULL)while(p!=NULL)Push(SPush(S，p);p);/向左走到尽头向左走到尽头向左走到尽头向左走到尽头p=p-lchild;p=p-lchild;if(!StackEmpty(S)if(!StackEmpty(S)Pop(SPop(S，p);p);coutdata;coutdata;/访问结点访问结点访问结点访问结点p=p-rchild);p=p-rchild);/向右一步向右一步向右一步向右一步 中序遍历的非递归算法中序遍历的非递归算法1第10页，此课件共116页哦11步骤步骤指针指针P P栈栈StackStack内容内容访问结访问结点值点值初态初态A A1 1A ABABA2 2B BDBADBA3 3D D DBADBA4 4 DBADBA5 5D DGBAGBAD D6 6GG GBAGBA7 7 GBAGBA8 8GG BABAGG9 9 BABA1010B B A AB B1111 A A1212A AC CA A1313C CECEC1414E E ECECA AC CB BFE EDGGwhile(p!=NULL)while(p!=NULL)Push(SPush(S，p);p);/向左走到尽头向左走到尽头向左走到尽头向左走到尽头p=p-lchild;p=p-lchild;if(!StackEmpty(S)if(!StackEmpty(S)Pop(SPop(S，p);p);coutdata;coutdata;/访问结点访问结点访问结点访问结点p=p-rchild);p=p-rchild);/向右一步向右一步向右一步向右一步第11页，此课件共116页哦121515 ECEC1616E E C CE E1717 C C1818C CF FC C1919F F F F2020 F F2121F F F F2222 AC CB BFED DG第12页，此课件共116页哦13中序遍历的非递归算法中序遍历的非递归算法2(2(算法算法)自学自学StatusInorderTraverse(BiTreeT，Status(*visit(TElemTypeStatus(*visit(TElemTypee)e)/采用二叉链表存储结构，采用二叉链表存储结构，VisitVisit是对数据元素操作的应用函是对数据元素操作的应用函是对数据元素操作的应用函是对数据元素操作的应用函数。先序遍历二叉树数。先序遍历二叉树数。先序遍历二叉树数。先序遍历二叉树T T的非递归算法，对每个数据元素调用函的非递归算法，对每个数据元素调用函的非递归算法，对每个数据元素调用函的非递归算法，对每个数据元素调用函数数数数VisitVisit。InitStack(S);p=T;InitStack(S);p=T;while(p|!StackEmpty(S)while(p|!StackEmpty(S)if(p)/根指针进栈，遍历左子树根指针进栈，遍历左子树根指针进栈，遍历左子树根指针进栈，遍历左子树Push(SPush(S，p);p=p-lchild;p);p=p-lchild;elseelse/访问结点，根指针退栈，遍历右子树访问结点，根指针退栈，遍历右子树访问结点，根指针退栈，遍历右子树访问结点，根指针退栈，遍历右子树Pop(S，p);visit(p-data);p=p-rchild;p);visit(p-data);p=p-rchild;第13页，此课件共116页哦14步骤步骤指针指针P P栈栈StackStack内内容容访问结访问结点值点值初态初态A A1 1B BA A2 2D DBABA3 3 DBADBA4 4GGBABAD D5 5 GBAGBA6 6 BABAGG7 7 A AB B8 8C CA A9 9E EC C1010 ECEC1111 C CE E1212F F C C1313 F F1414 F FAC CB BF FED DGGif(p)/根指针进栈，遍历左子树根指针进栈，遍历左子树根指针进栈，遍历左子树根指针进栈，遍历左子树Push(SPush(S，p);p=p-p);p=p-lchild;lchild;elseelse/访问结点，根指针退栈，遍历访问结点，根指针退栈，遍历访问结点，根指针退栈，遍历访问结点，根指针退栈，遍历右子树右子树右子树右子树Pop(SPop(S，p);visit(p-p);visit(p-data);p=p-rchild;data);p=p-rchild;第14页，此课件共116页哦153.3.后序非递归遍历后序非递归遍历后序非递归遍历后序非递归遍历(自学自学自学自学)与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的过与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的过与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的过与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的过程中，对一个结点访问之前，要程中，对一个结点访问之前，要程中，对一个结点访问之前，要程中，对一个结点访问之前，要两次经历这个结点两次经历这个结点。第一次是由该结点找到其左孩子结点，遍历其左子树，遍历完第一次是由该结点找到其左孩子结点，遍历其左子树，遍历完第一次是由该结点找到其左孩子结点，遍历其左子树，遍历完第一次是由该结点找到其左孩子结点，遍历其左子树，遍历完左子树后，返回到这个结点。左子树后，返回到这个结点。左子树后，返回到这个结点。左子树后，返回到这个结点。第二次是由该结点找到其右孩子结点，遍历其右子树，遍历第二次是由该结点找到其右孩子结点，遍历其右子树，遍历完右子树后，再次返回到结点，这时才能访问该结点。完右子树后，再次返回到结点，这时才能访问该结点。因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，用来保存指向所经历结点的指针。用来保存指向所经历结点的指针。用来保存指向所经历结点的指针。用来保存指向所经历结点的指针。第15页，此课件共116页哦16从上面的分析可知，在后续遍历二叉树时，一个指针要进从上面的分析可知，在后续遍历二叉树时，一个指针要进出栈两次，第一次出栈的目的是由该指针找到其左孩子结出栈两次，第一次出栈的目的是由该指针找到其左孩子结点，对该结点并不做任何处理，因此出栈后需再次进栈，点，对该结点并不做任何处理，因此出栈后需再次进栈，只有在他第二次出栈后，才能访问该结点。只有在他第二次出栈后，才能访问该结点。为了区别同一个结点两次出栈，设置一个标志为了区别同一个结点两次出栈，设置一个标志为了区别同一个结点两次出栈，设置一个标志为了区别同一个结点两次出栈，设置一个标志flag，令：，令：11第一次出栈，结点不能访问第一次出栈，结点不能访问flag=22第二次出栈，结点可以访问第二次出栈，结点可以访问第16页，此课件共116页哦17PostOrder(BiTreet)SqStacksMAX;BiTreep;intsign;if(t=NULL)retrun;top=-1;p=t;while(!(p=NULL&top=-1)if(p!=NULL)s+top.link=p;stop.flag=1;p=p-lchild;第17页，此课件共116页哦18elsep=stop.link;sign=stop-.flag;if(sign=1)s+top.link=p;stop.flag=2;p=p-rchild;elseprintf(“%c”,p-data);p=NULL;第18页，此课件共116页哦19第19页，此课件共116页哦204.按层次遍历二叉树按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个实现方法为从上层到下层，每层中从左侧到右侧依次访问每个实现方法为从上层到下层，每层中从左侧到右侧依次访问每个实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。个结点的遍历序列。个结点的遍历序列。个结点的遍历序列。A ACBF FEDGG按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为：ABCDEFGH第20页，此课件共116页哦21二叉树用顺序存储结构表示时，按层遍历的算法实现：二叉树用顺序存储结构表示时，按层遍历的算法实现：二叉树用顺序存储结构表示时，按层遍历的算法实现：二叉树用顺序存储结构表示时，按层遍历的算法实现：A AC CBFE EDGGA AB BCD DEF FGG0 01 12 234 45 56 67 712 234 45 56 67 7AC CBF FDGGA ABC CD#F FG0 012 234 45 56 67 71 1234 46 675 5第21页，此课件共116页哦22voidLevelOreder(SqBiTreeBT)for(i=1;i=n;i+)if(BT.elemi!=#)coutBT.elemi);A AB BC CD DE EF FGGHHI IJ JKK第22页，此课件共116页哦23二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：如下：如下：如下：(1)(1)访问根结点，并将该结点记录下来；访问根结点，并将该结点记录下来；访问根结点，并将该结点记录下来；访问根结点，并将该结点记录下来；(2)(2)若记录的所有结点都已处理完毕，则结束遍历操作；否则重若记录的所有结点都已处理完毕，则结束遍历操作；否则重若记录的所有结点都已处理完毕，则结束遍历操作；否则重若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。复下列操作。复下列操作。复下列操作。(3)(3)取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。下来。下来。下来。在这个算法中，应使用一个在这个算法中，应使用一个队列队列队列队列结构完成这项操作。所谓记录结构完成这项操作。所谓记录结构完成这项操作。所谓记录结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。访问结点就是入队操作；而取出记录的结点就是出队操作。访问结点就是入队操作；而取出记录的结点就是出队操作。访问结点就是入队操作；而取出记录的结点就是出队操作。第23页，此课件共116页哦24这样一来，这样一来，这样一来，这样一来，算法就可以描述成下列形式：算法就可以描述成下列形式：算法就可以描述成下列形式：算法就可以描述成下列形式：(1)访问根结点，并将根结点入队；访问根结点，并将根结点入队；访问根结点，并将根结点入队；访问根结点，并将根结点入队；(2)当队列不空时，重复下列操作：当队列不空时，重复下列操作：当队列不空时，重复下列操作：当队列不空时，重复下列操作：a.a.从队列退出一个结点；从队列退出一个结点；b.b.若其有左孩子，则访问左孩子，并将其左孩子入队；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有左孩子，则访问左孩子，并将其左孩子入队；c.c.若其有右孩子，则访问右孩子，并将其右孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；第24页，此课件共116页哦25A AB BC CD DE EF FGGHHI IJ JKK初始化初始化初始化初始化A第一次第一次第一次第一次whilewhile循环循环循环循环B BC C第二次第二次第二次第二次whilewhile循环循环循环循环CD D E E第三次第三次第三次第三次whilewhile循环循环循环循环DE EF FGG第四次第四次第四次第四次while循环循环循环循环EF F GG第四次第四次第四次第四次whilewhile循环循环循环循环F FGGHH I I第25页，此课件共116页哦26voidLevelOrder(BiTreeT)voidLevelOrder(BiTreeT)if(T)exit(0);InitQueue(Q);p=T;InitQueue(Q);p=T;/初始化初始化初始化初始化coutdata;coutdata;EnQueue(QEnQueue(Q，p);p);/访问根结点，并将根结点入队访问根结点，并将根结点入队访问根结点，并将根结点入队访问根结点，并将根结点入队 while(!QueueEmpty(Q)while(!QueueEmpty(Q)/当队非空时重复执行下列操作当队非空时重复执行下列操作当队非空时重复执行下列操作当队非空时重复执行下列操作DeQueue(Q，p);/出队出队出队出队if(p-Lchild)/处理左孩子处理左孩子处理左孩子处理左孩子coutLchild;EnQueue(QcoutLchild;EnQueue(Q，p-Lchild);if(p-Rchild)/处理右孩子处理右孩子处理右孩子处理右孩子coutRchild;EnQueue(QcoutRchild;EnQueue(Q，p-Rchild);第26页，此课件共116页哦27总结：总结：总结：总结：遍历的第一个和最后一个结点遍历的第一个和最后一个结点遍历的第一个和最后一个结点遍历的第一个和最后一个结点第一个结点第一个结点第一个结点第一个结点：先序：根结点；先序：根结点；中序：中序：后序：后序：最后一个结点最后一个结点最后一个结点最后一个结点：先序：先序：中序：中序：后序：根结点。后序：根结点。沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；从根结点出发，沿着右链走，找到一个没有右孩从根结点出发，沿着右链走，找到一个没有右孩从根结点出发，沿着右链走，找到一个没有右孩从根结点出发，沿着右链走，找到一个没有右孩子的结点；子的结点；子的结点；子的结点；从根结点出发，沿着右链走，找到一个没有右孩从根结点出发，沿着右链走，找到一个没有右孩从根结点出发，沿着右链走，找到一个没有右孩从根结点出发，沿着右链走，找到一个没有右孩子的结点；子的结点；子的结点；子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；第27页，此课件共116页哦28求中序的第一个结点求中序的第一个结点求中序的第一个结点求中序的第一个结点从根结点出发，沿着左链走，找到一个没从根结点出发，沿着左链走，找到一个没有左孩子的结点；有左孩子的结点；的算法：的算法：的算法：的算法：求中序的第一个结点的算法：求中序的第一个结点的算法：P=T;while(P-lchild)P=P-lchild;coutdata;第28页，此课件共116页哦29求中序的最后一个结点的算法：求中序的最后一个结点的算法：求中序的最后一个结点的算法：求中序的最后一个结点的算法：从根结点出发，沿着右链走，找从根结点出发，沿着右链走，找从根结点出发，沿着右链走，找从根结点出发，沿着右链走，找到一个没有右孩子的结点；到一个没有右孩子的结点；到一个没有右孩子的结点；到一个没有右孩子的结点；求中序的最后一个结点的算法：求中序的最后一个结点的算法：P=T；while(P-rchild)P=P-rchild;coutdata;第29页，此课件共116页哦30一个程序员的生活一个程序员的生活第30页，此课件共116页哦31第31页，此课件共116页哦32利用二叉链表中的空指针域，存放指向结点在某种遍历次序下利用二叉链表中的空指针域，存放指向结点在某种遍历次序下利用二叉链表中的空指针域，存放指向结点在某种遍历次序下利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针的前趋和后继结点的指针的前趋和后继结点的指针的前趋和后继结点的指针(这种附加的指针称为这种附加的指针称为这种附加的指针称为这种附加的指针称为“线索线索线索线索(Thread)”)。这种加上了线索的二叉链表称为这种加上了线索的二叉链表称为这种加上了线索的二叉链表称为这种加上了线索的二叉链表称为线索链表线索链表，相应的二叉树称为，相应的二叉树称为，相应的二叉树称为，相应的二叉树称为线索二叉树线索二叉树(ThreadedBinaryTree)。不同的遍历有不同的线索树。不同的遍历有不同的线索树。不同的遍历有不同的线索树。不同的遍历有不同的线索树。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中根据线索性质的不同，线索二叉树可分为前序线索二叉树、中根据线索性质的不同，线索二叉树可分为前序线索二叉树、中根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。序线索二叉树和后序线索二叉树三种。序线索二叉树和后序线索二叉树三种。序线索二叉树和后序线索二叉树三种。6.4线索二叉树线索二叉树第32页，此课件共116页哦33AB BC CD DE EF FGGHHI INULLNULLNULL中序线索二叉树中序线索二叉树中序线索二叉树中序线索二叉树第33页，此课件共116页哦34结点的结构：结点的结构：左标志左标志ltag=ltag=右标志右标志右标志右标志rtag=0：lchild是指向结点的左孩子的指针是指向结点的左孩子的指针是指向结点的左孩子的指针是指向结点的左孩子的指针0 0：rchild是指向结点的右孩子的指针是指向结点的右孩子的指针是指向结点的右孩子的指针是指向结点的右孩子的指针1 1：lchildlchild是指向结点的前驱的左线索是指向结点的前驱的左线索是指向结点的前驱的左线索是指向结点的前驱的左线索1 1：rchild是指向结点的后继的右线索是指向结点的后继的右线索是指向结点的后继的右线索是指向结点的后继的右线索lchildlchildltagdatadatartagrchildrchild第34页，此课件共116页哦35若结点有左孩子，则若结点有左孩子，则若结点有左孩子，则若结点有左孩子，则lchildlchild指示其左孩子，否则指示其左孩子，否则指示其左孩子，否则指示其左孩子，否则lchild中存储该中存储该中存储该中存储该结点的前驱结点的指针；结点的前驱结点的指针；结点的前驱结点的指针；结点的前驱结点的指针；若结点有右孩子，则若结点有右孩子，则rchildrchild指示其右孩子，否则指示其右孩子，否则指示其右孩子，否则指示其右孩子，否则rchildrchild中存储指中存储指向该结点的后继结点的指针向该结点的后继结点的指针实质：对一个非线性结构进行线性化操作，使每个结点实质：对一个非线性结构进行线性化操作，使每个结点实质：对一个非线性结构进行线性化操作，使每个结点实质：对一个非线性结构进行线性化操作，使每个结点(除第除第除第除第一和最后一个外一和最后一个外一和最后一个外一和最后一个外)在这些线性序列中有且仅有一个直接前驱和直在这些线性序列中有且仅有一个直接前驱和直在这些线性序列中有且仅有一个直接前驱和直在这些线性序列中有且仅有一个直接前驱和直接后继。接后继。接后继。接后继。第35页，此课件共116页哦36DBEAFHGICDBEAFHGIC0 0A A 0 00 0B B0 00 0 C C11 1 E E 1 11 1 F F0 01 1D D 1 10 0 GG0 01 1I I11 1H 1NULLNULL中序线索链表中序线索链表中序线索链表中序线索链表ROOTROOT第36页，此课件共116页哦37注意：图中的实线表示指针，虚线表示线索。注意：图中的实线表示指针，虚线表示线索。结点结点D的左线索为空，表示的左线索为空，表示D是中序序列的开始结点，是中序序列的开始结点，无前趋；无前趋；结点结点C的右线索为空，表示的右线索为空，表示C是中序序列的终端结点，是中序序列的终端结点，无后继。无后继。线索二叉树中，一个结点是叶结点的线索二叉树中，一个结点是叶结点的充要条件充要条件为：为：左、右标志均是左、右标志均是1第37页，此课件共116页哦38A ABCD DE EF FGGHHI INULLNULLNULL中序线索二叉树中序线索二叉树提问：中序线索二叉树是物理结构还是逻辑结构？提问：中序线索二叉树是物理结构还是逻辑结构？提问：中序线索二叉树是物理结构还是逻辑结构？提问：中序线索二叉树是物理结构还是逻辑结构？第38页，此课件共116页哦39不带表头结点的不带表头结点的先序先序穿线穿线(线索线索)链表链表0 0A A01 1B B0 00 0E E1 11 1D D 1 11 1F F1NULLNULL第39页，此课件共116页哦40不带表头结点的不带表头结点的后序后序穿线穿线(线索线索)链表链表0 0 A A01 1B B00 0E E11 1D1 11F F1NULLNULL非空二叉链表非空二叉链表非空二叉链表非空二叉链表第40页，此课件共116页哦41带表头结点的带表头结点的中序中序穿线穿线(线索线索)链表链表0 A0 01B B0 00 0 E E1 11 D1 11 1F1 10 01 1ROOTROOT0 01 1ROOT(a)(a)空二叉链表空二叉链表空二叉链表空二叉链表(b)(b)非空二叉链表非空二叉链表非空二叉链表非空二叉链表第41页，此课件共116页哦42从遍历的第一个结点来看从遍历的第一个结点来看从遍历的第一个结点来看从遍历的第一个结点来看：先序序列中第一个结点必为根结点，中、后序序列中第一个结点先序序列中第一个结点必为根结点，中、后序序列中第一个结点先序序列中第一个结点必为根结点，中、后序序列中第一个结点先序序列中第一个结点必为根结点，中、后序序列中第一个结点的左孩子定为空的左孩子定为空的左孩子定为空的左孩子定为空从遍历的最后一个结点来看：从遍历的最后一个结点来看：先、中序序列中最后一个结点的右孩子必为空，后序序列中最后先、中序序列中最后一个结点的右孩子必为空，后序序列中最后先、中序序列中最后一个结点的右孩子必为空，后序序列中最后先、中序序列中最后一个结点的右孩子必为空，后序序列中最后一个结点一定为根结点一个结点一定为根结点一个结点一定为根结点一个结点一定为根结点线索二叉树的作用：线索二叉树的作用：对于遍历操作，线索树优于非线索树；遍历线索树不用设栈对于遍历操作，线索树优于非线索树；遍历线索树不用设栈对于遍历操作，线索树优于非线索树；遍历线索树不用设栈对于遍历操作，线索树优于非线索树；遍历线索树不用设栈步骤：步骤：步骤：步骤：1)找遍历的第一个结点找遍历的第一个结点找遍历的第一个结点找遍历的第一个结点2)2)不断地找遍历到的结点的后继结点，直到树中各结点都遍不断地找遍历到的结点的后继结点，直到树中各结点都遍不断地找遍历到的结点的后继结点，直到树中各结点都遍不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束。历到为止，结束。历到为止，结束。历到为止，结束。遍历线索二叉树遍历线索二叉树第42页，此课件共116页哦43遍历中序线索二叉树遍历中序线索二叉树(带头结点带头结点)P134算法算法6.5StatusInorderTraverse_Thr(BiThrTreeTStatusInorderTraverse_Thr(BiThrTreeT，Status(*Visit)(TElemTypee)Status(*Visit)(TElemTypee)/T/T指向头结点，头结点的左链指向头结点，头结点的左链指向头结点，头结点的左链指向头结点，头结点的左链lchildlchild指向根结点，可参见线索化指向根结点，可参见线索化指向根结点，可参见线索化指向根结点，可参见线索化算法，中序遍历二叉线索树算法，中序遍历二叉线索树算法，中序遍历二叉线索树算法，中序遍历二叉线索树T T的非递归算法的非递归算法的非递归算法的非递归算法p=T-lchild;/p指向根结点指向根结点指向根结点指向根结点while(p!=T)while(p!=T)/空树或遍历结束时，空树或遍历结束时，空树或遍历结束时，空树或遍历结束时，p=Twhile(p-LTag=Link)p=p-lchild;if(!visit(p-data)returnERRORif(!visit(p-data)returnERROR；/访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点while(p-rchild!=T&p-RTag=Thread)p=p-rchild;Visit(p-data)p=p-rchild;Visit(p-data)/访问后继结点访问后继结点访问后继结点访问后继结点p=p-rchild;p=p-rchild;returnOK;returnOK;/InOrderTraverse_Thr/InOrderTraverse_Thr第43页，此课件共116页哦44B BDECFHI IKGJ JLA A(1)(1)while(p-LTag=Link)p=p-lchild;(2)(2)if(!visit(p-data)returnERRORif(!visit(p-data)returnERROR；/访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点(3)(3)while(p-rchild!=T&p-RTag=Thread)while(p-rchild!=T&p-RTag=Thread)/访问后继结点访问后继结点访问后继结点访问后继结点 p=p-rchild;Visit(p-data);p=p-rchild;Visit(p-data);(4)(4)p=p-rchild;p=p-rchild;NULLNULLNULLNULLp pp1p1p2p3p3p4p4p5p5p6p6p7p8p8p9p9p10p10p11p11p12p12p13p13p14p15第44页，此课件共116页哦45B BDE EC CFHIKKGGJL LA(1)(1)while(p-LTag=Link)p=p-lchild;while(p-LTag=Link)p=p-lchild;(2)(2)if(!visit(p-data)returnERRORif(!visit(p-data)returnERROR；/访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点(3)(3)while(p-rchild!=T&p-RTag=Thread)while(p-rchild!=T&p-RTag=Thread)/访问后继结点访问后继结点访问后继结点访问后继结点 p=p-rchild;Visit(p-data);p=p-rchild;Visit(p-data);(4)(4)p=p-rchild;p=p-rchild;NULLNULLNULLNULLP P怎样移动怎样移动怎样移动怎样移动p p第45页，此课件共116页哦46if(currentRTag=Thread)后继为后继为 currentrchildelse /currentRTag=Link 后继为中序遍历其右子树后继为中序遍历其右子树时访问的第一个结点时访问的第一个结点(即其右子即其右子树最左下的结点树最左下的结点)寻找当前结点寻找当前结点*current在在中序中序下下的后继的后继ABDECFHIKGJL中序后继线索二叉树中序后继线索二叉树中序后继线索二叉树中序后继线索二叉树DBGJEACHLKFIDBGJEACHLKFI第46页，此课件共116页哦47if(currentLTag=Thread)前驱为前驱为currentlchildelse/currentLTag=Link前驱为中序遍历其左子树时最后前驱为中序遍历其左子树时最后访问的一个结点访问的一个结点(即其左子树最右即其左子树最右下的结点下的结点)寻找当前结点寻找当前结点在在中序中序下的前驱下的前驱ABDECFHIKGJL中序前驱线索二叉树中序前驱线索二叉树中序序列：中序序列：DBGJEACHLKFI第47页，此课件共116页哦48if(currentRTag=Thread)后继为后继为currentrchildelse/currentRTag=Link后继为其左孩子，若无左孩后继为其左孩子，若无左孩子，则后继为其右孩子子，则后继为其右孩子寻找当前结点寻找当前结点*current在在先序先序下的后继下的后继先序线索二叉树先序线索二叉树先序序列先序序列ABDEGJCFHKLIABDECFHIKGJL第48页，此课件共116页哦49if(currentif(currentLTag=Thread)LTag=Thread)前驱为前驱为前驱为前驱为currentcurrentlchildlchildelseelse/currentcurrentLTag=Link 前驱为：前驱为：若为根结点，则无前驱；若为根结点，则无前驱；若为根结点，则无前驱；若为根结点，则无前驱；若结点无左兄弟，则其前驱为若结点无左兄弟，则其前驱为若结点无左兄弟，则其前驱为若结点无左兄弟，则其前驱为其父结点其父结点其父结点其父结点 若结点有左兄弟。则其前驱为若结点有左兄弟。则其前驱为若结点有左兄弟。则其前驱为若结点有左兄弟。则其前驱为先序遍历其左兄弟子树时访问先序遍历其左兄弟子树时访问先序遍历其左兄弟子树