深度優(yōu)先搜索算法（Depth First Search），是搜索算法的一種。是沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。
當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。
如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個作為源節(jié)點(diǎn)并重復(fù)以上過程，整個進(jìn)程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。
如右圖所示的二叉樹：
A 是第一個訪問的，然后順序是 B、D，然后是 E。接著再是 C、F、G。
那么，怎么樣才能來保證這個訪問的順序呢？
分析一下，在遍歷了根結(jié)點(diǎn)后，就開始遍歷左子樹，最后才是右子樹。
因此可以借助堆棧的數(shù)據(jù)結(jié)構(gòu)，由于堆棧是后進(jìn)先出的順序，由此可以先將右子樹壓棧，然后再對左子樹壓棧，
這樣一來，左子樹結(jié)點(diǎn)就存在了棧頂上，因此某結(jié)點(diǎn)的左子樹能在它的右子樹遍歷之前被遍歷。
深度優(yōu)先遍歷代碼片段
//深度優(yōu)先遍歷
void depthFirstSearch(Tree root){
stack<Node *> nodeStack; //使用C++的STL標(biāo)準(zhǔn)模板庫
nodeStack.push(root);
Node *node;
while(!nodeStack.empty()){
node = nodeStack.top();
printf(format, node->data); //遍歷根結(jié)點(diǎn)
nodeStack.pop();
if(node->rchild){
nodeStack.push(node->rchild); //先將右子樹壓棧
}
if(node->lchild){
nodeStack.push(node->lchild); //再將左子樹壓棧
}
}
}
廣度優(yōu)先搜索算法（Breadth First Search），又叫寬度優(yōu)先搜索，或橫向優(yōu)先搜索。
是從根節(jié)點(diǎn)開始，沿著樹的寬度遍歷樹的節(jié)點(diǎn)。如果所有節(jié)點(diǎn)均被訪問，則算法中止。
如右圖所示的二叉樹，A 是第一個訪問的，然后順序是 B、C，然后再是 D、E、F、G。
那么，怎樣才能來保證這個訪問的順序呢？
借助隊列數(shù)據(jù)結(jié)構(gòu)，由于隊列是先進(jìn)先出的順序，因此可以先將左子樹入隊，然后再將右子樹入隊。
這樣一來，左子樹結(jié)點(diǎn)就存在隊頭，可以先被訪問到。
廣度優(yōu)先遍歷代碼片段
//廣度優(yōu)先遍歷
void breadthFirstSearch(Tree root){
queue<Node *> nodeQueue; //使用C++的STL標(biāo)準(zhǔn)模板庫
nodeQueue.push(root);
Node *node;
while(!nodeQueue.empty()){
node = nodeQueue.front();
nodeQueue.pop();
printf(format, node->data);
if(node->lchild){
nodeQueue.push(node->lchild); //先將左子樹入隊
}
if(node->rchild){
nodeQueue.push(node->rchild); //再將右子樹入隊
}
}
}
完整代碼:
/**
* <!--
* File : binarytree.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <Stack>
#include <Queue>
using namespace std;
#define Element char
#define format "%c"
typedef struct Node {
Element data;
struct Node *lchild;
struct Node *rchild;
} *Tree;
int index = 0; //全局索引變量
//二叉樹構(gòu)造器,按先序遍歷順序構(gòu)造二叉樹
//無左子樹或右子樹用'#'表示
void treeNodeConstructor(Tree &root, Element data[]){
Element e = data[index++];
if(e == '#'){
root = NULL;
}else{
root = (Node *)malloc(sizeof(Node));
root->data = e;
treeNodeConstructor(root->lchild, data); //遞歸構(gòu)建左子樹
treeNodeConstructor(root->rchild, data); //遞歸構(gòu)建右子樹
}
}
//深度優(yōu)先遍歷
void depthFirstSearch(Tree root){
stack<Node *> nodeStack; //使用C++的STL標(biāo)準(zhǔn)模板庫
nodeStack.push(root);
Node *node;
while(!nodeStack.empty()){
node = nodeStack.top();
printf(format, node->data); //遍歷根結(jié)點(diǎn)
nodeStack.pop();
if(node->rchild){
nodeStack.push(node->rchild); //先將右子樹壓棧
}
if(node->lchild){
nodeStack.push(node->lchild); //再將左子樹壓棧
}
}
}
//廣度優(yōu)先遍歷
void breadthFirstSearch(Tree root){
queue<Node *> nodeQueue; //使用C++的STL標(biāo)準(zhǔn)模板庫
nodeQueue.push(root);
Node *node;
while(!nodeQueue.empty()){
node = nodeQueue.front();
nodeQueue.pop();
printf(format, node->data);
if(node->lchild){
nodeQueue.push(node->lchild); //先將左子樹入隊
}
if(node->rchild){
nodeQueue.push(node->rchild); //再將右子樹入隊
}
}
}
/**
* <!--
* File : BinaryTreeSearch.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include "binarytree.h"
int main() {
//上圖所示的二叉樹先序遍歷序列,其中用'#'表示結(jié)點(diǎn)無左子樹或無右子樹
Element data[15] = {'A', 'B', 'D', '#', '#', 'E', '#', '#', 'C', 'F','#', '#', 'G', '#', '#'};
Tree tree;
treeNodeConstructor(tree, data);
printf("深度優(yōu)先遍歷二叉樹結(jié)果: ");
depthFirstSearch(tree);
printf("\n\n廣度優(yōu)先遍歷二叉樹結(jié)果: ");
breadthFirstSearch(tree);
return 0;
}
posted on 2013-02-03 12:52
fancydeepin 閱讀(31255)
評論(4) 編輯 收藏