트리구조_이진트리(Binary tree)

트리

어떤 요구조건을 만족하는 정점과 선분들의 비어있지 않는 집합

정점은 또한 노드라고도 표현한다.

노드 : 동그라미 하나하나 트리의 요소를 나타냄

루트노드 : 부모노드의 최상단

단말노트 : 자식이 없는 노드

서브트리 : 트리안에 존재하는 트리

트리의 높이 : 가장 최상단부터 레벨을 1,2,3이라 매긴다.

트리의 성질

트리에는 어떤 두 노드를 연결 하는 경로는 한개다. (부모-자식간 양방향의 경로가 있어도 경로는 한개)

최소 공통 선조

어떤 두 노드는 최소 공통 선조를 지님.

루트가 최소공통선조가 되거나 근의 자식들중의 부분트리에 두 노드가 속하게 되므로 최소 공통선조는 항상 존재

각 노드가 최소공통 선조에 이르는 경로를 연결하면 두 노드간 최소 경로가 된다.

이진트리(Binary tree)

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 가지는 트리 구조로,

 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

이진트리 순회방법

목적/구성에 따라 순회하는 방법이 다르다.(기준은 루트노드 기준)

1. 전위순회(Preorder) - 루트 -> 왼쪽서브트리 -> 오른쪽 서브트리

F, B, A, D, C, E, G, I, H (root, left, right)

2. 중위순회(Inorder) - 왼쪽서브트리 -> 루트 -> 오른쪽서브트리

A, B, C, D, E, F, G, H, I (left, root, right)

3. 후위순회(Posterorder) - 왼쪽서브트리 -> 오른쪽서브트리 -> 루트

A, C, E, D, B, H, I, G, F (left, right, root)

학습참고 :

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C

https://coderkoo.tistory.com/9