자료구조 강의 7화 :: 이진 트리, 포화 이진, 완전 이진

자료구조 7화를 듣고 배운내용

 

 

KEYWORDS

• 트리: 논리적 계층이 있는 구조, 트리를 구성하는 항목을 노드 혹은 점(vertex)라고 한다.
• 루트 노드: 최상위 노드, 부모가 없는 노드(진입 차수 = 0)
• 서브 트리: 부모 노드를 삭제하면 생기는 트리들
• 리프 노드: 최하위 노드, 서브 트리를 갖지 않는 노드(진출 차수 = 0)
• 진입 차수: 트리의 어떤 노드에 들어오는 선의 개수
• 진출 차수: 트리의 어떤 노드에 나가는 선의 개수
• 내부 노드: 루트도 잎도 아닌 노드
• 형제(sibling): 같은 부모를 갖는 노드

 

• 포화 이진 트리: 이진 트리에서 각 레벨에 최대 개수(노드당 2개씩) 노드를 가지는 트리
• 완전 이진 트리: 높이 k 이진트리에서 k-2까지 다 채우고, 마지막 k-1 레벨에서 왼쪽부터 오른쪽으로 노드가 차례로 채워진 트리
• 순회(traverse): 트리의 각 노드를 빠짐없이, 중복없이 한 번씩만 방문

 

 

트리

• 검색의 편리
• 논리적 계층(구조화)
• 계급적 특성

트리의 높이: 루트 노드로부터 가장 멀리 있는 노드까지에 1을 더한 값

 

 

이진 트리

모든 노드의 차수가 2이하인 트리

컴퓨터 내부에서 구현하기 효율, 엄청 많이 쓰인다.

 

 

출처: https://limkydev.tistory.com/134

 

 

배열을 이용한 이진트리

트리가 완전 이진 트리 or 포화 이진 트리인 경우 낭비되는 공간이 없어 효율

=> 완전, 포화 이진 트리가 아닌 경우 공간 낭비

이 부분 때문에 배열을 잘 이용하지 않는다.

 

 

이진 트리 순회

보통 재귀함수 이용한다.

전위 순회(preorder)

루트 노드 - 왼쪽 자식노드 - 오른쪽 자식노드 순서대로 접근(출력)

 

후위 순회(postorder)

왼쪽 자식 - 오른쪽 자식 - 루트 노드 순서

 

 

일반 트리 => 이진 트리 변환 방법도 알아보자

바꾸는 이유는 메모리의 낭비를 막기 위해서