트리(Tree)란?
트리란 그래프의 일종으로, 비순환적인 그래프를 말한다.
즉, 사이클이 없는 그래프를 트리라고 한다. 사이클이 존재하지 않아 모습이 나무를 닮아 트리라는 이름이 붙여졌다.
노드가 n 개라면 간선 n-1개로 이루어진 그래프이다. 이 특징 또한 사이클이 없기 때문에 성립한다.
트리 기본 용어
리프(leaf)
이웃한 노드가 하나만 있는 노드를 말한다.
나무 중 제일 끝에 위치한 나뭇잎과 같이 제일 끝에 있는 노드를 의미한다.
루트(root)
제일 위에 위치한 노드라고 생각하면 된다.
나무의 시작인 뿌리와 같이 트리의 시작으로 설정한 노드이다.
부모(parent) 노드
어떠한 노드보다 위에 위치하며 루트 쪽에 가까이 위치한 노드를 의미한다.
자식(child) 노드
어떠한 노드보다 아래에 위치하며 루트쪽에 더 멀리 위치한 노드를 의미한다.
트리 순회
모든 노드를 순회하며 처리하는 방법은 3가지 존재한다.
방문한 노드를 언제 처리하는지에 따라 구분된다.
전위(preorder) 순회: 루트 노드를 처리한 뒤, 왼쪽 서브트리를서브 트리를 순회한 다음, 오른쪽 서브 트리를 순회한다.
중위(inorder) 순회: 먼저 왼쪽 서브트리를 순회하고, 루트 노드를 처리한 다음, 오른쪽 서브 트리를 순회한다.
후위(postorder) 순회: 먼저 왼쪽 서브트리를 순회하고, 오른쪽 서브 트리를 순회한 다음, 루트 노드를 처리한다.
