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

  • 时间:
  • 浏览:0
  • 来源:彩神欢乐生肖_神彩欢乐生肖官方

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

  现在,引入栈数据形态学 ,它是有4个 元素为节点指针的数组,将底下的递归函数改写为非递归函数。中序遍历的基本法子是:

  (2)不可能 前序遍历的逻辑的简洁性,不借有助 bVisited 标记,不都都还可以 完成遍历,但为了通用,还是都要一种生活节点标记。

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

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

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

  (1)最后有4个 代码块中的 continue 都都还可以 不都要写,但为了都都还可以 调整代码块的顺序,有4个 continue 都不 都要的。

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

  

  从底下的代码中,有两点都要说明:

  (1)将根节点 push 入栈;

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

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

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

  【补充】和本文相关的我写的一种生活博客文章:

  【后记】

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

  在底下的代码的 while 循环体内,都都还可以 分为有4个 小的代码块:

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

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

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

  只要调整 while 循环体中的这有4个 代码块的顺序,就都都还可以 分别实现一种生活遍历序。类似,前序:(1)(2)(3);后序:(2)(3)(1)。

  献给过后向我请教“采用非递归法子遍历树”的 小玉(littlehead)学妹。

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

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

  【前言】树的遍历,根据访问自身和其子节点之间的顺序关系,分为前序,后序遍历。对于二叉树,每个节点至多有有4个 子节点(不怎么的称为左,右子节点),又有中序遍历。不可能 树自身具有的递归性,哪些地方地方遍历函数使用递归函数很容易实现,代码也非常简洁。借有助数据形态学 中的栈,都都还可以 把树遍历的递归函数改写为非递归函数。

  都都还可以 看得人,释放树(FreeTree)一种生活函数,所以 按照后序遍历的顺序进行释放的。

  最后,补充上一种生活从不重要的法子,创建树,释放树,main 函数的代码如下(把已有所有代码拼在一起去即构成完全的 Demo 线程池池运行):

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

  (3)偷窥栈顶部节点,不可能 节点的左子节点不为 NULL,且这么 被访问,则将其左子节点 push 入栈,并跳到(3)。

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

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

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

  

  在这里我思考的问題是,很显然,循环都都还可以 改写为递归函数。递归函数否是 借助栈一种生活数据形态学 改写为循环呢。不可能 函数调用中,call procedure stack 中存储了流程的 context,调用和返回大约根据调用栈中的 context 进行跳转。而采用 stack 数据形态学 时,主要还是有4个 顺序循环形态学 ,主要通过 continue 实现流程控制。