遍历

先序遍历二叉树的递归算法怎样理解????(严蔚敏主编)
更新时间:2019-12-19 13:34 浏览:59 关闭窗口 打印此页

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  要想把所有的数据都访问到则必需按照一定的原则,即当前结点的下一个结点是哪个结点。

  无论是先、中还是后序算法都是先将左结点视为下一个结点,当左结点不存在(即为空时)才将右结点视作下一个结点,如果右结点也不存在就返回当前结点的上层结点再向右访问,如此类推。

  先序遍历的策略是按123的步骤执行,中序是按213来,后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。

  看着你刚画好的那个BitTree跟着我的思路走。在先序遍历算法PriorOrder中,先将BitTree的头结点A传进来,按步骤123的处理。123是抽象实现,记住所表达的思想,下面是具体实现。为了避免混乱用中文数字记录步骤。

  一、即是读取结点A的数据内容A(此时A为当前函数处理结点),将A的右结点C放入栈S中,S中的内容为S(C)[注意这一步是算法的一个辅助,并不是先向右访问,下同],将左结点B传给PriorOrder处理。此时读取了A

  二、读取B的内容B(此时B为当前结点),将B的右结点E放入S中,S中的内容为S(C,E),将B的左结点D传给PriorOrder处理。此时读取了AB

  三、D为当前结点,D的右为空没有东西放入S,S中的内容仍为S(C,E),D的左也为空,没有访问可访问的。此时就从S中取出E(因为栈是先进后出的所以取的就是E,此时S中的内容为S(C),正好是上一层没访问过的右子树),将E传给PriorOrder处理。此时读取了AB D

  五、F为当前结点,右为空,左也为空,读取了ABDEF,从栈中取出G传给PriorOrder处理,S的内容为S(C);

  六、类似的读取了ABDEFG,从S中取出了C,传给PriorOrder处理。此时S()。

  七、当前结点为C,从将C的右结点放入S,S中内容为S(H),C的左为空,从S取出H,将H传给PriorOrder处理。此时S为S().于是就读取了ABDEFGC

  你再对照的书上的算法想想,画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用,后执行完”,或者说“后调用,先执行完”。注意我加一个“完”字

  要想把所有的数据都访问到则必需按照一定的原则,即当前结点的下一个结点是哪个结点。

  无论是先、中还是后序算法都是先将左结点视为下一个结点,当左结点不存在(即为空时)才将右结点视作下一个结点,如果右结点也不存在就返回当前结点的上层结点再向右访问,如此类推。

  先序遍历的策略是按123的步骤执行,中序是按213来,后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。

  看着你刚画好的那个BitTree跟着我的思路走。在先序遍历算法PriorOrder中

上一篇文章:上一篇:String数组常用的几种遍历方法
下一篇文章 :下一篇:遍历是什么意思?
友情链接:

公司地址:

监督热线: