◎ 트리(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;

}


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



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

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




to Top