[자료구조] 이진 트리

이진 트리의 표현 - 배열 표현법

: 모든 이진 트리를 포화 이진 트리라고 가정하여 각 노드에 번호를 붙인다.

 

 

인덱스 관계

• 노드 i의 왼쪽 자식 노드 인덱스 : i*2
• 노드 i의 오른쪽 자식 노드 인덱스 : i*2+1
• 노드 i의 부모 노드 인덱스 : i/2

이진 트리의 표현 - 링크 표현법

: 포인터를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법

노드는 구조체로 링크는 포인터로 구현한다.

 

아래의 그림같은 트리를 구현해보자.

 

전체 코드

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
	int data;
	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;
	n2->right = NULL;

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

	printf("%d\n", n1->left->data);
	printf("%d", n1->right->data);
}

n1의 왼쪽 노드의 데이터를 출력하라고 했으니 20이 출력될 것이다.

n1의 오른쪽 노드의 데이터를 출력하라고 했으니 30이 출력 될 것이다.