深度优先搜索（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
*/
由此可见，运行结果是一样的。
我们来画图分析如下：
我们简化此图形，此图一般称之为深搜树，剪枝一词便来源于此
记忆化深度搜索
点点的
标签：Node,优先,遍历,int,DFS,right,搜索,new,delete From： https://www.cnblogs.com/zshsboke/p/17013164.html