이진 트리의 표현

이진 트리를 컴퓨터 프로그램 내에서 표현하려면

1. 배열을 이용하는 방법
2. 포인터를 이용하는 방법

위 2가지 방법을 사용할 수 있음

---

배열 표현법

- 주로 포화 이진 트리나 완전 이진 트리에서 자주 사용(그 외 이진 트리에서도 사용 가능)

- 저장하고자 하는 이진 트리를 완전 이진 트리라 가정, 이진 트리의 깊이가 k이면 최대 2ᵏ-1개의 공간을 연속적으로 할당한 다음 완전 이진 트리의 번호대로 노드들을 저장

- 이때 인덱스 0은 사용되지 않음

- 완전 이진 트리가 아닌 일반적인 이진 트리의 경우, 배열 표현법으로 표현하면 기억공간의 낭비 有

- 부모와 자식 인덱스 간 아래와 같은 공식 성립

- 노드 i의 부모 노드 인덱스 = i/2 - 노드 i의 왼쪽 자식 노드 인덱스 = 2i - 노드 i의 오른쪽 자식 노드 인덱스 - 2i + 1

---

링크 표현법

- 트리에서의 노드가 구조체로 표현

- 각 노드가 포인터를 가지고 있어 이 포인터를 이용하여 노드와 노드를 연결

- 위와 같이 하나의 노드가 3개의 필드(데이터 필드, 왼쪽/오른쪽 자식 노드 필드)를 가짐

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

- 루트 노드를 가리키는 포인터를 알면 트리 내의 모든 노드에 접근 가능(연결 리스트와 유사)

- 연결 리스트는 1차원적인 연결 구조, 이진 트리는 2차원적으로 연결된 구조

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

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

int main(void) {
	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;
	n3->right = NULL;

	n3->data = 30;
	n3->left = NULL;
	n3->right = NULL;

	free(n1); free(n2); free(n3);
	return 0;
}