Computer Science/Data Structure
2021. 11. 9.
[Data Structure] 트리
트리란 노드와 노드들을 이어주는 엣지로 이루어진 자료구조이다. 그래프의 일종이다. 트리의 특징 하나의 루트 노드를 가지며 부모 노드는 0개 이상의 자식 노드를 갖는다. 트리에는 사이클이 존재할 수 없다. 만약 사이클이 존재한다면 이는 트리가 아니라 그래프이다. 루트에서 어떤 노드로 가는 경우는 오직 하나이다. 트리 순회 방식 전위 순회 각 루트를 순차적으로 먼저 방문하는 방식이다. 루트 → 왼쪽 자식 → 오른쪽 자식 1 2 4 8 9 5 10 11 3 6 13 7 14 중위 순회 왼쪽 하위 트리를 방문 후 루트를 방문하는 방식이다. 왼쪽 자식 → 루트 → 오른쪽 자식 8 9 4 10 11 5 2 13 6 14 7 3 1 후위 순회 왼쪽 하위 트리와 오른쪽 하위 트리를 방문 후 루트를 방문하는 방식이다. ..
![[Data Structure] 트리](http://i1.daumcdn.net/thumb/C450x300/?fname=https://blog.kakaocdn.net/dn/yhIBz/btrkcqNH2eD/GyAm9afrNRE7RaD3l6PPPK/img.png)