언제나 휴일

[C언어 알고리즘] 3.4.4 이진 탐색 트리 소스 코드 테스트 로직을 구현합시다. 테스트 로직은 단순히 이진 탐색 트리를 생성한 후에 다양한 도서 정보를 추가하고 검색과 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 것입니다. 이 부분에 관한 별도의 설명은 생략할게요. //common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_..

[C언어 알고리즘] 3.4.3 이진 탐색 트리 구현 이제 이진 탐색 트리를 구현합시다. 이진 탐색 트리는 자료를 보관하는 컬렉션 중에 탐색 효율성을 높인 자료구조입니다. 여기에서는 도서를 보관하는 이진 탐색 트리를 구현하기로 할게요. 먼저 노드를 정의합시다. 이진 탐색 트리의 노드는 데이터와 왼쪽 자식 노드의 위치, 오른쪽 자식 노드의 위치로 구성합니다. 이 책에서는 삭제 편의성을 위해 부모 노드의 위치도 포함할게요. 그리고 동적으로 노드를 생성하는 함수를 제공합시다. typedef struct _Node Node; struct _Node { Book *book; Node *lch; Node *rch; Node *pa; }; Node *New_Node(Book *data); 이진 탐색 트리에는 root ..

[C언어 알고리즘] 3.4.2 이진 탐색 트리(Binary Search Tree)이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리(Binary Search Tree)를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 이진 트리입니다. 이진 탐색 트리에서는 자료를 보관할 때 부모보다 작은 값을 갖는 자료는 부모의 왼쪽 서브 트리에 매달고 큰 값을 갖는 자료는 부모의 오른쪽 서브 트리에 매다는 이진 트리입니다. 그리고 이진 탐색 트리에서는 같은 값을 갖는 자료는 보관하지 않습니다. 이처럼 매달면 서브 트리도 이진 탐색 트리인 특징을 갖습니다. binary search tree = { root, sub trees} sub tree is binary search tree, left son’ s..

[C언어 자료구조] 6.3 이진 탐색 트리 소스 코드 테스트 로직을 구현합시다. 테스트 로직은 단순히 이진 탐색 트리를 생성한 후에 다양한 도서 정보를 추가하고 검색과 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 것입니다. 이 부분에 관한 별도의 설명은 생략할게요. //common.h #pragma once //헤더 파일을 한 번만 포함해서 컴파일 #include #include #include #include #include #include #include #pragma warning(disable:4996) //4996컴파일 경고 메시지 출력 해제 //Book.h #pragma once #include "common.h" #define MAX_TIT_LEN 200 #define MAX_AUT_LE..

[C언어 자료구조] 6.2 이진 탐색 트리 구현 동적으로 노드를 생성하는 함수를 구현합시다. 여기에서는 Node 형식 크기의 메모리를 할당받은 후 입력 인자로 받은 도서 정보를 설정하고 나머지 멤버는 0으로 초기화합니다. Node *New_Node(Book *data) { Node *node = 0; node = (Node *)malloc(sizeof(Node)); node->book = data; node->lch = node->rch = node->pa = 0; return node; } 동적으로 이진 탐색 트리를 생성하는 함수를 구현합시다. 생성할 때 root는 비어있는 상태이고 보관하고 있는 도서 개수는 0입니다. BST *New_BST() { BST *bst = 0; bst = (BST *)ma..

[C언어 자료구조] 6.1 이진 탐색 트리 설계 이제 이진 탐색 트리를 설계합시다. 이진 탐색 트리는 자료를 보관하는 컬렉션 중에 탐색 효율성을 높인 자료구조입니다. 여기에서는 도서를 보관하는 이진 탐색 트리를 구현하기로 할게요. 먼저 노드를 정의합시다. 이진 탐색 트리의 노드는 데이터와 왼쪽 자식 노드의 위치, 오른쪽 자식 노드의 위치로 구성합니다. 이 책에서는 삭제 편의성을 위해 부모 노드의 위치도 포함할게요. 그리고 동적으로 노드를 생성하는 함수를 제공합시다. typedef struct _Node Node; struct _Node { Book *book; Node *lch; Node *rch; Node *pa; }; Node *New_Node(Book *data); 이진 탐색 트리에는 root 노드..

[C언어 자료구조] 6. 이진 탐색 트리(Binary Search Tree) 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리는 노드와 서브 트리의 집합으로 서브 트리도 이진 탐색 트리입니다. 그리고 부모 노드는 두 개의 자식 노드를 가질 수 있고 왼쪽 서브 트리에는 부모보다 작은 값들이 오른쪽 서브 트리에는 부모보다 큰 값들이 있습니다. [그림 6.1] 이진 탐색 트리 이진 탐색 트리에서 데이터를 추가하거나 검색할 때 재귀적인 방법으로 찾을 수 있습니다. 검색 (key:키, sroot: 서브 트리의 루트노드) rkey:= sroot.key gap: = rkey - key 조건(gap IsEqual 0) sr..

3.4.2 이진 탐색 트리 코드 테스트 로직을 구현합시다. 테스트 로직은 단순히 이진 탐색 트리를 생성한 후에 다양한 도서 정보를 추가하고 검색과 삭제 기능 등을 호출하여 잘 동작하는지 확인하는 것입니다. 이 부분에 관한 별도의 설명은 생략할게요. ▷BinSearchTree.h#pragma once #include "Book.h"typedef struct _Node Node;struct _Node{ Book *book; Node *lch; Node *rch; Node *pa;}; Node *New_Node(Book *data);typedef struct _BinSearchTree BST;struct _BinSearchTree{ Node *root; int count;};BST *New_BST();void..

3. 4 이진 탐색 트리 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리는 노드와 서브 트리의 집합으로 서브 트리도 이진 탐색 트리입니다. 그리고 부모 노드는 두 개의 자식 노드를 가질 수 있고 왼쪽 서브 트리에는 부모보다 작은 값들이 오른쪽 서브 트리에는 부모보다 큰 값들이 있습니다. [그림 3.7] 이진 탐색 트리 이진 탐색 트리에서 데이터를 추가하거나 검색할 때 재귀적인 방법으로 찾을 수 있습니다. 검색 (key:키, sroot: 서브 트리의 루트노드) rkey:= sroot.key gap: = rkey - key 조건(gap IsEqual 0) sroot 반환 조건(gap < 0) 조건(sroot의 ..

7.4 이진 탐색 트리 구현이제 앞에서 설계한 이진 탐색 트리를 구체적으로 구현합시다. 먼저 이진 탐색 트리의 추가 기능인 AddBook 메서드를 구현하기로 해요.bool BinSearchTree::AddBook(int bnum,string title){먼저 주요 키인 도서 번호로 부모 노드를 검색하기로 해요. Node *parent = Find(root,bnum); if(parent) {검색한 부모의 키가 입력한 도서 번호와 일치하였는지 확인하세요. Book *sbook = parent->book; if(sbook->GetBNum() == bnum) {일치하면 도서를 보관하지 않고 추가 실패를 반환하세요. return false; } }입력받은 인자로 도서 개체를 생성하세요. Book *book = n..