[Data Structure] Binary Search Tree 의 Traversal

 아래 주석에도 달아놓았지만 이진 트리와 이진 검색 트리는 다르다. 물론 이진 검색트리는 이진트리다. 그러나 이진트리는 반드시 이진 검색 트리라고 할 수 없다. 그 기준이 뭐냐하면 바로 내부에 있는 '값'이다.

 노드 내부의 키는 유일해야 한다. 그래야 노드간의 구별이 되기 때문이다. 또한 부모 노드의 왼쪽 서브 노드들의 값은 부모 노드의 값보다 작아야하며, 부모 노드의 오른쪽 서브 노드들의 값은 부무 노드의 값보다 커야 한다. 이러한 점을 지키면 이진 검색 트리가 된다.

 이진 검색 시에는 반복(iteration)과 순환(recursion) 방법이 있다. 언제나 그러하듯 반복은 효율이 좋고 순환은 이해가 편하다. 코드를 보자.

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

// 이진 트리와 이진 탐색 트리는 서로 정의가 다르다.
// 이진 탐색 트리는 ..
// 1. 모든 노드의 키는 유일하다
// 2. 왼쪽 서브 트리의 키들은 루트의 키보다 작다.
// 3. 오른쪽 서브 트리의 키들을 루트의 키보다 크다.
// 4. 왼쪽, 오른쪽 서브 트리도 이진 탐색 트리다.

typedef int element;
typedef struct {
    element data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// recursion
TreeNode *rec_search(TreeNode *root, element key){
    if (root == NULL) return root;
    if (key == root->data) return root;
    if (key < root->data) {
        return rec_search((TreeNode*)root->left, key);
    } else {
        return rec_search((TreeNode*)root->right, key);
    }
}

// iteration
TreeNode *iter_search(TreeNode *root, element key){
    TreeNode *p = root;
    while (p!=NULL) {
        if (key == p->data) {
            return p;
        } else if (key < p->data){
            p = (TreeNode*) p->left;
        } else {
            p = (TreeNode*) p->right;
        }
    }
    return NULL;
}

int main(){
    TreeNode n1 = {3,NULL,NULL};
    TreeNode n2 = {12,NULL,NULL};
    TreeNode n3 = {7,&n1,&n2};
    TreeNode n4 = {27,NULL,NULL};
    TreeNode n5 = {31,&n4,NULL};
    TreeNode n6 = {26,NULL,&n5};
    TreeNode n7 = {18,&n3,&n6};
    TreeNode *exp = &n7;
    
    TreeNode *rec = rec_search(exp, 18);
    TreeNode *iter = iter_search(exp, 3);

    printf("recursion : %d\n", rec->data);
    printf("iteration : %d\n", iter->data);
    
    return 0;
}