[C언어 소스] 완전이진트리 순회(Complete Binary Tree Traversal)

본 예제는 트리가 Complete Binary Tree일때만 사용 할 수 있는 예제이다. Complete Binary Tree란 Level을 기준으로 최하단을 제외한 모든 노드가 두개의 자식노드를 가지면서, 최 하단 또한 좌측 순서대로 2개씩 모두 차 있는 트리를 이야기 한다. 책에서는 어떻게 정의 하는지 모르겠으나, 대충 아래의 그림을 보면 이해 할 수 있을 것이다.

트리가 완전 이진 트리일 경우 모든 노드들은 수학적인 규칙을 가진다. 레벨 순으로 1 2 3 4 5 6 이렇게 번호를 매길 경우, 

왼쪽 자식 노드 번호 = (부모 노드 번호) * 2

오른쪽 자식 노드 번호 = (부모 노드 번호) * 2 +1

이라고 할 수 있다. 이런 규칙 덕분에 실제 형태는 트리 형태이더라도 표현은 1차원 배열로 표현이 가능하다.

아래 예제는 1차원 배열 값들로 표현된 트리를 Inorder traversal한 출력값을 Print하는 예제이다.

트리가 Complete Binary Tree가 아닐 경우엔 노드간의 관계를 표현하기 위해 최소한 Structure를 사용해야 하지만 트리가 완전트리이므로 아래 예제와 같이 간단하게 표현 가능하다.

#include <stdio.h>
#include <stdlib.h>

void inorder(char *tree, int size, int i) {
	if(i*2<=size) inorder(tree, size, i*2);
	printf("%c ",tree[i]);
	if(i*2+1<=size) inorder(tree, size, i*2+1);
}
	

int main(int args, char *argv[]) {
	char *tree;
	int i, treesize;
	char temp;
	FILE *f;

	if((f=fopen(argv[1],"r"))==NULL) {
		printf("파일 입출력에 문제가 있습니다.");
		exit(1);
	}

	fscanf(f,"%d ",&treesize);
	tree=(char*)malloc(sizeof(char)*(treesize+1));

	for(i=1; i<=treesize; i++) fscanf(f,"%c ",&tree[i]);
	i=1;
	inorder(tree, treesize, i);

	free(tree);
	tree=NULL;
}

입력 값은 Space로 구분된 캐릭터 배열이다. ex) A d 2 1 d B C g x k