pta6-4 二叉树的三种遍历（先序、中序和后序） 分数 7 作者 DS课程组 单位 临沂大学

pta6-4 二叉树的三种基本遍历方法是指针对一棵二叉树的节点进行访问的方式：

1. **先序遍历**（Preorder Traversal）：首先访问根节点，然后递归地对左子树进行先序遍历，最后遍历右子树。通常表示为顺序为 "根-左-右"。在Python的字典形式下，可以表达为：

   def preorder(node):
       if node is not None:
           print(node.value)  # 先访问节点值
           preorder(node.left)  # 再访问左子树
           preorder(node.right)  # 最后访问右子树

2. **中序遍历**（Inorder Traversal）：先遍历左子树，然后访问根节点，最后遍历右子树。这个顺序常用于排序，因为对于每个非空节点，其左子树的所有节点值都小于它，而其右子树所有节点值大于它。顺序为 "左-根-右"。

   def inorder(node):
       if node is not None:
           inorder(node.left)
           print(node.value)
           inorder(node.right)

3. **后序遍历**（Postorder Traversal）：先遍历左子树，再遍历右子树，最后访问根节点。顺序为 "左-右-根"。这个遍历常用于计算表达式的值或者打印树形结构的逆序。

   def postorder(node):
       if node is not None:
           postorder(node.left)
           postorder(node.right)
           print(node.value)

每种遍历都有其特定的应用场景，比如构建表达式树、打印文件目录等。