[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (2) - 노드 탐색

c언어 이진탐색트리 (Binary Search Tree) - 구현 (2) - 노드 탐색

 

[C언어 #69] 이진탐색트리 (Binary Search Tree)

[C언어 #70] 이진탐색트리 (Binary Search Tree) - 구현 (1) - 노드 생성, 노드 삽입

 

 

구현 함수 정리

#include <stdbool.h>
 
// 트리(Tree)를 구성하는 노드 구조체
struct node;
typedef struct node node;
 
// 숫자 k를 가지는 노드를 생성
node *newNode(int k);
 
// 트리의 데이터 제거 및 메모리 해제
node *freenode(node *p);
 
// 숫자 k를 가지는 노드를 트리에 삽입
node *insert(node *p, int k);
 
// 트리에서 k를 탐색
node *search(node *p, int k);
 
// k값을 가진 노드 존재 여부 확인
bool find(node *p, int k);
 
// 트리에서 최소값을 가진 노드 반환 (노드 삭제시 활용)
node *minnode(node *p);
 
// k값을 가진 노드를 트리에서 제거
node *deletenode(node *p, int k);

 

 

트리에서 숫자 k를 가진 노드를 탐색

node *search(node *p, int k) {
    if (p == NULL)     return p;
    if (k == p->value) return p;
    if (k < p->value)  return search(p->left, k);
    if (k > p->value)  return search(p->right, k);
}

 

 

k값을 가진 노드 탐색 여부 확인

bool find(node *p, int k) {
    return search(p, k) != NULL;
}

 

 

테스트 - k값을 가진 노드 탐색 테스트

void testSearch() {
    node *p = newNode(7);
    assert(find(p, 7) == true);
    p = insert(p, 3);
    assert(find(p, 3) == true);
    assert(find(p, 11) == false);
    p = insert(p, 11);
    assert(find(p, 11) == true);
    assert(find(p, 3) == true);
    assert(find(p, 7) == true);
    p = insert(p, 5);
    assert(find(p, 11) == true);
    assert(find(p, 3) == true);
    assert(find(p, 7) == true);
    assert(find(p, 5) == true);
    freenode(p);
}