遍历非递归算法精选文档.ppt

《遍历非递归算法精选文档.ppt》由会员分享，可在线阅读，更多相关《遍历非递归算法精选文档.ppt（116页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遍历非递归算法1本讲稿第一页，共一百一十六页2递归函数的主要优点是可以把算法写的比使用非递归函数时更递归函数的主要优点是可以把算法写的比使用非递归函数时更递归函数的主要优点是可以把算法写的比使用非递归函数时更递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁，而且某些问题，特别是与人工智能有关的问题，清晰更简洁，而且某些问题，特别是与人工智能有关的问题，清晰更简洁，而且某些问题，特别是与人工智能有关的问题，清晰更简洁，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法。递归的另一个优点是，递归函数不会受到更适宜用递归方法。递归的另一个优点是，递归函数不会受到更适宜用递归方

2、法。递归的另一个优点是，递归函数不会受到更适宜用递归方法。递归的另一个优点是，递归函数不会受到怀疑，较非递归函数而言，某些人更相信递归函数。怀疑，较非递归函数而言，某些人更相信递归函数。怀疑，较非递归函数而言，某些人更相信递归函数。怀疑，较非递归函数而言，某些人更相信递归函数。本讲稿第二页，共一百一十六页3以先序遍历为例：以先序遍历为例：void PreOrder(BiTree T)if(T)coutdata;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);A AB BC CD DE EF FHHGG本讲稿第三页，共一百一十六页4A

3、AB BC CD DE EF FHHGGB BD DGGNULLNULLD DNULLNULLGGC CE EF FHHF FHHNULLNULLGGNULLNULLNULLNULLNULLNULLNULLNULLHHE ENULLNULLNULLNULL本讲稿第四页，共一百一十六页5遍历二叉树的非递归算法遍历二叉树的非递归算法需用到栈，顺序栈的定义如下：需用到栈，顺序栈的定义如下：#define size 100 typedef struct Type data size;int top；SqStack；本讲稿第五页，共一百一十六页61.先序非递归遍历：先序非递归遍历：(1)初始化一个堆栈初

4、始化一个堆栈(2)把根结点入栈把根结点入栈(3)当堆栈非空时，循环当堆栈非空时，循环:A.出栈取一个结点指针，访问该结点出栈取一个结点指针，访问该结点;B.若该若该结点右子树非空，右子树指针入栈结点右子树非空，右子树指针入栈(4)左端到尽头后左端到尽头后,若该若该栈非空，右子树出栈栈非空，右子树出栈本讲稿第六页，共一百一十六页7先序遍历的非递归算法先序遍历的非递归算法StatusInorderTraverseStatusInorderTraverse(BiTreeT(BiTreeT)/采用二叉链表存储结构采用二叉链表存储结构.先序遍历二叉树先序遍历二叉树T的非递归算的非递归算法法。InitSt

5、ack(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);本讲稿第七页，共一百一十六页8步骤步骤指针指针P P栈栈StackStack内容内容访问结点值访问结点值初态初态A A1 1B BC CA A2 2D DGGB B3 3 D

6、 D4 4GG5 5C CF FGG6 6E E C C7 7 F F E E8 8F F9 9 F FA AC CB BF FE ED DGGwhile(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(

7、S)=0)/根指针退栈，根指针退栈，根指针退栈，根指针退栈，遍历右子树遍历右子树遍历右子树遍历右子树Pop(SPop(S，p);p);本讲稿第八页，共一百一十六页92.2.中序非递归遍历：中序非递归遍历：中序非递归遍历：中序非递归遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树中弹出，访问，再遍历右子树中弹出，访问，再遍历右子树中弹出，访问，再遍历右子树本讲稿第九页，共一百一十六页

8、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);

9、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本讲稿第十页，共一百一十六页11步骤步骤指针指针P P栈栈StackStack内容内容访问结访问结点值点值初态初态A A1 1A ABABA2 2B BDBADBA3 3D D DBADBA4 4 DB

