[C언어 자료구조] 6.1 이진 탐색 트리 설계

[C언어 자료구조] 6.1 이진 탐색 트리 설계

---

 이제 이진 탐색 트리를 설계합시다. 이진 탐색 트리는 자료를 보관하는 컬렉션 중에 탐색 효율성을 높인 자료구조입니다. 여기에서는 도서를 보관하는 이진 탐색 트리를 구현하기로 할게요.

 

 먼저 노드를 정의합시다. 이진 탐색 트리의 노드는 데이터와 왼쪽 자식 노드의 위치, 오른쪽 자식 노드의 위치로 구성합니다. 이 책에서는 삭제 편의성을 위해 부모 노드의 위치도 포함할게요. 그리고 동적으로 노드를 생성하는 함수를 제공합시다.

typedef struct _Node Node;

struct _Node

{

    Book *book;

    Node *lch;

    Node *rch;

    Node *pa;

};

Node *New_Node(Book *data);

 

 이진 탐색 트리에는 root 노드의 위치 정보와 보관한 데이터의 개수를 멤버로 구성할게요.

typedef struct _BinSearchTree BST;

struct _BinSearchTree

{

    Node *root;

    int count;

};

 

 이진 탐색 트리를 동적으로 생성하는 함수와 소멸하는 함수를 제공합시다. 그리고 이진 탐색 트리에 책을 보관하는 함수, 특정 번호의 도서를 제거하는 함수, 특정 번호의 도서를 검색하는 함수와 전체 도서 목록을 보여주는 함수를 제공합시다.

BST *New_BST();

void Delete_BST(BST *bst);

int BST_Insert(BST *bst,Book *book);

int BST_Remove(BST *bst, int num);

Book *BST_Find(BST *bst, int num);

void BST_List(BST *bst);