[C/C++] DFS/BFS 구현

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;
}