완전이진트리순회 소스코드

개요

• 트리가 Complete Binary Tree일때만 사용 할 수 있는 예제이다.

설명

• 트리가 완전 이진 트리일 경우 모든 노드들은 수학적인 규칙을 가진다. 레벨 순으로 1 2 3 4 5 6 이렇게 번호를 매길 경우
  • 왼쪽 자식 노드 번호 = (부모 노드 번호) * 2
  • 오른쪽 자식 노드 번호 = (부모 노드 번호) * 2 +1
• 라고 할 수 있다. 이런 규칙 덕분에 실제 형태는 트리 형태이더라도 표현은 1차원 배열로 표현이 가능하다.

---

• 아래 예제는 1차원 배열 값들로 표현된 트리를 Inorder traversal한 출력값을 Print하는 예제이다.
• 트리가 Complete Binary Tree가 아닐 경우엔 노드간의 관계를 표현하기 위해 최소한 Structure를 사용해야 하지만 트리가 완전트리이므로 아래 예제와 같이 간단하게 표현 가능하다.

C언어

#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;
}

• 출처 블로그(지식잡식)