hyelie
hyelie
Hyeil Jeong
       
글쓰기    관리    수식입력
  • 전체보기 (495)
    • PS (283)
      • Algorithm (28)
      • PS Log (244)
      • Contest (6)
      • Tips (5)
    • Development (52)
      • Java (14)
      • Spring (23)
      • SQL (2)
      • Node.js (2)
      • Socket.io (3)
      • Study (4)
      • Utils (4)
    • DevOps (36)
      • Git (5)
      • Docker (4)
      • Kubernetes (2)
      • GCP (3)
      • Environment Set Up (8)
      • Tutorial (12)
      • Figma (2)
    • CS (74)
      • OOP (7)
      • OS (24)
      • DB (2)
      • Network (24)
      • Architecture (0)
      • Security (2)
      • Software Design (0)
      • Parallel Computing (15)
    • Project (15)
      • Project N2T (5)
      • Project ASG (0)
      • Project Meerkat (1)
      • Model Checking (7)
      • Ideas (2)
    • 내가 하고싶은 것! (34)
      • Plan (16)
      • Software Maestro (10)
      • 취준 (8)
hELLO · Designed By 정상우.
hyelie

hyelie

PS/Algorithm

그래프 알고리즘 - (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;
}
​

'PS > Algorithm' 카테고리의 다른 글

좌표 압축  (0) 2022.06.28
정렬 ***TODO  (0) 2022.06.27
그래프 알고리즘 - (6) 위상 정렬 Topological sort  (0) 2022.06.22
그래프 알고리즘 - (5) Minimum Spanning Tree(Kruskal, Prim)  (0) 2022.06.22
그래프 알고리즘 - (4) Union-find(disjoint set)  (0) 2022.06.22
    hyelie
    hyelie

    티스토리툴바