|
Ⅰ. 이진탐색트리의 생성 및 노드 삽입
1. 이진탐색트리의 정의
이진탐색트리는 이진 트리로서 공백이 가능하다. 만약 공백이 아니라면 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않으며, 왼쪽 서브트리에는 루트보다 작은
|
|
|
|
typedef struct entry{ // 트리의 노드로 쓰일 구조체
int id;
char name[10];
char value;
}element;
element *BST[MAXSIZE+1]; // 이진탐색트리의 선언
void initSet_BST(){
int i = 0;
for(; i <= MAXSIZE; i++) { BST[i] = (element *)malloc(sizeof(element)); BST[i] = 0; }
} // 이진탐색트
|
|
|
|
program BSTree;
uses
Crt;
const
MAXSIZE = 100; (*트리의 사이즈*)
type
element = record (*트리의 노드로 쓰일 레코드*)
id : integer;
name : string[10];
value : char;
end;
Tree = array[1..100] of element;
var
BST : Tree; (*이진탐색트리가 될 전역 변수 선언*)
select : inte
|
|
|
재귀함수
if(T->rchild!=NULL)//만약 오른쪽 노드가 비어 있지않다면
mirror(T->rchild);//오른쪽노드에 대한 재귀함수
}
}
int isBST(Nptr T)//이 트리가 이진탐색트리인지 알아보는 함수
{
if(T == NULL)//만약 노드가 비어 있다면
return 1;//1을 리턴
if((T-&g
|
|
|
|
이진탐색 호출
bsum=bsum+count;
if(e==1)
printf(" 이진탐색 성공: index= %d, 비교횟수: %d\n", index, count);
else
printf(" 이진탐색 실패: 비교횟수
|
|
 |
이진탐색트리로 자식노드가 최대 2개인 트리로 왼쪽 자식노드가 부모 노드가 가진 값보다 작고 오른쪽 자식노드가 부모노드가 가진 값보다 큰 조건을 만족하는 이진트리 구조
balanced tree일때는 logN(탐색할때 마다 데이터양이 1/2씩 감소하기
|
|
메뉴펼치기
