分享：non-recursive breadth first search and depth first search algorithm in C# JobHunting - 待字闺中
f*y
1 楼
I am preparing algorithm, wrote the following algorithm. Share with you. Not
sure whether it is a duplicate post or not.
//---- Breadth Fast Search algorithm ---
// circular queue
int head = 0;
int tail = 0;
#define Q_EMPTY (head==tail)
#define Q_FULL ((tail-head+1)%SIZE==0)
#define SIZE 10
struct Node* q[SIZE];
void put(struct Node* x)
{
if (x==NULL) return;
if (Q_FULL) return; //queue full
q[tail] = x;
tail = (tail+1) % SIZE;
return;
}
struct Node* get()
{
if (Q_EMPTY) return NULL;
head %= SIZE;
return q[head++];
}
// breadth first search
void bfs(struct Node* root)
{
struct Node* n;
printf("breadth first search of tree:\t");
// get the ball rolling..
put(root);
while ( n=get()) {
// visit each node in queue
printf("%d ",n->i);
// push children to queue
put(n->left);
put(n->right);
}
printf("\n");
}
// push down stack
int top=0;
void push(struct Node* x)
{
if (x==NULL) return;
if (top
struct Node* pop()
{
if (top>0) return q[--top];
else return NULL;
}
// --- depth first search ---
void dfs(struct Node* root)
{
struct Node* n;
printf("depth first search of tree:\t");
// get the ball rolling..
push(root);
while ( n=pop()) {
// visit each node in stack
printf("%d ",n->i);
// push children to stack
push(n->right);
push(n->left);
}
printf("\n");
}
sure whether it is a duplicate post or not.
//---- Breadth Fast Search algorithm ---
// circular queue
int head = 0;
int tail = 0;
#define Q_EMPTY (head==tail)
#define Q_FULL ((tail-head+1)%SIZE==0)
#define SIZE 10
struct Node* q[SIZE];
void put(struct Node* x)
{
if (x==NULL) return;
if (Q_FULL) return; //queue full
q[tail] = x;
tail = (tail+1) % SIZE;
return;
}
struct Node* get()
{
if (Q_EMPTY) return NULL;
head %= SIZE;
return q[head++];
}
// breadth first search
void bfs(struct Node* root)
{
struct Node* n;
printf("breadth first search of tree:\t");
// get the ball rolling..
put(root);
while ( n=get()) {
// visit each node in queue
printf("%d ",n->i);
// push children to queue
put(n->left);
put(n->right);
}
printf("\n");
}
// push down stack
int top=0;
void push(struct Node* x)
{
if (x==NULL) return;
if (top
struct Node* pop()
{
if (top>0) return q[--top];
else return NULL;
}
// --- depth first search ---
void dfs(struct Node* root)
{
struct Node* n;
printf("depth first search of tree:\t");
// get the ball rolling..
push(root);
while ( n=pop()) {
// visit each node in stack
printf("%d ",n->i);
// push children to stack
push(n->right);
push(n->left);
}
printf("\n");
}
