트리(Tree) 자료구조

---

트리의 개념

 

트리(Tree)는 원소들 간에 계층 관계를 가지는 계층형, 비선형 자료 구조
일반적으로 원소들 간에 1:다 관계를 가진다.

 

트리 구성 요소

 

구분	설명
루트노드(root node)	트리의 시작 노드
간선(edge)	노드를 연결하는 선
형제노드(sibling node)	같은 부모 노드를 가진 자식 노드들
서브트리(subtree)	부모노드와 연결된 간선을 끊었을 때 생성되는 트리

 

트리 개념도

 

출처: 탑싯 에센스

---

기출 문제

---

예전에 한창 코딩 공부할 때 트리 및 그래프 관련 웬만한 알고리즘은 다 코딩할 수 있었는데, 

인간은 망각의 동물이라서, 3년 가까이 하지 않다 보니 거의 잊어버렸네요.

쉽지 않겠지만, 나중에 기회가 된다면 기초 Pseudo Code 까지는 업데이트 해 보겠습니다.

 

자료구조 및 알고리즘 관련 고득점을 목표로 한다면,

트리 자체의 개념을 익히는 것도 중요하지만, 이진트리와 알고리즘을 연계해서

동작 방식과 Pseudo Code 작성할 수 있는 수준까지 준비를 하시길 권고드립니다.

---

중요한 문제입니다.

(응용 126-4-1)
이진트리를 순회하는 방식은 전위 순회, 중위 순회, 후위 순회 등으로 나뉜다.
모든 순회 방식은 루트로부터 순회를 시작하여 트리의 모든 노드들을 반드시 한 번씩 방문하여 순회를 종료한다.
이와 관련하여 다음을 설명하시오.

가. 전위 순회 중위 순회, 후위 순회 방식
나. 아래 그림의 이진트리를 대상으로 전위 순회, 중위 순회, 후위 순회를 수행할 때,
각각의 방문순서

 

(관리 107-4-6)
다음과 같은 Node 구조를 통해 생성된 이진트리에 대해 물음에 답하시오.

Typedef struct Node {
int value;
struct Node* left;
struct Node* right;}
Node;

이진 탐색 트리의 루트 노드와 정수를 인자로 받아, 주어진 숫자를 이진 탐색 트리에 삽입하는 재귀 함수 Node* insertBinaryTree(Node*node, int val)을 작성하시오.

이진 탐색 트리란
"트리 내의 임의의 노드에 대해 해당 노드의 값이 해당 노드의 부분 트리의 모든 값보다 크고
오른쪽 부분 트리의 모든 값보다 작은 이진트리"를 말한다.

여기서 인자로 받은 val값이 트리 내에 존재하지 않는다고 가정하며, 작성한 리턴 값은 삽입이 완료된 트리의 루트 노드이다.

 

(관리 99-1-1)
이진 탐색 트리(Binary search tree)의 데이터 삽입 과정에 대하여 설명하시오.

 

(응용 116-4-2)
아래 그래프에서 최소 신장 트리(MST: Minimum Spanning Tree)를 구하는 과정을 2개의 알고리즘을 이용하여 설명하시오.

가. 크루스컬(Kruskal) 알고리즘
나. 프림(Prim) 알고리즘

 

참고 자료

 

탑싯 에센스 - 소프트웨어 개발

 

 

인터넷 검색하면서 트리에 대해 잘 설명된 블로그가 있어서 공유 차원에서 링크합니다. (↓)

 

[자료구조] 트리 (Tree) (tistory.com)

[자료구조] 트리 (Tree)