자료구조 트리(Tree)

◎ 트리(Tree) : 배열(Array), 링크드 리스트(Linked List), 스택(Stack), 큐(Queue) 같이 선형 자료구조(Linear Data Structure)와 달리 트리는 계층적 자료구조(Hierarchical Data Structure) 입니다.

◎ 용어(Tree Vocabulary)

- 노드(Node) : 트리 구조의 각각의 요소(Element)

- 루트(Root) 노드 : 최상위(Topmost) 노드

- 자식(Child) 노드 : 해당 노드 바로 아래 노드

- 부모(Parent) 노드 : 해당 노드 바로 위 노드

- 잎(Leaf) 노드 : 자식 노드가 없는 노드

◎ 사용 목적

1. 컴퓨터 파일 시스템과 같이 계층을 형성하는 정보를 저장하기 위해 사용합니다.

2. 이진 탐색 트리와 같은 정렬되어있는 트리는 적당한(Moderate) 접근, 탐색을 제공합니다. (링크드 리스트보다 빠르지만 배열보다 느림)

3. 트리는 적당한(Moderate) 입력/삭제를 제공합니다. (배열보다 빠르지만 정렬되지 않은 링크드 리스트보다 느립니다.)

4. 링크드 리스트와 마찬가지로 배열과 달리 트리는 노드들이 포인터로 연결되어있어 노드수의 상한선(Upper limit)이 없습니다.

◎ 트리 응용(Applications)

1. 계층적 데이터를 다룹니다.(Manipulate)

2. 정보를 검색하기 쉽게 만듭니다. - 트리 순회(Tree Traversal) 참조

3. 정렬된(Sorted) 리스트 데이터를 다룹니다.

4. 라우터 알고리즘(Router Algorithms)

◎ 이진 트리(Binary Tree) : 자식 노드의 수가 2개 이하인 트리를 이진 트리라고 합니다. 이진 트리 각각의 노드들은 오직 2개의 자식만 가질 수 있으며, 이를 일반적으로(typically) 왼쪽 자식, 오른쪽 자식이라고 부릅니다.

- C에서 이진 트리 표현(Binary Tree Representation in C) : 트리에서 최상위 노드는 포인터로 표현됩니다. 트리가 비어있다면(empty) 루트의 값은 NULL입니다.

- C에서 트리 노드는 구조체로 표현합니다. 아래 예제는 integer형 자료를 저장하는 트리 노드의 예제입니다.

struct node  // 노드 구조체

{

int data; // 데이터 값

struct node *left; // 왼쪽 자식

struct node *right; // 오른쪽 자식

};

- C에서 4개의 노드를 생성하는 간단한 예제입니다.

struct node* newNode(int data) // 노드 생성

{

struct node* node = (struct node*) malloc(sizeof(struct node)); // node 구조체를 동적 생성

node -> data = data; // 입력 한 값을 저장 

node -> left = NULL; // 왼쪽 자식 : 없음

node -> right = NULL; // 오른쪽 자식 : 없음

return node; // 노드 반환

}

int main()

{

struct node* root = new Node(1); // 노드 생성(루트 노드, 값 = 1)

root -> left = newNode(2); // 노드 생성(왼쪽 자식, 값 = 2)

root -> right = newNode(3); // 노드 생성(오른쪽 자식, 값 = 3)

root -> left -> left = newNode(4); // 노드 생성(왼쪽 자식의 왼쪽 자식, 값 = 4)

return 0;

}

위의 소스코드를 그림으로 표현하면 다음과 같습니다.

정보가 유익하셨다면 아래 공감버튼 눌러주시면 감사하겠습니다.

질문사항은 댓글로 달아주시면 성의껏 답변해드리겠습니다.