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

1. 순차 자료구조를 이용한 이진 트리 구현

1) 1차원 배열의 순차 자료구조 사용

• 높이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용
• 인덱스 0번 : 실제로 사용하지 않고 비워둔다.
• 인덱스 1번 : 루트 저장

 

2) 이진 트리의 1차원 배열에서의 인덱스 관계

 

노드	인덱스	성립 조건
노드 i의 부모 노드	[ i/2 ] 정수로 만듦 (가우스 기호)	i > 1
노드 i의 왼쪽 자식 노드	2 * i	(2 * i) ≤ n
노드 i의 오른쪽 자식 노드	(2 * i) + 1	(2 * i + 1) ≤ n
루트 노드	1	0 < n

 

3) 이진 트리의 순차 자료구조 표현 단점

• 사향(Skewed) 이진 트리의 경우에 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
• 트리의 원소 삽입, 삭제에 대한 배열의 크기 변경 어려움

 

2. 연결 자료구조를 이용한 이진 트리 구현

1) 단순 연결 리스트를 사용

• 이진 트리의 모든 노드는 2개의 자식 노드를 가지므로 일정한 구조의 노드를 사용할 수 있다.

 

2) 이진 트리의 노드 구조에 대한 C언어 구조체

 

typedef struct TREENODE{
	char data;
	struct TREENODE *left;
	struct TREENODE *right;
}TNODE;

 

3) 완전 이진 트리의 구현

 

완전 이진 트리

 

3. C언어 실습

 

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

typedef struct NODE {
	struct NODE *left;
	int num;
	struct NODE *right;
}NODE;

int menu(void);
void add(NODE **root);
void prt(NODE *root);
void insertNode(NODE **root, int num);

int main(void) {
	NODE *root = NULL;
	while (1) {
		switch (menu()) {
		case 1:
			add(&root);
			break;
		case 2:
			prt(root);
			break;
		case 3:
			return 0;
		}
		puts("\n");
	}
	return 0;
}

int menu(void) {
	int n;
	printf(" 1. 추가\t");
	printf(" 2. 출력\t");
	printf(" 3. 중지");
	printf("\n\n 번호 : ");
	scanf("%d", &n);
	return n;
}

void add(NODE **root) {
	int num;
	printf(" 입력값 : ");
	scanf("%d", &num);
	insertNode(root, num);
}

void prt(NODE *root) {
	if (root) {
		prt(root -> left);
		printf(" %d, ", root -> num);
		prt(root -> right);
	}
}

void insertNode(NODE **root, int num) {
	NODE *node1 = NULL;
	NODE *node2 = *root;
	NODE *newNode;

	while (node2) {
		if ((node2 -> num) == num) {
			printf("Data exists already\n");
			return;
		}
		node1 = node2;
		if ((node2 -> num) > num)
			node2 = node2 -> left;
		else
			node2 = node2 -> right;
	}

	newNode = (NODE *)malloc(sizeof(NODE));
	newNode -> num = num;
	(newNode -> left) = (newNode -> right) = NULL;

	if (node1) {
		if ((node1 -> num) > num)
			node1 -> left = newNode;
		else
			node1 -> right = newNode;
	}
	else
		*root = newNode;
}

 

 

실행