二叉树的中序遍历

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2020年2月9日11:20:23 评论

一、中序遍历

中序遍历过程:先访问左子节点,然后访问当前节点,最后访问右子节点。

以下试一次中序遍历过程:

二叉树的中序遍历

二、非递归实现

非递归方式遍历依赖栈来实现,因为要先访问子节点,然后访问父节点,因此必须要有一个数据结构来保存已经父节点。

实现原理:

  1. 每次遍历到一个节点,不访问它,先压栈,然后对左子树循环做这个操作。
  2. 遍历左节点直到左节点为空时,取出栈顶元素,访问它。
  3. 然后对这个栈顶元素的右节点重复执行第一个步骤。

大致的逻辑和前序遍历差不多,相对于前序遍历而言,中序遍历知识把访问节点的时机延后了一些。前序遍历可以参考二叉树的先序遍历

代码描述:

三、递归实现

递归实现很简单,不做详细描述:

历史上的今天
二月
9
马谦马谦马谦
  • 本文由 发表于 2020年2月9日11:20:23
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/inorder-traversal-in-binary-trees.html
二叉树的后序遍历 数据结构和算法

二叉树的后序遍历

一、后序遍历 后序遍历逻辑:优先访问左、右子节点,然后访问当前节点。 一个后序遍历的示例,它的后序遍历结果为: 二、非递归实现 后序遍历的非递归实现比前序和中序的非递归实现要复杂很多,因为每个节点都可...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: