Tree : 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라 부른다.
루트라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결한다.
노드(Node) : 트리 구조를 이루는 모든 개별 데이터
루트(Root) : 트리 구조의 시작점이 되는 노드
부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
Graph : 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료 구조
정점과 정점 사이의 관계를 간선으로 표현하는 방식을 사용한다.
정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.
간선 (edge): 정점 간의 관계를 나타낸다.
인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻한다.
가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프를 뜻한다.
비가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻한다.
무(방)향 그래프 (undirected graph): 단방향 그래프와 달리 정점과 정점 사이의 관계가 양방향일 경우이다.
진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.
사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.
Binary Search Tree : 모든 왼쪽 자식의 값이 루트나 부모보다 작고 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 트리
트리 순회
전위 순회 : root를 먼저 방문 뿌리 -> 왼쪽 자식 -> 오른쪽 자식 순
중위 순회 : 왼쪽 하위 트리를 방문 후 root를 방문 왼쪽 자식 -> 뿌리 -> 오른쪽 자식 순
후위 순회 : 하위 트리 모두 방문 후 root를 방문 왼쪽 자식 -> 오른쪽 자식 -> 뿌리 순
