[C++]이진탐색트리의 생성 및 탐색 및 출력

소개글

[C++]이진탐색트리의 생성 및 탐색 및 출력에 대한 보고서 자료입니다.

본문내용

Ⅰ. 이진탐색트리의 생성 및 노드 삽입
1. 이진탐색트리의 정의
이진탐색트리는 이진 트리로서 공백이 가능하다. 만약 공백이 아니라면 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않으며, 왼쪽 서브트리에는 루트보다 작은 키가, 오른쪽 서브트리에는 루트보다 큰 키가 위치하는 트리이다.
2. 이진탐색트리의 노드
이진탐색트리는 이진트리를 기반으로 하므로 키 및 왼쪽/오른쪽 자식의 노드를 갖는다. 따라서 이를 클래스로 나타내면 아래와 같다.
class TreeNode{ // 이진탐색 트리의 노드 클래스
friend class BST;
private:
int nData;
TreeNode *pLeftChild;
TreeNode *pRightChild;
};
위 클래스에서 nData는 키를 나타내며, pLeftChild 및 pRightChild는 왼쪽/오른쪽 자식의 포인터이다. 이러한 노드구조를 이용하여 아래와 같은 BST 클래스를 통해 이진탐색트리의 각 작업을 수행한다.
class BST{ // 이진탐색트리의 작업을 수행하는 클래스
private:
int buff[MaxBuffSize][MaxBuffSize]; // 트리를 그리기 위한 배열
TreeNode *m_pRoot; // 루트 포인터
TreeNode *m_pCurrent; // 현재 노드
};
위 클래스에서 m_pRoot는 이진탐색트리의 루트노드를 유지할 포인터이며, m_pCurrent를 현재 포인터의 위치를 유지할 변수이다.

키워드

이진탐색트리,   이진탐색,   BST,   이진트리그리기,   이진트리,   이진트리구성,   자료구조