二叉树的中序遍历

有空一起学习 2020年2月9日11:20:23 发表评论
文章最后编辑于:2020-2-9 11:22:16

一、中序遍历

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

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

二叉树的中序遍历

二、非递归实现

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

实现原理:

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

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

代码描述:

三、递归实现

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

本文共执行69次查询,耗时0.692秒!
历史上的今天
二月
9
有空一起学习

发表评论

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