二叉树遍历：先序、中序、后序遍历详解

二叉树遍历：先序、中序、后序遍历详解

二叉树遍历是指按照一定的规则访问树中的所有节点。常见的遍历方式有三种：先序遍历、中序遍历和后序遍历。

1. 先序遍历

规则：

1. 访问根节点。
2. 递归地先序遍历左子树。
3. 递归地先序遍历右子树。

示例：

     a
    / \ 
   b   c
  / \   / 
 d  e f  
 /
 g

先序遍历结果： a b d g e c f

2. 中序遍历

规则：

1. 递归地中序遍历左子树。
2. 访问根节点。
3. 递归地中序遍历右子树。

示例：

     a
    / \ 
   b   c
  / \   / 
 d  e f  
 /
 g

中序遍历结果： g d b e a f c

3. 后序遍历

规则：

1. 递归地后序遍历左子树。
2. 递归地后序遍历右子树。
3. 访问根节点。

示例：

     a
    / \ 
   b   c
  / \   / 
 d  e f  
 /
 g

后序遍历结果： g d e b f c a

总结

三种遍历方式各有特点，适用于不同的应用场景。理解二叉树遍历是学习数据结构的基础，也是理解树形结构算法的关键。