Tree(트리)의 개념, 이진 트리 ,이진 트리 종류 [자료구조]

출처 나무위키

트리 :  두 지점의 연결관계로 구성되어지고 계층 관계가 존재한다는 것이 특징이다.

트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다.

 

트리에서 쓰이는 용어들을 공부해보자.

노드 : 각 지점을 의미하며 ( 정점이라고도 불린다. )
간선 : 두 노드를 연결하는 선 ( 예지 라고도 불린다.)
루트 노드 : 트리에서 맨 꼭대기를 의미한다.
부모 자식 : 위에있는 것이 부모, 아래에 있는 것이 자식이라고 한다.
차수 : 특정 노드를 중심으로 자식이 몇 개 있는지를 의미한다.
깊이 : 루트 노드와 얼마나 떨어져있는지를 의미한다.
높이 : 트리에서 깊이가 가장 깊은 높이 , 루트노드의 깊이를 0이라 했을때 가장 긴 깊이에 1을 더한 값
리프 노드 : 자식을 가지고 있지 않은 노드

트리에는 사이클이 존재할 수 없다. 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작노드로 돌아올 수 없다.

 

이진 트리 : 자신의 수가 최대 2개로 제한이 되어있는 트리 (자식의 수가 0~2개)

장점 : 구현하기 쉽고 배열로도 구현 가능

자식 노드가 둘이기 때문에 왼쪽 자식 오른쪽 자식으로 나뉜다.

 

이진트리는 재귀를 사용하면 비교적 쉽게 탐색을 할 수 있다.

 

방문 순서에 따른 세가지 방법

1. 전위 탐색 : 부모 - 왼쪽 자식 - 오른쪽 자식
2. 중위 탐색 : 왼쪽 자식 - 부모 - 오른쪽 자식
3. 후위 탐색 : 왼쪽 자식 - 오른쪽 자식 - 부모

 

이진 트리 종류

 

완전 이진 트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있다.

노드가 왼쪽에서 오른쪽으로 채워져야한다.

 

전 이진 트리 : 모든 노드가 0개 또는 2개 자식 노드를 갖는 트리이다.

 

포화 이진 트리 : 모든 레벨이 노드로 꽉차있는 트리를 말한다. 전 이진트리의 성질도 만족해야한다.

 

이진 탐색 트리 : 부모 키가 왼쪽 자식노드의 키보다는 크고 오른쪽 자식 노드의 키보다는 작다.