DSA 中序遍历

二叉树的中序遍历

中序遍历是一种深度优先搜索，其中每个节点都以特定的顺序访问。了解更多关于二叉树遍历的信息，请访问这里。

运行下面的动画，了解如何进行二叉树的中序遍历。

中序遍历对左子树进行递归中序遍历，访问根节点，最后对右子树进行递归中序遍历。这种遍历主要用于二叉搜索树，它以升序返回值。

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

这是中序遍历代码的示例

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

The inOrderTraversal() function keeps calling itself with the current left child node as an argument (line 4) until that argument is None and the function returns (line 2-3).

The first time the argument node is None is when the left child of node C is given as an argument (C has no left child).

After that, the data part of node C is printed (line 5), which means that 'C' is the first thing that gets printed.

Then, node C's right child is given as an argument (line 6), which is None, so the function call returns without doing anything else.

After 'C' is printed, the previous inOrderTraversal() function calls continue to run, so that 'A' gets printed, then 'D', then 'R', and so on.