[자료구조] 이진 트리의 구현

이진 트리의 구현, 표현 방법에는 배열을 이용한 방법과 연결리스트를 이용한 방법이 있습니다.

배열을 이용한 이진 트리의 구현

배열을 이용한 방법은 모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법입니다.

 

어떤 노드를 n이라고 할 때,

n의 부모 노드의 인덱스(index)는 n/2

n의 왼쪽 자식 노드의 인덱스는 2n

n의 오른쪽 자식 노드의 인덱스는 2n + 1 입니다.

 

위 그림에서 c노드의 배열 인덱스를 찾기 위해서는 i의 인덱스를 1이라고 할 때, 순차적으로 계산하면 됩니다.

f의 인덱스 == (1 * 2), a의 인덱스 == (2 * 2), b의 인덱스 == (4 * 2 + 1), e의 인덱스 == (9 * 2 + 1), d의 인덱스 == (19 * 2), 마지막 c의 인덱스 == (38 * 2) == 76 이되는 것입니다.

 

 

 

포인터를 이용한 이진 트리의 구현

이중 연결리스트의 노드 포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법입니다. 자식 노드를 노드 포인터로 생성하고 자식 노드가 없는 경우는 null로 표기합니다.

 

기본 알고리즘

#include <stdio.h>

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
} TreeNode;

void  main()
{
	TreeNode* n1, * n2, * n3;

	n1 = (TreeNode*)malloc(sizeof(TreeNode));
	n2 = (TreeNode*)malloc(sizeof(TreeNode));
	n3 = (TreeNode*)malloc(sizeof(TreeNode));
	n1->data = 10;	// 첫 번째 노드
	n1->left = n2;
	n1->right = n3;
	n2->data = 20;	// 두 번째 노드
	n2->left = NULL;
	n2->right = NULL;
	n3->data = 30;	// 세 번째 노드
	n3->left = NULL;
	n3->right = NULL;
	free(n1); free(n2); free(n3);
	return 0;
}

위 이진 트리의 기본 구조는 n1을 루트 노드로써 데이터 10을 저장하고 n1의 왼쪽 자식 노드인 n2와 오른쪽 자식 노드인 n3를 연결합니다. n2의 데이터에 20을 저장하고 n2의 자식 노드는 모두 null로 지정하며, n3의 데이터에 30을 저장하고 n3의 자식노드는 모두 null로 지정합니다.