中序遍历

在本文中，我们将讨论数据结构中的中序遍历。

如果我们想按升序遍历节点，那么我们就使用中序遍历。以下是中序遍历所需的步骤：

• 访问左子树的所有节点
• 访问根节点
• 访问右子树的所有节点

栈、数组、队列等线性数据结构只有一种遍历数据的方式。但在树等层次化数据结构中，有多种遍历数据的方式。在这里，我们将讨论另一种遍历树数据结构的方法，即中序遍历。

中序遍历有两种常用方法：

• 递归中序遍历
• 迭代法中序遍历

中序遍历技术遵循**左根右**的策略。其中，左根右意味着首先遍历根节点的左子树，然后是根节点，最后是根节点的右子树。在这里，中序名称本身就表明根节点位于左子树和右子树之间。

我们将讨论递归和迭代两种方法的中序遍历。让我们先从递归的中序遍历开始。

递归中序遍历

中序遍历示例

现在，让我们看一个中序遍历的例子。通过示例更容易理解中序遍历的过程。

黄色的节点尚未访问。现在，我们将使用中序遍历来遍历上述树的节点。

• 这里，40是根节点。我们移动到 40 的左子树，即 30，它也有子树 25，所以我们再次移动到 25 的左子树，即 15。这里，15 没有子树，所以**打印 15** 并移向它的父节点，25。
  
• 现在，**打印 25** 并移到 25 的右子树。
  
• 现在，**打印 28** 并移到 25 的根节点，即 30。
  
• 所以，30 的左子树已被访问。现在，**打印 30** 并移到 30 的右子节点。
  
• 现在，**打印 35** 并移到 30 的根节点。
  
• 现在，**打印根节点 40** 并移到它的右子树。
  
• 现在递归地遍历 40 的右子树，即 50。
  50 有子树，所以首先遍历 50 的左子树，即 45。45 没有子节点，所以**打印 45** 并移到它的根节点。
  
• 现在**打印 50** 并移到 50 的右子树，即 60。
  
• 现在递归地遍历 50 的右子树，即 60。60 有子树，所以首先遍历 60 的左子树，即 55。55 没有子节点，所以**打印 55** 并移到它的根节点。
  
• 现在**打印 60** 并移到 60 的右子树，即 70。
  
• 现在**打印 70**。
  

中序遍历完成后，最终输出为：

{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}

中序遍历的复杂度

中序遍历的时间复杂度为 **O(n)**，其中 'n' 是二叉树的大小。

而，如果不考虑函数调用的栈大小，中序遍历的空间复杂度为 **O(1)**。否则，中序遍历的空间复杂度为 **O(h)**，其中 'h' 是树的高度。

中序遍历的实现

现在，让我们看看不同编程语言中中序遍历的实现。

程序：编写一个 C 语言程序来实现中序遍历。

输出

程序：编写一个 C++ 程序来实现中序遍历。

输出

程序：编写一个 C# 程序来实现中序遍历。

输出

程序：编写一个 Java 程序来实现中序遍历。

输出

所以，这就是关于本文的全部内容。希望本文能对您有所帮助并提供信息。