深度优先搜索（DFS）

我们以二叉树的遍历为例子。

先序遍历

遍历过程

访问根节点
先序遍历其左子树
先序遍历其右子树

中序序遍历

遍历过程

中序遍历其左子树
访问根节点
中序遍历其右子树

后序遍历

遍历过程

后序遍历其左子树
后序遍历其右子树
访问根节点

我们使用数组来模拟二叉数，使用代码实现如下：

展开查看

#include<bits/stdc++.h>
using namespace std;
const int N = 9;
int a[N]; // 根节点在a[1]
void proOrder(int index){
    if(index >= N) return;
    cout << a[index] << endl;
    proOrder(2 * index);
    proOrder(2 * index + 1);
}
int main(){
    for(int i = 1; i < N; i ++ ) a[i] = i;
    proOrder(1);
    return 0;
}
/*
运行结果
1
2
4
8
5
3
6
7
*/

我们使用结构体模拟二叉树，代码实现如下：

展开查看

#include<bits/stdc++.h>
using namespace std;
struct Node{
    Node(int val){
        this -> val = val;
        this -> left = nullptr;
        this -> right = nullptr;
    }
    int val;
    Node *left;
    Node *right;
};
void proOrder(Node *node){
    if(!node) return;
    cout << node -> val << endl;
    proOrder(node -> left);
    proOrder(node -> right);
}
int main(){
    Node *node1 = new Node(1);
    Node *node2 = new Node(2);
    Node *node3 = new Node(3);
    Node *node4 = new Node(4);
    Node *node5 = new Node(5);
    Node *node6 = new Node(6);
    Node *node7 = new Node(7);
    node1 -> left = node2;
    node1 -> right = node3;
    node2 -> left = node4;
    node2 -> right = node5;
    node3 -> left = node6;
    node3 -> right = node7;
    proOrder(node1);
    delete node1;
    delete node2;
    delete node3;
    delete node4;
    delete node5;
    delete node6;
    delete node7;
    return 0;
}
/*
运行结果
1
2
4
8
5
3
6
7
*/

由此可见，运行结果是一样的。
我们来画图分析如下：

我们简化此图形，此图一般称之为深搜树，剪枝一词便来源于此