深度优先搜索(DFS)和广度优先搜索(BFS)

yxjoey posted @ 2008年3月28日 09:15 in C语言 with tags c 程序 , 4451 阅读

简单来说

深度优先搜索用递归实现

输出当前结点
对于当前结点的所有子结点，依次递归运用深度优先搜索

广度优先搜索用队列实现

将起始结点入队列
循环(队列非空)
- 取出一个结点
- 输出结点内容
- 将此结点的所有子结点入队列

代码：

#include <stdio.h>
#include <stdlib.h>
 
struct Node{
  int value;
  struct Node *left; 
  struct Node *right;
};
 
struct qNode{
  struct Node *value;
  struct qNode *next;
};
 
struct Node *constructTree(int a[], int n){
  struct Node *nodes = (struct Node *)malloc(n*sizeof(struct Node));
  int i;
  for(i=0; i<n; i++){
    nodes[i].value = a[i] ;
    nodes[i].left = (2*i+1<n)?&nodes[2*i+1]:NULL;
    nodes[i].right = (2*i+2<n)?&nodes[2*i+2]:NULL;
  }
  return nodes;
}
 
void dfs(struct Node *p){
  printf("%d ", p->value);
  if(p->left!=NULL)
    dfs(p->left);
  if(p->right!=NULL)
    dfs(p->right);
}
 
struct qNode* createqueue(){
  struct qNode *p = (struct qNode*)malloc(sizeof(struct qNode));
  p->value = NULL;
  p->next = NULL;
  return p;
}
 
int isEmpty(struct qNode *queue){
  return queue->next==NULL;
}
 
void enqueue(struct qNode *queue, struct Node *node){
  struct qNode *p = (struct qNode*)malloc(sizeof(struct qNode));
  struct qNode *q = queue->next;
  p->value = node;
  p->next = q;
  queue->next = p;
}
 
struct Node* dequeue(struct qNode *queue){
  if(isEmpty(queue))
    return NULL;
  struct qNode *p=queue,*q;
  while(p->next!=NULL){
    q = p;
    p = p->next;
  }
  q->next =NULL;
  return p->value;
}
 
void bfs(struct Node *p){
  struct qNode *queue = createqueue();
  enqueue(queue, p);
  while(!isEmpty(queue)){
    struct Node *tmp = dequeue(queue);
    printf("%d ", tmp->value);
    if(tmp->left!=NULL)
      enqueue(queue, tmp->left);
    if(tmp->right!=NULL)
      enqueue(queue, tmp->right);
  }
}
 
int main(int argc, char *argv[]){
  int a[]={1,2,3,4,5,6,7,8,9,10};
  struct Node *p = constructTree(a, sizeof(a)/sizeof(a[0]));
  dfs(p);
  printf("\n==================\n"); 
  bfs(p);
  printf("\n==================\n");
}