이진탐색트리 삽입(반복, 재귀) - C로 구현

반복(Iterative search) 으로 구현

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

// 트리 노드 정의
typedef struct treeNode {
    int key;
    struct treeNode* leftChild;
    struct treeNode* rightChild;
} treeNode, * treePointer;

// modifiedSearch 함수 정의
treePointer modifiedSearch(treePointer root, int k) {
    treePointer p = root;
    treePointer lastExamined = NULL; // 마지막으로 탐색한 노드를 저장할 변수

    while (p != NULL) {
        lastExamined = p; // 현재 노드를 lastExamined에 저장

        if (k < p->key) // k가 key보다 작으면
            p = p->leftChild; // 왼쪽 서브트리로 이동
        else if (k > p->key) // k가 key보다 크면
            p = p->rightChild; // 오른쪽 서브트리로 이동
        else // k가 key와 같으면
            return NULL; // NULL 반환 (값이 이미 존재)
    }

    return lastExamined; // 마지막으로 탐색한 노드 반환
}

// insert 함수 정의
void insert(treePointer* node, int k) {
    /* if k is in the tree pointed at by node do nothing;
       otherwise add a new node with data = k */
    treePointer ptr;
    /* searches the binary search tree *node for the key k */
    treePointer temp = modifiedSearch(*node, k);
    if (temp || !(*node)) {
        /* k is not in the tree */
        ptr = (treePointer)malloc(sizeof(treeNode));
        if (ptr == NULL) {
            fprintf(stderr, "메모리 할당 실패\n");
            exit(1);
        }
        ptr->key = k;
        ptr->leftChild = ptr->rightChild = NULL;

        if (*node) { /* insert as child of temp */
            if (k < temp->key)
                temp->leftChild = ptr;
            else
                temp->rightChild = ptr;
        }
        else
            *node = ptr;
    }
    else {
        printf("같은 값 존재\n");
    }
}

// 이진 탐색 트리의 중위 순회(inorder traversal) 함수
void inorderTraversal(treePointer root) {
    if (root != NULL) {
        inorderTraversal(root->leftChild);
        printf("%d ", root->key);
        inorderTraversal(root->rightChild);
    }
}

int main() {
    treePointer root = NULL;

    // 7, 3, 8, 1, 5의 값을 갖는 이진 탐색 트리 생성
    insert(&root, 7);
    insert(&root, 3);
    insert(&root, 8);
    insert(&root, 1);
    insert(&root, 5);

    printf("이진 탐색 트리 중위 순회 결과: ");
    inorderTraversal(root);
    printf("\n");

    // 값 6을 이진 탐색 트리에 삽입
    insert(&root, 6);

    printf("6을 삽입한 후 이진 탐색 트리 중위 순회 결과: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

 

재귀로 구현

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

// 트리 노드 정의
typedef struct treeNode {
    int key;
    struct treeNode* leftChild;
    struct treeNode* rightChild;
} treeNode, *treePointer;

// 재귀적으로 노드를 삽입하는 함수
treePointer insertNode(treePointer root, int key) {
    // 기저 조건: 트리가 비어 있으면 새 노드를 반환
    if (root == NULL) {
        treePointer newNode = (treePointer)malloc(sizeof(treeNode));
        if (newNode == NULL) {
            fprintf(stderr, "메모리 할당 실패\n");
            exit(1);
        }
        newNode->key = key;
        newNode->leftChild = newNode->rightChild = NULL;
        return newNode;
    }

    // 재귀적으로 왼쪽 또는 오른쪽 서브트리에 삽입
    if (key < root->key)
        root->leftChild = insertNode(root->leftChild, key);
    else if (key > root->key)
        root->rightChild = insertNode(root->rightChild, key);
    else
        printf("같은 값 존재\n");

    return root;
}

// 이진 탐색 트리의 중위 순회(inorder traversal) 함수
void inorderTraversal(treePointer root) {
    if (root != NULL) {
        inorderTraversal(root->leftChild);
        printf("%d ", root->key);
        inorderTraversal(root->rightChild);
    }
}

int main() {
    treePointer root = NULL;

    // 7, 3, 8, 1, 5의 값을 갖는 이진 탐색 트리 생성
    root = insertNode(root, 7);
    root = insertNode(root, 3);
    root = insertNode(root, 8);
    root = insertNode(root, 1);
    root = insertNode(root, 5);

    printf("이진 탐색 트리 중위 순회 결과: ");
    inorderTraversal(root);
    printf("\n");

    // 값 6을 이진 탐색 트리에 삽입
    root = insertNode(root, 6);

    printf("6을 삽입한 후 이진 탐색 트리 중위 순회 결과: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}