深度优先搜索（DFS， Depth-First-Search）

在深度优先搜索中，遍历树是从根开始的，在每个子节点上采用递归方法遍历树，尽可能的深入到树中，然后遍历下一个兄弟节点。而在深度优先搜索中有三种顺序：中序、前序和后序。

一、中序遍历和中缀表示法

 其工作流程如下：检查当前节点是否为空，如果不为空就遍历树：
1.遍历左子树并递归调用 inorder 函数

2.访问根节点

3.遍历右边的子树，递归调用 inorder 函数

现在，给出一个二叉树的结构画像

 

 对于中序遍历二叉树，首先，递归访问根节点的左子树的根节点B， 从而递归的得到B节点的左子树D，以此反复，当到达G节点时，G节点没有子节点，则开始回溯。先获取G节点的值，然后是D节点，最后是H节点，最后，对于D子树以全部遍历完毕，重新回到B结点开始遍历，以此类推：

整个中序遍历的顺序为：G-D-H-B-E-A-C-F

相关代码：

class Node:     # 节点类
    """每个节点包含存储数据和指向子节点的指针， 而对于二叉树来说，则只有两个即左节点和右节点"""

    def __init__(self, data=None):
        self.data = data            # 数据
        self.right_child = None     # 右节点
        self.left_child = None      # 左节点

class Tree:     # 树结构类，暂时仅添加遍历函数

    def __init__(self, data=None):
        self.root = Node(data)

    def inorder(self, root):        # 中序遍历
        current = root
        if not current: return
        self.inorder(current.left_child)
        print(current.data)
        self.inorder(current.right_child)


# 手动创建节点
a = Node("A")
b = Node("B")
c = Node("C")
d = Node("D")
e = Node("E")
f = Node("F")
g = Node("G")
h = Node("H")

# 构建关系
a.left_child = b
a.right_child = c

b.left_child = d
b.right_child = e
c.right_child = f

d.left_child = g
d.right_child = h

# 调用Tree中的inorder函数实现中序遍历
tree = Tree()
tree.inorder(a)

运行结果：

G
D
H
B
E
A
C
F

结果与预想一致。这种表达方式比较适合表达式二叉树使用，根节点存储二元运算符，叶节点则按照特定顺序存入被运算数。后面会提到。

二、前序遍历和前缀表达式

前序遍历的顺序为：

1.从根节点开始遍历

2.遍历左子节点并调用 preorder 函数

3.遍历右子节点并调用 preorder 函数

同样对于如下的一个二叉树结构，它的前序遍历顺序为：A-B-D-G-H-E-C-F

相关函数代码如下：

    def preorder(self, root):       # 前序遍历
        current = root
        if not current: return 
        print(current.data)
        self.preorder(current.left_child)
        self.preorder(current.right_child)

将preorder函数的代码添加到Tree类中，并修改最后的调用：

# 调用Tree中的preorder函数实现中序遍历
tree = Tree()
tree.preorder(a)

运行结果：

A
B
D
G
H
E
C
F

与预期一致。

前缀表示法同时也被称为逆波兰表达式，在这种表达式中，运算符出现在被运算数之前

例如：* + 4 5 - 5 3

对于这样的表达式，存入二叉树是极其方便的。

三、后序遍历和后缀表达式

后缀遍历的顺序为：

1.遍历左子树并调用postder函数

2.遍历右子树并调用postder函数

3.访问根节点

对于同样的二叉树结构，后续遍历的顺序为：G-H-D-E-B-F-C-A

 

相关代码：

    def postorder(self,root):       # 后续遍历
        current = root
        if not current: return
        self.postorder(current.left_child)
        self.postorder(current.right_child)
        print(current.data)

以及最后调用函数的更改：

# 调用Tree中的postorder函数实现中序遍历
tree = Tree()
tree.postorder(a)

运行结果：

G
H
D
E
B
F
C
A