10、ADBA5 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 BF FED DGwhile(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;/

11、访问结点访问结点访问结点访问结点p=p-rchild);p=p-rchild);/向右一步向右一步向右一步向右一步本讲稿第十一页，共一百一十六页121515 ECEC1616E E C CE E1717 C C1818C CF FC C1919F F F F2020 F F2121F F F F2222 A AC CB BF FE ED DGG本讲稿第十二页，共一百一十六页13中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法中序遍历的非递归算法2(2(算法算法)自学自学自学自学StatusInorderTraverse(BiTreeTStatusInorderTraverse(Bi

12、TreeT，Status(*visit(TElemTypee)Status(*visit(TElemTypee)/采用二叉链表存储结构，采用二叉链表存储结构，采用二叉链表存储结构，采用二叉链表存储结构，VisitVisit是对数据元素操作的应用函是对数据元素操作的应用函数。先序遍历二叉树数。先序遍历二叉树T T的非递归算法，对每个数据元素调用函的非递归算法，对每个数据元素调用函的非递归算法，对每个数据元素调用函的非递归算法，对每个数据元素调用函数数数数Visit。InitStack(S);p=T;while(p|!StackEmpty(S)if(p)/根指针进栈，遍历左子树根指针进栈，遍历左子

13、树根指针进栈，遍历左子树根指针进栈，遍历左子树Push(SPush(S，p);p=p-lchild;p);p=p-lchild;elseelse/访问结点，根指针退栈，遍历右子树访问结点，根指针退栈，遍历右子树访问结点，根指针退栈，遍历右子树访问结点，根指针退栈，遍历右子树Pop(SPop(S，p);visit(p-data);p=p-rchild;p);visit(p-data);p=p-rchild;本讲稿第十三页，共一百一十六页14步骤步骤指针指针P P栈栈StackStack内容内容访问结访问结点值点值初态初态A A1 1B BA A2 2D DBABA3 3 DBADBA4 4GGB

14、ABAD 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 FA AC CBF FE ED DGGif(p)if(p)/根指针进栈，遍历左子树根指针进栈，遍历左子树根指针进栈，遍历左子树根指针进栈，遍历左子树Push(SPush(S，p);p=p-p);p=p-lchild;lchild;elseelse/访问结点，根指针退栈，遍访问结点，根指针退栈，遍访问结点，根指针退栈，遍访问结点，根指针退栈，遍历右子树历右子树历右子树历右子树Pop(S，p);vis

15、it(p-p);visit(p-data);p=p-rchild;data);p=p-rchild;本讲稿第十四页，共一百一十六页153.后序非递归遍历后序非递归遍历后序非递归遍历后序非递归遍历(自学自学自学自学)与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的与前序遍历和中序遍历二叉树的算法不同，在后续遍历二叉树的过程中，对一个结点访问之前，要过程中，对一个结点访问之前，要过程中，对一个结点访问之前，要过程中，对一个结点访问之前，要两次经历这个结点两次经历这个结点两次经历这

16、个结点两次经历这个结点。第一次是由该结点找到其左孩子结点，遍历其左子树，遍历第一次是由该结点找到其左孩子结点，遍历其左子树，遍历完左子树后，返回到这个结点。完左子树后，返回到这个结点。第二次是由该结点找到其右孩子结点，遍历其右子树，遍历完右子第二次是由该结点找到其右孩子结点，遍历其右子树，遍历完右子第二次是由该结点找到其右孩子结点，遍历其右子树，遍历完右子第二次是由该结点找到其右孩子结点，遍历其右子树，遍历完右子树后，再次返回到结点，这时才能访问该结点。树后，再次返回到结点，这时才能访问该结点。树后，再次返回到结点，这时才能访问该结点。树后，再次返回到结点，这时才能访问该结点。因此，用非递归方

17、法后续遍历二叉树时，也需要设置一个栈结构，因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，因此，用非递归方法后续遍历二叉树时，也需要设置一个栈结构，用来保存指向所经历结点的指针。用来保存指向所经历结点的指针。用来保存指向所经历结点的指针。用来保存指向所经历结点的指针。本讲稿第十五页，共一百一十六页16从上面的分析可知，在后续遍历二叉树时，一个指针要进出栈两从上面的分析可知，在后续遍历二叉树时，一个指针要进出栈两从上面的分析可知，在后续遍历二叉树时，一个指针要进出栈两从上面的分析可知，在后续遍历二叉树时，一个指针要进出栈两次，第

18、一次出栈的目的是由该指针找到其左孩子结点，对该结点次，第一次出栈的目的是由该指针找到其左孩子结点，对该结点次，第一次出栈的目的是由该指针找到其左孩子结点，对该结点次，第一次出栈的目的是由该指针找到其左孩子结点，对该结点并不做任何处理，因此出栈后需再次进栈，只有在他第二次出栈并不做任何处理，因此出栈后需再次进栈，只有在他第二次出栈并不做任何处理，因此出栈后需再次进栈，只有在他第二次出栈并不做任何处理，因此出栈后需再次进栈，只有在他第二次出栈后，才能访问该结点。后，才能访问该结点。后，才能访问该结点。后，才能访问该结点。为了区别同一个结点两次出栈，设置一个标志为了区别同一个结点两次出栈，设置一个标

19、志为了区别同一个结点两次出栈，设置一个标志为了区别同一个结点两次出栈，设置一个标志flagflag，令：，令：，令：，令：11第一次出栈，结点不能访问第一次出栈，结点不能访问第一次出栈，结点不能访问第一次出栈，结点不能访问flag=flag=22第二次出栈，结点可以访问第二次出栈，结点可以访问第二次出栈，结点可以访问第二次出栈，结点可以访问本讲稿第十六页，共一百一十六页17PostOrder(BiTreet)SqStacksMAX;BiTreep;intsign;if(t=NULL)retrun;top=-1;p=t;while(!(p=NULL&top=-1)if(p!=NULL)s+top

20、.link=p;stop.flag=1;p=p-lchild;本讲稿第十七页，共一百一十六页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;本讲稿第十八页，共一百一十六页19本讲稿第十九页，共一百一十六页204.按层次遍历二叉树按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个实现方法为从上层到下层，每层中从左侧到右侧依次访问每个实现方法为从上层到下层，每层中从左侧到右侧依次访问每个实现方法为从上层到下

21、层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。个结点的遍历序列。个结点的遍历序列。个结点的遍历序列。A ACB BF FE ED DG按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为：按层次遍历该二叉树的序列为：ABCDEFGHABCDEFGH本讲稿第二十页，共一百一十六页21二叉树用顺序存储结构表示时，按层遍历的算法实现：二叉树用顺序存储结

22、构表示时，按层遍历的算法实现：二叉树用顺序存储结构表示时，按层遍历的算法实现：二叉树用顺序存储结构表示时，按层遍历的算法实现：A AC CB BF FE ED DGGAB BC CD DE EF FGG0 01 12 23 34 456 671 12 234 456 67A ACB BF FD DGGA BC CD D#FGG01 12 2345 56 671 12 23 346 67 75 5本讲稿第二十一页，共一百一十六页22voidLevelOreder(SqBiTreeBT)for(i=1;i=n;i+)if(BT.elemi!=#)coutBT.elemi);A AB BC CD D

23、E EF FGGHHI IJ JKK本讲稿第二十二页，共一百一十六页23二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：述如下：述如下：述如下：(1)(1)访问根结点，并将该结点记录下来；访问根结点，并将该结点记录下来；访问根结点，并将该结点记录下来；访问根结点，并将该结点记录下来；(2)(2)若记录的所有结点都已处理完毕，则结束遍历操作；否则若记录的所有结点都已处理完毕，则结束遍历操作；否则若记录的所有结点都已

24、处理完毕，则结束遍历操作；否则若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。重复下列操作。重复下列操作。重复下列操作。(3)(3)取出记录中第一个还没有访问孩子的结点，若它有左孩子，取出记录中第一个还没有访问孩子的结点，若它有左孩子，取出记录中第一个还没有访问孩子的结点，若它有左孩子，取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。并记录下

25、来。并记录下来。并记录下来。在这个算法中，应使用一个在这个算法中，应使用一个队列队列队列队列结构完成这项操作。所谓记录结构完成这项操作。所谓记录结构完成这项操作。所谓记录结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。访问结点就是入队操作；而取出记录的结点就是出队操作。访问结点就是入队操作；而取出记录的结点就是出队操作。访问结点就是入队操作；而取出记录的结点就是出队操作。本讲稿第二十三页，共一百一十六页24这样一来，这样一来，这样一来，这样一来，算法就可以描述成下列形式：算法就可以描述成下列形式：算法就可以描述成下列形式：算法就可以描述成下列形式：(1)访问根结点

26、，并将根结点入队；访问根结点，并将根结点入队；(2)当队列不空时，重复下列操作：当队列不空时，重复下列操作：a.a.从队列退出一个结点；从队列退出一个结点；b.b.若其有左孩子，则访问左孩子，并将其左孩子入队；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有左孩子，则访问左孩子，并将其左孩子入队；c.c.若其有右孩子，则访问右孩子，并将其右孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；本讲稿第二十四页，共一百一十六页25A AB BC CD D

27、E EF FGGHHI IJ JKK初始化初始化初始化初始化A A第一次第一次whilewhile循环循环循环循环B B C C第二次第二次第二次第二次whilewhile循环循环循环循环C CD D E E第三次第三次第三次第三次whilewhile循环循环循环循环DEF FG第四次第四次第四次第四次whilewhile循环循环循环循环E EF FGG第四次第四次第四次第四次whilewhile循环循环循环循环F FGGH I本讲稿第二十五页，共一百一十六页26voidLevelOrder(BiTreeT)voidLevelOrder(BiTreeT)if(T)exit(0);if(T)ex

28、it(0);InitQueue(Q);p=T;/初始化初始化初始化初始化coutdata;EnQueue(QEnQueue(Q，p);p);/访问根结点，并将根结点入队访问根结点，并将根结点入队 while(!QueueEmpty(Q)while(!QueueEmpty(Q)/当队非空时重复执行下列操作当队非空时重复执行下列操作当队非空时重复执行下列操作当队非空时重复执行下列操作DeQueue(Q，p);p);/出队出队出队出队if(p-Lchild)if(p-Lchild)/处理左孩子处理左孩子处理左孩子处理左孩子coutLchild;EnQueue(QcoutLchild;EnQueue(

29、Q，p-Lchild);if(p-Rchild)if(p-Rchild)/处理右孩子处理右孩子coutRchild;EnQueue(QcoutRchild;EnQueue(Q，p-Rchild);p-Rchild);本讲稿第二十六页，共一百一十六页27总结：总结：遍历的第一个和最后一个结点遍历的第一个和最后一个结点第一个结点第一个结点第一个结点第一个结点：先序：根结点；先序：根结点；中序：中序：后序：后序：最后一个结点最后一个结点：先序：先序：中序：中序：后序：根结点。后序：根结点。沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点

30、；沿着左链走，找到一个没有左孩子的结点；从根结点出发，沿着右链走，找到一个没有右从根结点出发，沿着右链走，找到一个没有右从根结点出发，沿着右链走，找到一个没有右从根结点出发，沿着右链走，找到一个没有右孩子的结点；孩子的结点；孩子的结点；孩子的结点；从根结点出发，沿着右链走，找到一个没有从根结点出发，沿着右链走，找到一个没有右孩子的结点；右孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；沿着左链走，找到一个没有左孩子的结点；本讲稿第二十七页，共一百一十六页28求中序的第一个结点求中序的第一个结点从根结点出发，沿着左链走

31、，找到一个从根结点出发，沿着左链走，找到一个没有左孩子的结点；没有左孩子的结点；的算法：的算法：的算法：的算法：求中序的第一个结点的算法：求中序的第一个结点的算法：P=T;while(P-lchild)P=P-lchild;coutdata;本讲稿第二十八页，共一百一十六页29求中序的最后一个结点的算法：求中序的最后一个结点的算法：求中序的最后一个结点的算法：求中序的最后一个结点的算法：从根结点出发，沿着右链走，从根结点出发，沿着右链走，找到一个没有右孩子的结点；找到一个没有右孩子的结点；求中序的最后一个结点的算法：求中序的最后一个结点的算法：P=T；while(P-rchild)P=P-rc

32、hild;coutdata;本讲稿第二十九页，共一百一十六页30一个程序员的生活一个程序员的生活本讲稿第三十页，共一百一十六页31本讲稿第三十一页，共一百一十六页32利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针前趋和后继结点的指针前趋和后继结点的指针前趋和后继结点的指针(这种附加的指针称为这种附加的指针称为“线索线索线索线索(Thread)”)(Thread)”)。这种加上了线索的二叉链表称为这种

33、加上了线索的二叉链表称为线索链表线索链表，相应的二叉树称为，相应的二叉树称为，相应的二叉树称为，相应的二叉树称为线索二叉树线索二叉树线索二叉树线索二叉树(ThreadedBinaryTree)(ThreadedBinaryTree)。不同的遍历有不同的线索树。不同的遍历有不同的线索树。不同的遍历有不同的线索树。不同的遍历有不同的线索树。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。线索二

34、叉树和后序线索二叉树三种。线索二叉树和后序线索二叉树三种。线索二叉树和后序线索二叉树三种。6.4线索二叉树线索二叉树本讲稿第三十二页，共一百一十六页33A ABC CD DE EF FGGHHI INULLNULLNULLNULL中序线索二叉树中序线索二叉树中序线索二叉树中序线索二叉树本讲稿第三十三页，共一百一十六页34结点的结构：结点的结构：结点的结构：结点的结构：左标志左标志ltag=ltag=右标志右标志rtag=rtag=0：lchild是指向结点的左孩子的指针是指向结点的左孩子的指针是指向结点的左孩子的指针是指向结点的左孩子的指针0：rchild是指向结点的右孩子的指针是指向结点的右

35、孩子的指针是指向结点的右孩子的指针是指向结点的右孩子的指针1：lchildlchild是指向结点的前驱的左线索是指向结点的前驱的左线索是指向结点的前驱的左线索是指向结点的前驱的左线索1 1：rchild是指向结点的后继的右线索是指向结点的后继的右线索是指向结点的后继的右线索是指向结点的后继的右线索lchildlchildltagdatartagrtagrchildrchild本讲稿第三十四页，共一百一十六页35若结点有左孩子，则若结点有左孩子，则若结点有左孩子，则若结点有左孩子，则lchildlchild指示其左孩子，否则指示其左孩子，否则指示其左孩子，否则指示其左孩子，否则lchildlch

36、ild中存储该中存储该结点的前驱结点的指针；结点的前驱结点的指针；若结点有右孩子，则若结点有右孩子，则rchildrchild指示其右孩子，否则指示其右孩子，否则指示其右孩子，否则指示其右孩子，否则rchildrchild中存储指中存储指中存储指中存储指向该结点的后继结点的指针向该结点的后继结点的指针向该结点的后继结点的指针向该结点的后继结点的指针实质：对一个非线性结构进行线性化操作，使每个结点实质：对一个非线性结构进行线性化操作，使每个结点实质：对一个非线性结构进行线性化操作，使每个结点实质：对一个非线性结构进行线性化操作，使每个结点(除第一和除第一和最后一个外最后一个外)在这些线性序列中有

37、且仅有一个直接前驱和直在这些线性序列中有且仅有一个直接前驱和直接后继。接后继。本讲稿第三十五页，共一百一十六页36DBEAFHGIC0 0A 00 0B0 00 0C C1 11 1E E11 1 F F0 01 1D D1 10 0GG0 01 1 I I11HH 1 1NULLNULLNULL中序线索链表中序线索链表ROOTROOT本讲稿第三十六页，共一百一十六页37注意：图中的实线表示指针，虚线表示线索。注意：图中的实线表示指针，虚线表示线索。结点结点D的左线索为空，表示的左线索为空，表示D是中序序列的开始结点，是中序序列的开始结点，无前趋；无前趋；结点结点C的右线索为空，表示的右线索为

38、空，表示C是中序序列的终端结点，是中序序列的终端结点，无后继。无后继。线索二叉树中，一个结点是叶结点的线索二叉树中，一个结点是叶结点的充要条件充要条件为：为：左、右标志均是左、右标志均是1本讲稿第三十七页，共一百一十六页38AB BC CDE EFGHHINULLNULLNULLNULL中序线索二叉树中序线索二叉树中序线索二叉树中序线索二叉树提问：中序线索二叉树是物理结构还是逻辑结构？提问：中序线索二叉树是物理结构还是逻辑结构？提问：中序线索二叉树是物理结构还是逻辑结构？提问：中序线索二叉树是物理结构还是逻辑结构？本讲稿第三十八页，共一百一十六页39不带表头结点的不带表头结点的先序先序穿线穿线

39、(线索线索)链表链表0 0A A0 01 B0 00 0 E E11D D1 11 1F F1NULLNULL本讲稿第三十九页，共一百一十六页40不带表头结点的不带表头结点的后序后序穿线穿线(线索线索)链表链表0 0 A A0 01 1 B B 0 00E E 1 11 1D D11F F 1 1NULL非空二叉链表非空二叉链表非空二叉链表非空二叉链表本讲稿第四十页，共一百一十六页41带表头结点的带表头结点的中序中序穿线穿线(线索线索)链表链表0 0A 01 1B0 00 0E1 11 1D 11 1F1 101 1ROOTROOT0 01 1ROOT(a)(a)空二叉链表空二叉链表(b)(b

40、)非空二叉链表非空二叉链表本讲稿第四十一页，共一百一十六页42从遍历的第一个结点来看从遍历的第一个结点来看从遍历的第一个结点来看从遍历的第一个结点来看：先序序列中第一个结点必为根结点，中、后序序列中第一个结先序序列中第一个结点必为根结点，中、后序序列中第一个结先序序列中第一个结点必为根结点，中、后序序列中第一个结先序序列中第一个结点必为根结点，中、后序序列中第一个结点的左孩子定为空点的左孩子定为空点的左孩子定为空点的左孩子定为空从遍历的最后一个结点来看：从遍历的最后一个结点来看：从遍历的最后一个结点来看：从遍历的最后一个结点来看：先、中序序列中最后一个结点的右孩子必为空，后序序列中最先、中序序

41、列中最后一个结点的右孩子必为空，后序序列中最先、中序序列中最后一个结点的右孩子必为空，后序序列中最先、中序序列中最后一个结点的右孩子必为空，后序序列中最后一个结点一定为根结点后一个结点一定为根结点后一个结点一定为根结点后一个结点一定为根结点线索二叉树的作用：线索二叉树的作用：对于遍历操作，线索树优于非线索树；遍历线索树不用设栈对于遍历操作，线索树优于非线索树；遍历线索树不用设栈对于遍历操作，线索树优于非线索树；遍历线索树不用设栈对于遍历操作，线索树优于非线索树；遍历线索树不用设栈步骤：步骤：步骤：步骤：1)1)找遍历的第一个结点找遍历的第一个结点找遍历的第一个结点找遍历的第一个结点2)不断地找

42、遍历到的结点的后继结点，直到树中各结点都遍不断地找遍历到的结点的后继结点，直到树中各结点都遍不断地找遍历到的结点的后继结点，直到树中各结点都遍不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束。历到为止，结束。历到为止，结束。历到为止，结束。遍历线索二叉树遍历线索二叉树本讲稿第四十二页，共一百一十六页43遍历中序线索二叉树遍历中序线索二叉树(带头结点带头结点)P134算法算法6.5StatusInorderTraverse_Thr(BiThrTreeTStatusInorderTraverse_Thr(BiThrTreeT，Status(*Visit)(TElemTypee)St

43、atus(*Visit)(TElemTypee)/T/T指向头结点，头结点的左链指向头结点，头结点的左链指向头结点，头结点的左链指向头结点，头结点的左链lchild指向根结点，可参见线索指向根结点，可参见线索指向根结点，可参见线索指向根结点，可参见线索化算法，中序遍历二叉线索树化算法，中序遍历二叉线索树化算法，中序遍历二叉线索树化算法，中序遍历二叉线索树T T的非递归算法的非递归算法的非递归算法的非递归算法p=T-lchild;p=T-lchild;/p指向根结点指向根结点while(p!=T)while(p!=T)/空树或遍历结束时，空树或遍历结束时，空树或遍历结束时，空树或遍历结束时，p=

44、Tp=Twhile(p-LTag=Link)p=p-lchild;if(!visit(p-data)returnERRORif(!visit(p-data)returnERROR；/访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点访问其左子树为空的结点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)/访问后继结点访问后继结点p=p-rchild;p=p-rchild;returnOK;returnOK;

45、/InOrderTraverse_Thr/InOrderTraverse_Thr本讲稿第四十三页，共一百一十六页44B BD DECFHI IKKGGJLA 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)/访问后继结点

46、访问后继结点访问后继结点访问后继结点 p=p-rchild;Visit(p-data);p=p-rchild;Visit(p-data);(4)(4)p=p-rchild;p=p-rchild;NULLNULLNULLNULLp pp1p1p2p2p3p3p4p5p5p6p6p7p8p8p9p9p10p10p11p12p12p13p13p14p14p15p15本讲稿第四十四页，共一百一十六页45B BDE EC CF FHHI IKKGGJ JL LA A(1)(1)while(p-LTag=Link)p=p-lchild;while(p-LTag=Link)p=p-lchild;(2)(2)

47、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怎样移动怎样移

48、动p本讲稿第四十五页，共一百一十六页46if(currentRTag=Thread)后继为后继为 currentrchildelse /currentRTag=Link 后继为中序遍历其右子后继为中序遍历其右子树时访问的第一个结点树时访问的第一个结点(即其即其右子树最左下的结点右子树最左下的结点)寻找当前结点寻找当前结点*current在在中序中序下下的后继的后继ABDECFHIKGJL中序后继线索二叉树中序后继线索二叉树中序后继线索二叉树中序后继线索二叉树DBGJEACHLKFIDBGJEACHLKFI本讲稿第四十六页，共一百一十六页47if(currentLTag=Thread)前驱为前驱

49、为currentlchildelse/currentLTag=Link前驱为中序遍历其左子树时最后前驱为中序遍历其左子树时最后访问的一个结点访问的一个结点(即其左子树最右即其左子树最右下的结点下的结点)寻找当前结点寻找当前结点在在中序中序下的前驱下的前驱ABDECFHIKGJL中序前驱线索二叉树中序前驱线索二叉树中序序列：中序序列：DBGJEACHLKFI本讲稿第四十七页，共一百一十六页48if(currentRTag=Thread)后继为后继为currentrchildelse/currentRTag=Link后继为其左孩子，若无左后继为其左孩子，若无左孩子，则后继为其右孩子孩子，则后继为其

50、右孩子寻找当前结点寻找当前结点*current在在先序先序下的后继下的后继先序线索二叉树先序线索二叉树先序序列先序序列ABDEGJCFHKLIABDECFHIKGJL本讲稿第四十八页，共一百一十六页49if(currentif(currentLTag=Thread)前驱为前驱为currentcurrentlchildlchildelseelse/currentcurrentLTag=LinkLTag=Link 前驱为：前驱为：前驱为：前驱为：若为根结点，则无前驱；若为根结点，则无前驱；若为根结点，则无前驱；若为根结点，则无前驱；若结点无左兄弟，则其前驱若结点无左兄弟，则其前驱为其父结点为其父结