[PASCAL] 배열을 이용한 이진탐색트리 삽입, 삭제, 탐색 프로그램

소개

파스칼로 구현한 배열이진탐색트리 프로그램

이진탐색트리는 부모노드를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치하는 형식의 자료구조이다. 따라서 탐색은 루트노드를 시작으로 하여 그 크기 비교를 통해 어느 자식으로 이동할 지를 결정하여 이루어진다. 이번 프로그램에서는 배열로 트리가 구현되어 있으므로 인덱스 1을 시작으로 탐색하는 레코드의 값이 작은 경우는 현재 인덱스에 2를 곱하고, 큰 경우는 2를 곱한 후 1을 더해 탐색을 수행한다. 각 노드의 비교 기준은 ID 값이 되며, ID는 integer type으로서 단순한 비교로 그 크기를 결정할 수 있을 것이다.

2) 탐색 연산은 search, isMember 함수가 담당한다. search는 탐색할 데이터를 입력받는 역할만을 하며, 실제로 탐색이 수행되는 함수는 isMember다. 여기서는 탐색이 성공하든 실패하든 마지막으로 종료한 인덱스를 반환하게 되는데, 이는 다른 함수에서도 이용할 수 있도록 하기 위해 결정된 것이다. 따라서 반환된 인덱스가 트리의 크기를 넘어서거나, 그 위치에 데이터가 없는 경우는 탐색이 실패한 것이고, 존재하는 경우라도 NAME, VALUE 값이 다른 경우는 탐색 실패로 처리된다.


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 : integer;

procedure initSet_set(); (*이진탐색트리 초기화*)
var
i : integer;
begin
for i := 1 to MAXSIZE do
begin
BST[i].id := 0;
end; (*end of for*)
end;

Function Get_Element(var a : element) : element;
(*이진탐색트리의 노드를 구성하는 구조체의 정보를 입력받는 함수*)
begin
Writeln('Input ID : '); (*id를 입력 받음*)
Read(a.id); Readln;
Writeln('Input NAME : '); (*name을 입력받음*)
Readln(a.name);
Writeln('Input VALUE : '); (*value를 입력받음*)
Readln(a.value);
Get_Element := a;
end;

Function isMember(var a : element) : integer;
(*파라미터로 받은 노드가 현재 이진탐색트리에 존재하는지 탐색하
여 그 결과를 반환하여 준다. 반환되는 값은 탐색이 종료된 트리상의
위치이며, 이를 이용하여 여러가지 작업을 할 수 있게 하기 위함이다.*)
var
cnt : integer;
done : boolean;
begin
cnt := 1;
done := true;

컴파일 실행환경

pascal, delphi

참고자료

· 없음