深度优先搜索算法(Depth First Search)

DFS是搜索算法的一种。它沿着树的深度遍历树的节点,尽可能深的搜索树的分支。

当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

如右图所示的二叉树:

A 是第一个访问的,然后顺序是 B、D,然后是 E。接着再是 C、F、G。

那么,怎么样才能来保证这个访问的顺序呢?

分析一下,在遍历了根结点后,就开始遍历左子树,最后才是右子树。

因此可以借助堆栈的数据结构,由于堆栈是后进先出的顺序,由此可以先将右子树压栈,然后再对左子树压栈,

这样一来,左子树结点就存在了栈顶上,因此某结点的左子树能在它的右子树遍历之前被遍历。

广度优先搜索算法(Breadth First Search)

又叫宽度优先搜索,或横向优先搜索。

是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。

如右图所示的二叉树,A 是第一个访问的,然后顺序是 B、C,然后再是 D、E、F、G。

那么,怎样才能来保证这个访问的顺序呢?

借助队列数据结构,由于队列是先进先出的顺序,因此可以先将左子树入队,然后再将右子树入队。

这样一来,左子树结点就存在队头,可以先被访问到。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>  
#include <queue>
#include<stack>
using namespace std;

struct Node
{
int nVal;
Node *pLeft;
Node *pRight;

Node(int val,Node* left=NULL,Node * right=NULL):nVal(val),pLeft(left),pRight(right){}; //构造
};

// 析构
void DestroyTree(Node *pRoot)
{
if (pRoot==NULL)
return;

Node* pLeft=pRoot->pLeft;
Node* pRight=pRoot->pRight;

delete pRoot;
pRoot =NULL;

DestroyTree(pLeft);
DestroyTree(pRight);

}

// 用queue实现的BFS
void BFS(Node *pRoot)
{
if (pRoot==NULL)
return;

queue<Node*> Q;

Q.push(pRoot);

while(!Q.empty())
{

Node *node = Q.front();

cout<<node->nVal<<"->";
if (node->pLeft!=NULL)
{
Q.push(node->pLeft);
}

if (node->pRight!=NULL)
{
Q.push(node->pRight);
}

Q.pop();
}

cout<<endl;
}

// DFS的递归实现
void DFS_Recursive(Node* pRoot)
{
if (pRoot==NULL)
return;

cout<<pRoot->nVal<<" ";

if (pRoot->pLeft!=NULL)
DFS_Recursive(pRoot->pLeft);


if (pRoot->pRight!=NULL)
DFS_Recursive(pRoot->pRight);

}

// DFS的迭代实现版本(stack)
void DFS_Iterative(Node* pRoot)
{
if (pRoot==NULL)
return;

stack<Node*> S;
S.push(pRoot);

while (!S.empty())
{
Node *node=S.top();
cout<<node->nVal<<",";

S.pop();

if (node->pRight!=NULL)
{
S.push(node->pRight);
}

if (node->pLeft!=NULL)
{
S.push(node->pLeft);
}

}

}

// 打印树的信息
void PrintTree(Node* pRoot)
{
if (pRoot==NULL)
return;

cout<<pRoot->nVal<<" ";

if (pRoot->pLeft!=NULL)
{
PrintTree(pRoot->pLeft);
}

if (pRoot->pRight!=NULL)
{
PrintTree(pRoot->pRight);
}
}

int main()
{
Node *node1=new Node(4);
Node *node2=new Node(5);
Node *node3=new Node(6);

Node* node4=new Node(2,node1,node2);
Node* node5=new Node(3,node3);
Node* node6=new Node(1,node4,node5);


Node* pRoot = node6;
//PrintTree(pRoot);
//DFS_Recursive(pRoot);

DFS_Iterative(pRoot);
DestroyTree(pRoot);

return 0;
}