그래프 알고리즘 - (7) BST의 간단한 구현과 Tree traversal

이 글은 포스텍 오은진 교수님의 알고리즘(CSED331) 강의를 기반으로 재구성한 것입니다.

 

1. Tree

 앞선 글에서 설명했듯 Tree는 directed acyclic graph이다. 그 중 대표적인 binary search tree의 몇몇 method의 구현과, 그 순회를 살펴볼 것이다.

struct node{
    node *left, *right, *parent;
    int x;
};
 
// root node 초기화
node* initRoot(){
    node *root = new node;
    root->parent=root;
    root->left = root->right = NULL;
    root->num=rootnum; 
}
 
void insertNode(node *root, int value){
    node *parent = root;
 
    // cur node 초기화
    node *cur_node = new node;
    cur_node->x = each_node.first;
    cur_node->left = cur_node->right = NULL;
    
    while(1){
        if(cur_node->x < parent->x){ // parent보다 작으면 왼쪽으로
            if(parent->left == NULL){ // left가 비었으면 left에 값을 넣고 break;
                parent->left = cur_node;
                cur_node->parent = parent;
                break;
            } else{
                parent = parent->left; // 비지 않았으면 그것에서 다시 탐색
            }
        } else if(cur_node->x > parent->x){ // 크면 오른쪽으로
            if(parent->right == NULL){ // right가 비었으면 right에 값을 넣고 break;
               parent->right = cur_node;
               cur_node->parent=parent;
               break;
            } else{
               parent = parent->right; // 비지 않았으면 그것에서 다시 탐색
            }
        }
    }
}
 
node* search(node *cur_node, int value){
    if(root == NULL) return NULL;
    if(cur_node->x == value) return cur_node;
    else if(cur_node->x > value) return search(cur_node->left, value); // 값이 더 작으면 왼쪽으로 탐색
    else if(cur_node->x < value) return search(cur_node->right, value); // 더 크면 오른쪽으로 탐색
}

 

 

 

2. Tree Traversal

 트리 순회는 3가지 종류가 있다. preorder, inorder, postorder.

 preorder는 parent를 방문한 후 child를 방문하는 것, (parent - left child - right child)
 inorder는 left child - parent - right child 순서로 방문하는 것, 
 postorder는 child를 방문한 후 parent를 방문하는 것(left child - right child - parent)이다.

 DFS로 쉽게 구현 할 수 있고, 크게 어려운 것 없이 구현할 수 있을 것이다.

void preorder(node* cur_node){
    if(cur_node == NULL) return;
    cout<<cur_node->num<<endl;
    result.push_back(cur_node->num);
    preorder(cur_node->left, result);
    preorder(cur_node->right, result);
}
 
void inorder(node* cur_node){
    if(cur_node == NULL) return;
    inorder(cur_node->left, result);
    cout<<cur_node->num<<endl;
    inorder(cur_node->right, result);
    return;
}
 
void postorder(node* cur_node){
    if(cur_node == NULL) return;
    postorder(cur_node->left, result);
    postorder(cur_node->right, result);
    cout<<cur_node->num<<endl;
    return;
}
​