트리

[WonYong-Jang]

트리

• 트리란 연결 리스트와 유사한 자료 구조지만 연결 리스트가 단순히 다음 노드를 가르키는 선형이라면 트리는 각 노드가 여러 개의 노드를 가리키는 비선형입니다.
• 트리 구조는 그래프의 한 종류로 1개 이상의 노드로 구성되며 사이클이 없는 그래프로 임의의 두 노드간에 하나의 경로만이 존재
• 트리의 root는 부모를 가지지 않고 최대 하나의 root 노드가 있을 수 있습니다.
• edge는 부모와 자식을 잊는 연결 선입니다. 자식이 없는 노드를 leaf 노드라고 부릅니다.
• 자식이 하나라도 있는 노드 internal 노드
• 노드의 차수(degree) 는 특정 노드의 자식 수 / 트리의 차수는 트리의 모든 노드 중에 가장 높은 차수
• 자식 노드에 대하여 상위 노드(부모) / 동일한 부모를 가진 자식노드(형제) / 특정 노드의 부모노드의 집합 (조상)이라하고 반대로 특정 노드의 부속 트리의 모든 노드 집합을 자손
• sibilings , ancestor, descendant
• 노드의 depth는 root 에서 해당 노드까지 경로의 길이 (트리에서 가장 큰 레벨 )
• 노드의 height 는 해당 노드에서 가장 깊은 노드까지 경로의 길이 ( 하나의 노드를 가진 트리의 높이는 0)
• 노드의 크기는 자신을 포함한 descendant 들의 수를 말합니다.
• level은 루트 노드 아래로 한단계식 레벨을 가지며 루트가 레벨 1
• 모든 노드들이 자식을 하나만 가질 때 이를 skew 트리(편향 트리)라고 부름 ( left skew, right skey)

이진 트리

모든 노드들이 둘 이하의 자식을 가질 때 이를 이진 트리

• 순 이진 트리( Strict Binary Tree ) : 노드들이 정확히 자식 노드를 가지거나 아예 안가질때
• 전 이진 트리 ( Full Binary Tree ) : 각 노드가 정확히 두 개의 자식노드를 가지고 모든 leaf 노드들이 동일한 레벨 이진 트리
• 완전 이진 트리( Complete Binary Tree) : root 에서 시작하여 왼쪽에서 오른쪽으로 노드들이 번호를 매겼을 때 그 번호가 1부터 노드들의 수까지 완전히 연속적인 수를 얻게 됩니다. / 설명
• 레벨이 n인 이진트리의 최대 노드 수는 2^n-1 이다. ( ex 레벨이 2면 최대 노드수 3개)
• 이진트리에서 단말 노드(terminal node)의 개수는 분지수(degree)가 2인 내부노드(internal node)의 개수 보다 하나 더 많다.

트리 순회

http://3dmpengines.tistory.com/423
먼저 트리 순회 방법이 있는 이유는 트리는 선형이 아닌 비선형이기 때문에 모든 노드들을 거쳐가기 위한 방법이 필요하게 된다.

• 전위순회
• 중위순회
• 후위순회
• 레벨순회 : 트리의 각 노드를 레벨 순서로 방문 ( 같은 레벨에서는 왼쪽에서 오른쪽 순)
  사용 자료구조로는 큐를 사용 합니다

수식 트리

https://blog.naver.com/muramura12/220704218849

[WonYong-Jang]

트리의 지름

• 트리의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미.
• 모든 두 노드를 잡고 구하는 경우는 N^2 시간복잡도
• O(N) 시간 안에 트리의 지름을 구하는 방법

1. 트리의 임의의 정점 x를 잡는다.
2. 정점 x에서 가장 먼 정점 y를 찾는다.
3. 정점 y에서 가장 먼 정점 z를 찾는다.

• 백준 1967

[WonYong-Jang]

105. Construct Binary Tree from Preorder and Inorder Traversal

preorder , inorder 이용하여 binary tree 구하기 !!!!!!!!!

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

=> inorder : 각 서브 트리의 root 가 중간에 나오기 때문에 앞에서 부터 인덱스 별로 hash 화 시켜준다면
서브 트리의 root 기준으로 인덱스가 작은 값은 left child / 큰 값은 right child

=> preorder : root가 처음 나오기 때문에 순차적으로 inorder 의 hash 값을 찾아서 연결한다.

106. Construct Binary Tree from Inorder and Postorder Traversal

postorder , inorder 이용하여 binary tree 구하기 !!!!!!!!!

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

풀어보기!!!!!!!!