树的遍历

从二叉树的根节点出发，节点的遍历分为三个主要步骤：对当前节点进行操作（称为“访问”节点，或者根节点）、遍历左边子节点、遍历右边子节点。访问节点顺序的不同也就形成了不同的遍历方式。需要注意的是树的遍历通常使用递归的方法进行理解和实现，在访问元素时也需要使用递归的思想去理解。实际实现中对于前序和中序遍历可尝试使用递归实现。

按照访问根元素(当前元素)的前后顺序，遍历方式可划分为如下几种：

深度优先：先访问子节点，再访问父节点，最后访问第二个子节点。根据根节点相对于左右子节点的访问先后顺序又可细分为以下三种方式 a, 前序遍历（pre-order），根—>左—>右 b, 中序遍历（in-order）左—>根—>右 c, 后序遍历（post-order）左—>右—>根

广度优先：先访问根节点，沿着树的宽度遍历子节点，直到所有节点均被访问为止

二叉树的广度优先遍历和树的前序/中序/后序遍历不太一样，前/中/后序遍历使用递归，也就是栈的思想对二叉树进行遍历，广度优先一般使用队列的思想对二叉树进行遍历。

python实现程序：

 1 class TreeNode:
 2     def __init__(self, val):
 3         self.val = val
 4         self.left, self.right = None, None
 5 
 6 class Traversal(object):
 7     def __init__(self):
 8         self.traverse_path = list()
 9 
10     def preorder(self, root):
11         if root:
12             self.traverse_path.append(root.val)
13             self.preorder(root.left)
14             self.preorder(root.right)
15 
16     def inorder(self,root):
17         if root:
18             self.inorder(root.left)
19             self.traverse_path.append(root.val)
20             self.inorder(root.right)
21 
22     def postorder(self,root):
23         if root:
24             self.postorder(root.left)
25             self.postorder(root.right)
26             self.traverse_path.append(root.val)

本文摘自https://algorithm.yuanbin.me/zh-hans/basics_data_structure/binary_tree.html