Programming/Code
[C/C++] DFS/BFS 구현
MIN JOON
2019. 4. 24. 21:20
DFS(깊이 우선탐색)
- preorder
- inorder
- postorder
BFS(너비 우선탐색)
struct Node{
int data;
Node* left;
Node* right;
};
Node* insert(Node* root ,int data){
if(root == nullptr)
{
root = new Node();
root->data = data;
root->left = root->right = nullptr;
}
else if( data <= root->data)
{
root->left = insert(root->left, data);
}
else
{
root->right = insert(root->right, data);
}
return root;
}
void dfs_pre(Node* root)
{
if(root == nullptr)
{
return;
}
Node* c = root;
printf("%d ",c->data);
dfs_pre(root->left);
dfs_pre(root->right);
}
void dfs_post(Node* root)
{
if(root == nullptr)
{
return;
}
Node* c = root;
dfs_post(root->left);
dfs_post(root->right);
printf("%d ",c->data);
}
void dfs_in(Node* root)
{
if(root == nullptr)
{
return;
}
Node* c = root;
dfs_in(root->left);
printf("%d ",c->data);
dfs_in(root->right);
}
Node* Q[50];
int front,tail;
void push(Node* c)
{
Q[tail++] = c;
}
void pop()
{
front++;
}
bool isEmpty()
{
return front == tail ? true : false;
}
Node* getFront()
{
return Q[front];
}
void bfs(Node* root)
{
front = tail = 0;
if(root == nullptr)
{
return;
}
push(root);
while(!isEmpty())
{
Node* c = getFront();
printf("%d ",c->data);
if(c->left != nullptr) push(c->left);
if(c->right != nullptr)push(c->right);
pop();
}
}
Node* root;
int main(int argc, const char * argv[]) {
root = nullptr;
root = insert(root, 15);
root = insert(root, 20);
root = insert(root, 4);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 29);
printf("preorder\n");
dfs_pre(root);
printf("\n");
printf("postorder\n");
dfs_post(root);
printf("\n");
printf("inorder\n");
dfs_in(root);
printf("\n");
printf("bfs\n");
bfs(root);
printf("\n");
return 0;
}