Data Structure - Trees

Tree

• 노드로 이루어진 자료구조 이고, node 들과 노드를 연결하는 edge(link, branch)로 구성되어 있다.
• 그래프의 한 종류이고, 방향성이 있는 비순환 그래프의 종류이기 때문에 loop이나 cycle이 없다.
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.
  https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
  
• root node : 부모가 없는 노드이고 트리는 하나의 루트노드만을가진다.
• leaf node : 자식이 없는 노드

tree 종류

1. 이진 트리 (binary tree)
   • 각 노드가 최대 두개의 자식을 갖는 트리
2. 이진 탐색 트리
   • 부모 노드 기준으로 정렬이 되어있는 이진트리에 왼쪽자손은 부모보다 작은 노드, 오른쪽 자손은 부모보다 큰 형태로 구성

전위 순회(Pre-order traversal) : 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문

중위 순회(In-order traversal) : 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문.

이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
후위 순회(Post-order traversal) : 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.

레벨 순서 순회(Level-order traversal) : 너비 우선 순회(Breadth-First traversal | BFS)라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법.

순회 예시 (첫번째 그림을 순회 하였다고 할때)

전위(pre) : 2, 7, 2, 6, 5, 11, 5, 9, 4

중위(in): 2, 7, 5, 6, 11, 2, 5, 4, 9

후위(post): 2, 5, 11, 6, 7, 4, 9, 5, 2

레벨(bfs): 2, 7, 5, 2, 6, 9, 5, 11, 4

참고블로그
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

https://gseok.gitbooks.io/algorithm/content/d2b8-b9ac-c54c-ace0-b9ac-c998/d2b8-b9ac-c21c-d68c.html

http://yoonbumtae.com/?p=2378