[자료구조] BST insert, inorder traversal 문제 REVIEW

 

 

 

본격적인 문제 review에 앞서,  BST(binary search tree)와 inorder traversal(중위 순회) 이 무엇인지 함께 알아보자.

 

---

 

BST (binary search tree) = 이진 탐색 트리 

: 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴.

 

* BST가 가능하려면, 왼쪽 자식의 노드보다 오른쪽 자식의 노드가 항상 크거나 같아야 한다는 전제조건이 있다.

 

 

BST INSERT

: 1. 삽입을 하기 전, 검색을 수행한다. 

  2. 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

 

---

 

 INORDER TRAVERSAL (중위 순회)

: 트리를 탐색(혹은 순회)할 때, 왼쪽 노드 => 루트 노드 => 오른쪽 노드 순으로 진행하는 방식이다.

 

---

 

 

 

우리의 문제는 BST insert를 이용하여 우리 손으로 직접 bst를 생성한 후 중위 순회를 진행하여야 하는 방식이다. 따라서 우선적으로 BST insert 과정을 진행하여야 하므로, 해당 작업에 쓰일 두 가지 함수를 먼저 보도록 하자. 아 해당 문제에 쓰인 구조체 먼저 적어두고 진행하겠다.

 

typedef struct treeNode *treePointer;

typedef struct treeNode{
int key;
treePointer right, left;
}treeNode;

 

 

구조체 포인터 treePointer를 선언하였고, 구조체 내부에는 특정 key값을 저장할 변수와 양 방향을 링킹할 포인터 두 개를두었다. 

 

 

1.

 

treePointer modifiedSearch(treePointer node, int k) {
    treePointer prev = NULL;
    treePointer cur = node;
    
    while (cur != NULL) {
        if (k == cur->key) {
            return NULL;
        }
        prev = cur;
        if (k < cur->key) {
            cur = cur->left;
        } else {
            cur = cur->right;
        }
    }
    return prev;
}

 

 

 

먼저 modifiedSearch 는 특정 키 k 값이 트리 내에 있는지 검색하는 역할의 함수다. 이미 있다면 NULL값을 반환, 기존에 없던 키 값이었다면 k 값 노드가 삽입될 위치의 부모 노드를 반환해주는 역할을 한다. 이를 통해 중복된 키 값이 트리 내에 들어가지 않도록 한다.

 

 

 

 

 

2.

 

void insert(treePointer *node, int k) {
    treePointer ptr, temp = modifiedSearch(*node, k);
    
    if (temp || !(*node)) {
        ptr = (treePointer)malloc(sizeof(*ptr));
        ptr->key = k;
        ptr->left = ptr->right = NULL;
        
        if (*node) {
            if (k < temp->key) {
                temp->left = ptr;
            } else {
                temp->right = ptr;
            }
        } else {
            *node = ptr;
        }
    }
}

 

 

insert 함수는 직접적으로 새로운 노드를 트리에 삽입해주는 함수라 볼 수 있겠다.  modifiedSearch함수를 호출하여 새로운 노드가 들어갈 위치의 부모 노드 값(혹은 NULL값)을 반환받는다. 새로운 노드는 동적 할당을 통해 생성해준 후, 노드의 값들을 알맞게 초기화시키고, 부모 노드보다 key값이 큰지 작은지에 따라 그에 알맞는 자리에 삽입되도록 한다.

 

 

 

---

 

 

 

다음으로는 중위 순회를 진행할 함수를 살펴보도록 하자.

 

void Inorder_traversal(treePointer node) {
    treePointer temp = node;

    if (temp != NULL) {
        Inorder_traversal(temp->left);
        printf("%d ", temp->key);
        Inorder_traversal(temp->right);
    }
}

 

 

이 코드는 처음에는 조금 눈으로 보기 난해할 수 있다. 재귀적으로 왼쪽 노드 - 루트 노드 - 오른쪽 노드를 훑어가는 과정인데, 그래도 말로 조금이나마 풀어보자면

 

1. Inorder_traversal(temp->left); 를 통해 재귀적으로 해당 트리의 가장 왼쪽 밑단까지 내려간다.

2. NULL이 되기 직전 노드였을, 가장 왼쪽 밑단노드를 print한다.

3. 왼쪽 밑단 노드의 오른쪽 자식도 NULL일 테므로, 한 칸 올라가 부모 노드를 print 한다.

4. 해당 부모 노드의 오른쪽 자식 노드도 위와 같은 메커니즘에 따라 print가 수행된다.

5. 이렇게 가장 왼쪽 밑단에서 차례대로 올라가며 print가 수행될 것이다.  

 

 

 

 

 

 

---

 

전체 정답 코드

 

#include <stdio.h>
#include <stdlib.h>


typedef struct treeNode *treePointer;

typedef struct treeNode{
    int key;
    treePointer right, left; 
}treeNode;


treePointer insert(treePointer *node, int k) {
    treePointer *curr = node;
    while (*curr != NULL) {
        if (k < (*curr)->key) {
            curr = &(*curr)->left;
        } else {
            curr = &(*curr)->right;
        }
    }

    treePointer new_node = (treePointer)malloc(sizeof(*new_node));
    new_node->key = k;
    new_node->left = new_node->right = NULL;
    *curr = new_node;
    return new_node;
}

void Inorder_traversal(treePointer node)
 {
    treePointer temp=node;

    if(temp!=NULL)
    {
    Inorder_traversal(temp->left);
    printf("%d ",temp->key);
    Inorder_traversal(temp->right); 
    }
 }


void findmax(treePointer node)
{
    treePointer temp=node;

    while(temp->right!=NULL)
    {
        temp=temp->right;
    }

    int x= temp->key;
    printf("\n%d",x);
}



int main()
{

    FILE *f=fopen("in.txt","r");

    int n=0;
    int k=0;

    treePointer node=NULL;

    fscanf(f,"%d",&n);
    for(int i=0;i<n;i++)
    {
        fscanf(f,"%d",&k);
        insert(&node,k);
    }

    fclose(f);

    Inorder_traversal(node);
    findmax(node);


    return 0;
}