IT용어위키



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

1. 개요

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

2. 설명

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

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


3. C언어

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 void inorder(char *tree, int size, int i) {
 5 	if(i*2<=size) inorder(tree, size, i*2);
 6 	printf("%c ",tree[i]);
 7 	if(i*2+1<=size) inorder(tree, size, i*2+1);
 8 }
 9 	
10 
11 int main(int args, char *argv[]) {
12 	char *tree;
13 	int i, treesize;
14 	char temp;
15 	FILE *f;
16 
17 	if((f=fopen(argv[1],"r"))==NULL) {
18 		printf("파일 입출력에 문제가 있습니다.");
19 		exit(1);
20 	}
21 
22 	fscanf(f,"%d ",&treesize);
23 	tree=(char*)malloc(sizeof(char)*(treesize+1));
24 
25 	for(i=1; i<=treesize; i++) fscanf(f,"%c ",&tree[i]);
26 	i=1;
27 	inorder(tree, treesize, i);
28 
29 	free(tree);
30 	tree=NULL;
31 }

  출처: 공대위키(공대위키에서 최신 문서 보기)
  * 본 페이지는 공대위키에서 미러링된 페이지입니다. 일부 오류나 표현의 누락이 있을 수 있습니다. 원본 문서는 공대위키에서 확인하세요!