不使用递归进行中序遍历

二叉树的节点可以通过一种称为中序遍历的技术以精确的顺序进行访问。在遍历过程中，节点的访问顺序如下：左子节点、根节点，然后是右子节点。由于在访问根节点和右子节点之间访问左子节点，因此此过程称为“中序”。

下面提供了中序遍历二叉树的步骤大纲

i) 访问左子节点：递归地遍历左子树。也就是说，转到当前节点的左子节点。

ii) 访问当前节点，然后访问根节点。

iii) 访问右子节点：递归地遍历右子树。也就是说，转到当前节点的右子节点。

中序遍历二叉树有几个好处。

1. 排序：通过使用中序遍历，可以按照值的升序访问二叉搜索树（BST）中的节点。对于需要以排序方式处理或显示数据的应用程序，此属性非常有帮助。
2. BST验证：通过确保节点按正确的顺序（升序）访问，可以使用中序遍历来确定给定的二叉树是否为有效的二叉搜索树（BST）。
3. 表达式求值：二叉树有时用于表示算术表达式。当与此类表达式树一起使用时，中序遍历允许使用正确的运算顺序来求值表达式。
4. BST恢复：如果BST被意外更改（例如，通过交换两个节点），则中序遍历后进行顺序校正可以帮助恢复原始的有效BST。
5. 线索二叉树：在线索二叉树中，节点具有额外的线索，无需占用额外内存即可将它们链接起来，中序遍历起着至关重要的作用。这些线索能够高效地遍历线索二叉树。

中序遍历二叉树的缺点

1. 递归方法：递归中序遍历是传统方法，尽管对于非常深的树，递归调用堆栈可能导致堆栈溢出。
2. 空间复杂度：由于调用堆栈需要更多空间，因此对于大型树，递归方法在内存效率方面较低。
3. 非递归复杂度：非递归遍历过程可能会变得更加复杂，因为管理堆栈需要额外的代码。
4. 非BST树：当树不是BST时，或者遍历顺序无关紧要时，使用不同的遍历技术可能更合适、更有效。

代码

为什么会发生递归？

在计算机编程中，当一个函数直接或间接地调用自身时，就会发生递归。递归是一种通过将问题分解成更小、更易于管理子问题来解决问题的方法。递归是编程中的一个基本概念，广泛应用于许多不同的算法和数据结构中。

以下是递归的主要原因

1. 递归能够将一个问题分解成更小、更易于管理的子问题。每次进行递归调用时，它都会处理原始问题的一个更小或更简单的版本，使其更接近于基本情况，在基本情况下，答案是显而易见的或简单的。
2. 在优雅性和清晰性方面，递归解决方案通常比迭代解决方案更优雅、更易于理解。递归代码在某种程度上可以非常接近一个人解决问题的方式。

结论

总之，中序二叉树遍历能够按排序顺序遍历节点，因此更受欢迎。这使其在排序、验证二叉搜索树和求值表达式等活动中非常有用。但是，由于其递归性、空间复杂性和适用性，它可能不适用于非BST树。应根据树的精确需求和特性以及要解决的问题来选择遍历方法。