深度优先搜索算法（depth first search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
如右图所示的二叉树：
a 是第一个访问的，然后顺序是 b、d，然后是 e。接着再是 c、f、g。
那么，怎么样才能来保证这个访问的顺序呢？
分析一下，在遍历了根结点后，就开始遍历左子树，最后才是右子树。
因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序，由此可以先将右子树压栈，然后再对左子树压栈，
这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。
深度优先遍历代码片段
//深度优先遍历
void depthfirstsearch(tree root){
stack<node *> nodestack; //使用c 的stl标准模板库
nodestack.push(root);
node *node;
while(!nodestack.empty()){
node = nodestack.top();
printf(format, node->data); //遍历根结点
nodestack.pop();
if(node->rchild){
nodestack.push(node->rchild); //先将右子树压栈
}
if(node->lchild){
nodestack.push(node->lchild); //再将左子树压栈
}
}
}
广度优先搜索算法（breadth first search），又叫宽度优先搜索，或横向优先搜索。
是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
如右图所示的二叉树，a 是第一个访问的，然后顺序是 b、c，然后再是 d、e、f、g。
那么，怎样才能来保证这个访问的顺序呢？
借助队列数据结构，由于队列是先进先出的顺序，因此可以先将左子树入队，然后再将右子树入队。
这样一来，左子树结点就存在队头，可以先被访问到。
广度优先遍历代码片段
//广度优先遍历
void breadthfirstsearch(tree root){
queue<node *> nodequeue; //使用c 的stl标准模板库
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); //再将右子树入队
}
}
}
完整代码:
/**
*
*/
#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; //全局索引变量
//二叉树构造器,按先序遍历顺序构造二叉树
//无左子树或右子树用'#'表示
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); //递归构建左子树
treenodeconstructor(root->rchild, data); //递归构建右子树
}
}
//深度优先遍历
void depthfirstsearch(tree root){
stack<node *> nodestack; //使用c 的stl标准模板库
nodestack.push(root);
node *node;
while(!nodestack.empty()){
node = nodestack.top();
printf(format, node->data); //遍历根结点
nodestack.pop();
if(node->rchild){
nodestack.push(node->rchild); //先将右子树压栈
}
if(node->lchild){
nodestack.push(node->lchild); //再将左子树压栈
}
}
}
//广度优先遍历
void breadthfirstsearch(tree root){
queue<node *> nodequeue; //使用c 的stl标准模板库
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); //再将右子树入队
}
}
}
/**
*
*/
#include "binarytree.h"
int main() {
//上图所示的二叉树先序遍历序列,其中用'#'表示结点无左子树或无右子树
element data[15] = {'a', 'b', 'd', '#', '#', 'e', '#', '#', 'c', 'f','#', '#', 'g', '#', '#'};
tree tree;
treenodeconstructor(tree, data);
printf("深度优先遍历二叉树结果: ");
depthfirstsearch(tree);
printf("\n\n广度优先遍历二叉树结果: ");
breadthfirstsearch(tree);
return 0;
}
posted on 2013-02-03 12:52
fancydeepin 阅读(30927)
评论(4)