언제나 휴일

7.3 이진 탐색 트리 설계 및 사용 이번에는 이진 탐색 트리 설계 및 이를 사용하는 프로그램을 작성합시다. 여기에서 구현할 이진 탐색 트리는 도서 개체를 보관하고 삭제, 검색, 전체 보기를 할 수 있는 기능을 제공하기로 해요. STL에서 제공하는 map 사용하는 방법을 익히고 난 후에 다시 한 번 STL의 map을 모델로 자신의 map을 구현할 것입니다. 여기에서는 이진 탐색 트리 개념을 잡기 위해 비교적 간단하게 구현해 보아요. 프로젝트를 생성한 후에 공통으로 사용할 파일(3.1.1 참고)을 추가하세요. 그리고 여기에서 보관할 도서를 Book 클래스로 정의합시다.class Book{도서는 상수화 멤버로 도서 번호와 도서명을 멤버 필드로 추가하세요. const int bnum; string title;..

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

7. 이진 탐색 트리 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리를 살펴보기 전에 먼저 트리가 무엇인지 살펴보기로 해요. 트리는 대표적인 비선형 자료구조입니다. 비선형 자료구조는 자료를 보관하는 구조를 하나의 선의 형태로 표시할 수 없는 자료구조를 말하며 트리와 그래프 등이 있습니다. 그 중에 트리는 뿌리에서부터 계층적으로 자료를 보관하는 자료구조입니다. 트리는 방향성 있는 그래프로 표현하며 사이클이 존재하지 않고(ACycle) 고립 상태가 없는(No Island) 자료구조입니다. 트리는 다음처럼 루트와 서브 트리의 집합으로 정의할 수 있습니다.Tree = {root , sub trees} sub tre..

이진 탐색 트리 운행, C언어 소스 //이진 탐색 트리 운행#include #include typedef struct Node//노드 정의{ int data; struct Node *lchild; struct Node *rchild;}Node; typedef Node *Tree;//트리 형식명 정의 Node *NewNode(int data);//노드 생성void InitTree(Tree *bst);//트리 초기화int AddData(Tree *bst, int data); //데이터 보관void Preorder(Node *sr);//전위 순위 운행void Inorder(Node *sr);//중위 순위 운행void Postorder(Node *sr);//후위 순위 운행void ClearTree(Tree *b..