DSA 中序遍历

二叉树的中序遍历

中序遍历是一种深度优先搜索（DFS），其中每个节点按照特定顺序访问。在此处 阅读更多关于二叉树遍历的内容。

运行下面的动画，查看二叉树的中序遍历是如何完成的。

中序遍历会递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。这种遍历主要用于二叉搜索树，在这种树中，它会按升序返回值。

该遍历之所以被称为“中”序，是因为节点是在递归函数调用“之间”被访问的。节点在左子树的中序遍历之后，右子树的中序遍历之前被访问。

中序遍历的代码如下所示

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

inOrderTraversal() 函数会不断地用当前左子节点作为参数调用自身（第 4 行），直到该参数为 None，然后函数返回（第 2-3 行）。

第一次参数 node 为 None 的情况是当 C 节点的左子节点被作为参数传递时（C 没有左子节点）。

之后，节点 C 的 data 部分被打印（第 5 行），这意味着“C”是第一个被打印的内容。

然后，将节点 C 的右子节点作为参数传递（第 6 行），该参数为 None，因此函数调用在不执行任何其他操作的情况下返回。

在打印“C”之后，先前的 inOrderTraversal() 函数调用继续执行，因此“A”被打印，然后是“D”，接着是“R”，以此类推。