采用栈数据结构的二叉树非递归遍历

  • 时间:
  • 浏览:1
  • 来源:5分6合APP下载_5分6合APP官方

  【补充】和本文相关的我写的你你是什么博客文章:

  现在,引入栈数据社会形态,它是另另好几个 元素为节点指针的数组,将上面的递归函数改写为非递归函数。中序遍历的基本法律最好的办法是:

  (1)pop 栈顶的节点,并访问此节点 (line 150 ~ 33);

  很明显,对应于前面给出的定义,只需要调整上述代码中行号为 14,15,16 的顺序,就都可不能能 得到相应的遍历序。

  (3)偷窥栈顶部节点,意味着着节点的左子节点不为 NULL,且没了被访问,则将其左子节点 push 入栈,并跳到(3)。

  (2)当栈不为空时,重复(3)到(5)的操作:

  (3)push 右子节点 (line 35 ~ 41);

  其中序遍历的输出为:1,2,3,4,5,6,7,8,9;

  都可不能能 看一遍,释放树(FreeTree)你你是什么函数,只是按照后序遍历的顺序进行释放的。

  从上面的代码中,有两点需要说明:

  (4)当被偷窥的节点没了左子树,pop 该节点出栈,并访问它(一块儿标记该节点为已访问情况报告)。

  在这里我思考的问题是,很显然,循环都可不能能 改写为递归函数。递归函数否是借助栈你你是什么数据社会形态改写为循环呢。意味着着函数调用中,call procedure stack 中存储了流程的 context,调用和返回大约根据调用栈中的 context 进行跳转。而采用 stack 数据社会形态时,主要还是另另好几个 顺序循环社会形态,主要通过 continue 实现流程控制。

  对二叉查找树 BST 来说,中序遍历的输出,是排序结果。全都这里我以另另好几个 BST 的中序遍历为主要例子说明问题。另另好几个 简单的 BST 如下图所示(为了保证美观精确,下图由我临时编写的另另好几个 VC 窗口系统应用应用程序绘制为样本进行加工得到的):

  最后,补充上你你是什么从不重要的法律最好的办法,创建树,释放树,main 函数的代码如下(把已有所有代码拼在一块儿即构成完全的 Demo 系统应用应用程序):

  在上面的代码的 while 循环体内,都可不能能 分为另另好几个 小的代码块:

  (2)中序遍历:左子节点,当前节点,右子节点;

  完后 面的 BST 为例,在非递归函数中,栈情况报告的动态变化如下图所示(下图主要由 Excel 和 Photoshop 制作):

  (1)将根节点 push 入栈;

  (3)后序遍历:左子节点,右子节点,当前节点。

  【后记】

  (1)前序遍历:当前节点,左子节点,右子节点;

  

  

  假如有一天调整 while 循环体中的这另另好几个 代码块的顺序,就都可不能能 分别实现并就有遍历序。累似 ,前序:(1)(2)(3);后序:(2)(3)(1)。

  根据以上法律最好的办法,给出非递归函数的中序遍历版本代码如下:

  (1)最后另另好几个 代码块中的 continue 都可不能能 需要写,但为了都可不能能 调整代码块的顺序,另另好几个 continue 总要需要的。

  首先,给出遍历二叉树的序的定义:

  (2)push 左子节点 (line 22 ~ 28);

  【前言】树的遍历,根据访问自身和其子节点之间的顺序关系,分为前序,后序遍历。对于二叉树,每个节点至多有另另好几个 子节点(一阵一阵的称为左,右子节点),又有中序遍历。意味着着树自身具有的递归性,什么遍历函数使用递归函数很容易实现,代码也非常简洁。借有助数据社会形态中的栈,都可不能能 把树遍历的递归函数改写为非递归函数。

  (5)当该节点的右子节点不为空,将其右子节点 push 入栈,并跳到(3)。

  (2)意味着着前序遍历的逻辑的简洁性,不借有助 bVisited 标记,也都可不能能 完成遍历,但为了通用,还是需要你你是什么节点标记。

  首先给出中序遍历的递归函数,代码如下:

  献给只是向我请教“采用非递归法律最好的办法遍历树”的 小玉(littlehead)学妹。

  (2)[非原创]树和图的遍历。1508-8-10;

  (1)采用路径模型实现遍历二叉树的法律最好的办法。2013-5-18;

猜你喜欢

游客uzeogvglzl7a4的主页

MaxCompute生态文章:2丨粉丝:64241丨话题:0文章:12丨粉丝:64328丨话题:1文章:30丨粉丝:63040丨话题:0阿里云ET专家,重点在智能语音、人脸识别

2020-02-25

成功运作一个开源项目的15个要点

13、管理知识产权和版权文档化项目的代码格式规则(使代码格式化预设易于访问),对测试覆盖面、开发措施、软件和所需工具的期望,与项目团队联系的渠道以及针对潜在贡献者的这些 重要

2020-02-25

有技术,爱写博客?那就来云栖社区吧!无人机大奖等你拿!

所有参加活动的技术亲(符合规定的),均可获得150元阿里云通用代金券参与法律法律依据:奖品设置:让人跟阿里专家同场竞技“内容最优质量”奖(3名):活动流程:更能不能 通过持续

2020-02-25

全球获得诺贝尔文学奖的有多少人

台湾残疾青年郑丰喜他真是先天身患小儿麻痹,落得双腿残疾,差许多就被家人背叛,幸而爷爷与二婶等人的呵护与庇护,才得以新生,能能从艰难困苦的人生境遇中成长起来。已经 来家贫困,幼

2020-02-25

技术流|使用开源项目的正确姿势:如果没有你要的轮子,那就重新造吧!

还是以上面提到的TT为例:这里让一群人的经验是聚焦于有无满足业务,而不能自己过于关注开源方案有无牛逼。什么都有有让一群人的建议是太少改动原系统,而是要开发辅助系统: 监控,报警

2020-02-24