카테고리 없음
이진탐색트리 삽입(반복, 재귀) - C로 구현
진강이
2024. 5. 21. 00:24
반복(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;
}